Hard-working Student

Time limit1sMemory limit128 MB

Summary

Simulate a growing graph with forward and backward edges, processing commands whose action strings execute right to left, printing results of 'k' and '=' actions.

Level: Medium6 of 10
Topics: Graph, Simulation, Implementation
Solved: No attempts yet

Problem

Billy is a hard-working student who studies graph theory. He must write a program that builds the graph shown in the figure above.

The vertices carry integer keys $0, 1, \dots, N-1$ ( $N \le 10000$ ). The graph has two kinds of directed edges: forward edges (marked F in the figure) and backward edges (marked B). The vertices are arranged in rows of two, where row $r$ holds keys $2r$ (left) and $2r+1$ (right). A forward edge leaves a vertex for the opposite column of the next row down: from $2r$ to $2r+3$ , and from $2r+1$ to $2r+2$ . A backward edge leaves a vertex straight up to the same column of the previous row: from a vertex $u$ to $u-2$ . The top vertices $0$ and $1$ have no backward edge.

The program starts from the initial graph that contains the vertices $0, 1, 2, 3$ and keeps building it according to a sequence of commands. Each command has the form

index0 string_of_characters index1

where index0 and index1 are vertex keys and string_of_characters is a sequence of actions executed from right to left. Each action is one of the following characters:

Character	Action
`f`	Follow the forward edge from the current node, creating the edge and its target vertex if it does not yet exist; the reached vertex becomes the current node.
`b`	Follow the backward edge from the current node, creating the edge and its target vertex if it does not yet exist; the reached vertex becomes the current node.
`k`	Print the key of the current node.
`<`	Store the current node into `v[index0]`.
`=`	Print `=` if `v[index0]` equals the current node, otherwise print `#`.

When present, the < and = actions may appear only as the left-most character of the action string (so they are executed last).

Here v is an array of nodes indexed by vertex key. The current node for the right-most (first executed) action is v[index1]; each f or b updates the current node for the actions to its left. A node is stored into v only by the < action. Initially the array holds v[0] = 0, v[1] = 1, v[2] = 2, and v[3] = 3.

Input

The input is a text file that contains the sequence of commands. White space (spaces, tabs, and newlines) may appear freely between tokens. The input ends at end of file.

Output

Each k and = action prints its result on its own line, starting at the beginning of the line, with no blank lines in between. Print the results in the order in which the actions are executed.

Examples1

Example 1
Input
```
4 <kf 3
0 =bb 4
7 <ff 3
```
Expected output
```
4
=
```