시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB65202039.216%

문제

It is very easy to produce the various traversals of a binary tree, however this problem requires you to produce the tree from the traversals. Specifically, given the pre-order and in-order traversals of a binary tree (not necessarily a binary search tree), reconstruct, if possible, the original tree.

For instance, the following tree will produce the traversals shown

      E
/ \
D   F
/ \
B   G
/ \   \
A   C   I
/ \
H   K
/
J

Preorder : EDBACFGIHKJ
Inorder : ABCDEFGHIJK

Postorder: ACBDHJKIGFE 

입력

Input will consist of representations of several trees, each on a single line, and terminated by a #. Each line will consist of two strings of up to 26 unique uppercase letters in the form

<pre-order> <space> <in-order>.

You can assume that the two strings will be permutations of each other.

출력

Output will consist of the post-order traversal of the reconstructed tree if possible, otherwise the words 'Invalid tree'.

예제 입력 1

EDBACFGIHKJ ABCDEFGHIJK
#


예제 출력 1

ACBDHJKIGFE


출처

• 데이터를 추가한 사람: kajebiii