Description

Given the inorder and postorder traversal sequences of a tree, please print the corresponding preorder traversal sequence.

 

Input

• Input includes multiple sets of test cases, and each test case consists of two lines of strings.
• For each test case, the first line is the inorder traversal sequence, and the second line is the postorder traversal sequence.
• Each line is represented as: “v1,v2,v3,…,vn” where vi is the key of the tree node.
• No duplicated keys in a tree.
• Each key is an integer within [1,100000]. In other words, the key of tree nodes does not exceed 100000.
• The number of tree nodes is an integer within [1,100000]. In other words, the number of tree nodes in a tree does not exceed 100000.

Output

• For each test case, print the corresponding preorder traversal sequence.
• Each sequence should be followed by a new line.
• Commas separate the out keys in the traversal sequence.
• You do not need to add a comma at the end of the sequence.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss