Automated Train Routing

Ingrid is the head of a large railway station. One of her tasks is to route trains arriving at the single entrance to the correct platforms. The station is structured as a directed tree: the entrance connects to one node, switches (which have exactly one inbound track and two outbound tracks) can direct trains to their left or right branch, and platforms (with a single inbound track) are dead ends where trains immediately vanish.

Each switch starts by directing trains to its left branch. Every morning, Ingrid prepares a toggling schedule. For a given train number and switch id, if a train passes through that switch at that train number, the switch is toggled immediately before the train chooses its branch. (If multiple toggles are scheduled for the same switch and train number, they cancel pairwise so that an odd number of toggles causes a state change.)

The process is as follows:

$$\text{For each train } t=1,2,\ldots,T:\\ \quad \text{Start at the entrance.}\\ \quad \text{If at an entrance node, move to its only child.}\\ \quad \text{At a switch node } s:\\ \quad \quad \text{If toggle instructions for } s \text{ exist for train } t \text{ (and the count is odd), toggle the state of } s.\\ \quad \quad \text{Follow the active branch (0 for left, 1 for right).}\\ \quad \text{Stop when a platform is reached and output its id.} $$

Your task is to simulate the path of each train and output the platform id where it arrives.

inputFormat

The input consists of several parts:

• An integer n denoting the number of nodes in the railway network. Nodes are numbered from 1 to n.
• The next n lines describe these nodes. The format for each node is as follows:
  • If the node is the entrance (always node 1), the format is: entrance x where x is the id of its only child.
  • If the node is a switch, the format is: switch L R where L and R are the left and right child ids respectively. All switch nodes initially have their state set to direct trains to the left branch.
  • If the node is a platform, the line contains just the word platform.
• An integer T representing the number of trains arriving.
• An integer M representing the number of toggle instructions.
• Then follow M lines, each containing two integers: the train number at which a toggle is to occur and the id of the switch to toggle. Note that a toggle for a given switch is executed only when a train of the specified number reaches that switch. If the train does not visit the switch, the toggle instruction is ignored.

Note: You can assume that all nodes (except the entrance) have exactly one inbound track, and every node is reachable from the entrance.

outputFormat

Output T lines. The i-th line (1-indexed) should contain the id of the platform where the i-th train arrives.

sample

6
entrance 2
switch 3 4
platform
switch 5 6
platform
platform
5
3
2 2
4 4
4 2

3
5
5
3
3

</p>