Description

Given an infix Boolean expression with parentheses, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Build a corresponding syntax tree for it.

To parse the infix expression with parentheses, use the grammar below.

EXPR = FACTOR | EXPR OP FACTOR

FACTOR = ID | (EXPR)

EXPR is the expression, ID is one of ‘A’, ‘B’, ’C’, or ‘D’, and OP is one of ‘&’ or ‘|’.

 

You will be provided with main.c and function.h. main.c contains the implementation of functions printPrefix and freeTree. function.h contains the definition of tree node and variables. You only need to implement the following three functions in function.c.

BTNode* makeNode(char c)   // create a node without any child

BTNode* EXPR()   // parse an infix expression and generate a syntax tree

BTNode* FACTOR()   // use the parse grammar FACTOR = ID | (EXPR) to deal with parentheses

 

For OJ submission:

        Step 1. Submit only your function.c into the submission block.(Please choose C compiler)

        Step 2. Check the results and debug your program if necessary.

Input

The input contains N infix expressions, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, two operators ‘&’ and ‘|’, and parentheses. All parentheses are matched. 

Output

The output contains N prefix expressions without parentheses, which are preorders of syntax trees.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10966.c

Partial Judge Header

10966.h

Tags

Discuss

Description

 

You are given some binary trees of total N vertices numbered from 1 to N.

And M branches connect those trees.

There are Q questions.

Print every direction if you want to walk from node A to node B (Guaranteed only one path if it can be reached),

or "oops" if you can't walk there. 

P: move to parent

R: move to right child

L: move to left child

B: move to branch

 

Limit:

Testcases 1~2: only one tree, M = 0.

Testcase 3: no more than two trees.

Testcases 4~5: N, M <= 3000.

Input

The first line contains two integers N, M (2≤N, M≤3000).

Each of the next N lines contains 2 integers, representing the left child and the right child of the i th node. (and 0 means empty)

Each of the next M lines contains 2 intergers Bi, Bj, representing there is a branch between the Bi node and the Bj node.

The next line contains an integer Q (1≤Q≤3000).

Each of the next Q lines contains two integers, A, B.

Output

For each question, output every direction that walks from node A to node B, or "oops" if you can't walk there. 

Remember to add a new line in the end of each question.

Sample Input  Download

Sample Output  Download

Tags

Discuss