Hilbert's Hotel

Hilbert's Hotel has infinitely many rooms, numbered 0, 1, 2, $\cdots$. At most one guest occupies each room. Since people tend to check in as groups, the hotel keeps a group counter variable $G$.

Hilbert's Hotel opened today. Soon after, infinitely many people arrived at once, filling every room. All guests received group number 0, and $G$ was set to 1.

Ironically, the hotel can accept more guests even though every room is full.

• If $k$ ($k \geq 1$) people arrive at the hotel, then for each room number $x$, the guest in room $x$ moves to room $x+k$. The new guests then fill all rooms from 0 to $k-1$.
• If infinitely many people arrive at the hotel, then for each room number $x$, the guest in room $x$ moves to room $2x$. The new guests then fill all rooms with odd numbers.

You must write a program that processes the following queries.

• 1 k - If $k \geq 1$, then $k$ people arrive at the hotel. If $k = 0$, then infinitely many people arrive. Assign group number $G$ to the new guests, then increment $G$ by 1.
• 2 g x - Find the $x$-th smallest room number occupied by a guest with group number $g$. Output that value modulo $10^9 + 7$, followed by a newline.
• 3 x - Output the group number of the guest in room $x$, followed by a newline.

The first line contains an integer $Q$ ($1 \leq Q \leq 300\,000$), the number of queries. Each of the next $Q$ lines contains a query. All numbers in the queries are integers.

• For 1 k queries, $0 \leq k \leq 10^9$.
• For 2 g x queries, $g < G$, $1 \leq x \leq 10^9$, and at least $x$ guests have group number $g$.
• For 3 x queries, $0 \leq x \leq 10^9$.

Process all queries and output as required. It is guaranteed that the output is not empty.

If you know about cardinals, assume that "infinite" refers only to "countably infinite." If you do not, you do not have to worry about it.