Jas the Worm

Jas is a little worm who has decided to make his home in a tree. The tree he picks is very young: at the moment Jas moves in, it has only a single vertex, numbered $1$.

After that, both the tree and Jas go about their own business.

• The tree keeps growing, sprouting new vertices one at a time. An event written D x means a new vertex is added to the tree and attached to a vertex $x$ that is already present.
• Jas strolls around the tree, each step moving from his current vertex to one of its direct neighbours. An event written J x means Jas moves one step in the direction of vertex $x$. Note that the vertex he actually reaches is not given, only the vertex he is heading toward.

Newly attached vertices are numbered with consecutive integers: the first one added becomes vertex $2$, the next becomes vertex $3$, and so on. Jas always begins at vertex $1$.

Hektor is watching all of this and, after every move Jas makes, wants to know where Jas currently is. Can you help him?

The first line contains an integer $Z$ ($1 \le Z \le 10$), the number of test sets. The test sets are described one after another.

For each test set, the first line contains an integer $N$ ($1 \le N \le 10^6$), the number of events. Each of the following $N$ lines describes one event in one of two forms:

• D x (with $1 \le x \le$ the current number of vertices in the tree): a new vertex is attached to vertex $x$.
• J x (with $1 \le x \le$ the current number of vertices in the tree): Jas moves one step toward vertex $x$.

If, when a J x event arrives, Jas is already standing at vertex $x$, then he stays where he is, and that unchanged position must still be reported.

For each test set, print one line for every J x event, in the order the events occur. On each such line print the number of the vertex where Jas ends up right after that move.

Take the sample. First the tree sprouts four new vertices, so it has $5$ in total: vertices $1, 2, 3, 4$ form the chain $1 - 2 - 3 - 4$, and vertex $5$ is also attached to vertex $3$.

Then Jas starts to wander. His first move is toward vertex $5$, so he steps to vertex $2$. The next two moves toward vertex $5$ take him first to vertex $3$ and then to vertex $5$. The following two moves are toward vertex $4$: Jas has to walk back to vertex $3$ to reach it. Finally the tree grows a sixth vertex attached to vertex $1$; Jas heads that way, up the tree, and arrives at vertex $3$.