Rebuild from two lists

Problem

A tree with different values was written down twice: once in preorder and once in inorder. Rebuild the tree and print its postorder list, separated by spaces.

Input, output and limits

Input: Line 1: the preorder list of a binary tree. Line 2: its inorder list. Both are separated by spaces.
Output: The postorder values on one line.
Constraints: 1 ≤ number of nodes ≤ 2000
All values are different integers between 1 and 100000

Examples

Example 1

Input

3 9 20 15 7
9 3 15 20 7

Output

9 15 7 20 3

Prints 9 15 7 20 3.

Example 2

Input

1
1

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

The first preorder value is the root.

Hint 2

Find it in the inorder list: the values before it are the left side.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Where two reporting lines meethard
Best route anywherehard
Zigzag levelsmedium
Count the routes with a given totalhard
Valid price treemedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Trees problems

Problem

Input, output and limits

Examples

Hints

More Binary Trees problems