Borrowing a Lump Only to Come Back with One

"Borrowing a lump only to come back with one: ad hoc"

The old man with the lump on his face went to the goblin to have his big lump removed, but the goblin, who loves pranks, wants to attach even more lumps instead. For convenience, every lump is treated as a line segment, and at the start the old man has exactly one lump, lump $0$, whose length is infinite. The goblin always attaches lumps so that the connection relations among all lumps form a tree. That is, the top of every lump other than lump $0$ touches the bottom of exactly one lump.

While attaching lumps, the goblin asks the old man, "What lump is this far above this lump, hmm?" The goblin promised that if all these questions are answered correctly, he will remove every lump at the end. Since the old man is not confident about solving them, you will give the answers on his behalf.

To keep anyone from predicting where lumps will be attached in advance, the goblin uses an unusual method to decide the attachment position.

The first line gives the number of goblin actions $Q$ ($1 \le Q \le 150\,000$).

Across $Q$ lines, the goblin's actions are given in order, each in the form "query $x$ $L$" or "ad-hoc $k$ $L$". At the moment the goblin is about to act, let the number of lumps attached to the old man be $M$.

• "query $x$ $L$": Starting from the bottom end of lump $x$ and going $L$ up along the lumps, you must answer which lump is there. If that point is the boundary between two lumps, answer the number of the upper lump. This answer becomes the "last answer" from then on. ($0 \le x < M$, $1 \le L \le 10^{18}$)
• "ad-hoc $k$ $L$": Compute $x = (k +$ "last answer"$) \mod M$, then create a new lump $M$ of length $L$ and attach it so that the top of lump $M$ touches the bottom of lump $x$. When attaching lump $M$, make sure it touches no lump other than lump $x$. If no query has been given yet, the "last answer" is taken to be $0$. The sum of all $L$ given in all ad-hoc actions the goblin performs is at most $10^{18}$. ($0 \le k < M$)

At least one query is always given.

Output the answers to all query actions in order, one per line.