Description

You have an arithmetic expression that contains at most 5 variables A - E , binary operators '+', '-', '*', '/', where the '/' denotes integer division, and brackets '(', ')'.  Given the values for the variables, please calculate the answer.

Note: Here we define integer division as the integer part of division (not rounding down).  For example, 8 divided by 7 under division is 1.1428..., so 8 divided by 7 under integer division will be 1.  -8 divided by 7 is -1.1428..., so -8 divided by 7 under integer division will be -1 (instead of -2).

Input

The first line is the arithmetic expression.

The second line is an integer T.

In the following T lines, each line has 5 integers: the values for variable A to E.

Constraints

- 1 <= T <= 10
- Length of arithmetic expression <= 200,000
- -1,000,000,000 <= The intermediate values during calculation <= 1,000,000,000
- Division by zero will not happen during calculation

Output

Output T lines, each line is the answer to a set of values for variable A to E.

Output Format

There's no \n on the last output line!

[Answer 1]\n

[Answer 2]\n

...

[Answer T]

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given the preorder and inorder traversal of a binary tree. Your job is to reconstruct the tree and print the postorder traversal of the tree.

Note
- Each vertex of the tree is labeled 1 ~ n distinctly.

Input

Each input is given in three lines.

The first line contains an integer `n`: The number of vertices of the binary tree.

The second line is the preorder traversal of the tree.

The last line is the inorder traversal of the tree.

Note
- For both traversals, each vertex is seperated by an empty space.

Restriction
- 1 <= n <= 2*10⁵

Output

Output should be printed in one line. Containing the postorder traversal of the tree. Each vectex of the traversal should be seperated with an empty space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given a rooted Binary Tree, please print the last element that appears in the preorder traversal.

Note
- Each vertex of the tree is labeled 1 ~ n distinctly.

Input

The first line is n: The number of vertices of the tree.

Then followed by n lines. Each line contains l_i , r_i

l_i / r_i denotes the left/right child of the i-th vertex.

If the vertex has no left/right child, the coresponding l_i /  r_i will be -1.

Restriction
- 1 <= n <= 10⁶

Output

Your output should be one line with one integer x.

x is the last element of the preorder traversal.

Sample Input  Download

Sample Output  Download

Tags

Discuss