“Once you get the information, you get victory,” Big China Day says seriously.
After hundreds of battles against each other, neither Little Graphy nor the river crabs are able to defeat the other. One day, when Little Graphy is trying to figure out where the crabs are hidding just like usual, Blues rushes into her tent.
“Graphy! Graphy!” he yells. “How many times did I tell you not to be so rough?” Little Graphy scolds.
“Big China Day said that ‘information is the key to victory,’ right?” Blues says excitedly.
Little Graphy tries to answer, “I’m not sure if h…”
“Guess what? I found some encoded messages in the fortress we destroyed last week!” Blues keeps talking, “Look!”
“My intuition of graph tells me this must be a description of a tree.” Little Graphy says.
“Tree? This is just two sequence of integers and an big number,” he asks, “how can it be a tree?”
Little Graphy smiles to Blues and says, “Obviously, the first sequence is the preorder of the tree.”
“And, the second sequence should be its postorder.”
“The big number k means that the tree’s inorder is the kth possible inorder in lexicographical order.”
“Wow! How do we construct the tree?” Blues asks.
“Hummmmmmnmmmmm…In fact, we need to find out the inorder first…” Little Graphy answers.
Guess what? It’s your show time!
There’re several test cases in the file, ended with EOF.
Every test case starts with two integers n, k.
The following line contains n integers, representing the preorder.
The third line also contains n integers, representing the postorder.
For each test case, print the inorder traversal of the tree.