힐베르트 호텔

힐베르트 호텔에는 0, 1, 2, $\cdots$번 방이 무한히 있다. 각 방에는 최대 한 명의 손님이 묵는다. 사람들은 보통 단체로 체크인하는 경향이 있어서, 호텔에는 단체 번호를 관리하는 변수 $G$가 있다.

힐베르트 호텔은 오늘 개업했다. 곧바로 무한히 많은 사람이 한꺼번에 도착해 호텔의 모든 방이 찼다. 모든 손님은 단체 번호 0을 받았고, $G$는 1로 설정되었다.

아이러니하게도 모든 방이 찼는데도 호텔은 손님을 더 받을 수 있다.

• $k$ ($k \geq 1$)명의 사람이 호텔에 도착하면, 각 방 번호 $x$에 대해 $x$번 방의 손님이 $x+k$번 방으로 옮긴다. 그 뒤 새로 온 손님들이 0번부터 $k-1$번 방을 모두 채운다.
• 무한히 많은 사람이 호텔에 도착하면, 각 방 번호 $x$에 대해 $x$번 방의 손님이 $2x$번 방으로 옮긴다. 그 뒤 새로 온 손님들이 홀수 번호 방을 모두 채운다.

다음 질의를 처리하는 프로그램을 작성해야 한다.

• 1 k - $k \geq 1$이면 $k$명의 사람이 호텔에 도착한다. $k = 0$이면 무한히 많은 사람이 도착한다. 새로 온 손님들에게 단체 번호 $G$를 부여하고, $G$를 1 증가시킨다.
• 2 g x - 단체 번호 $g$인 손님이 묵는 방 번호 중 $x$번째로 작은 것을 찾는다. 그 값을 $10^9 + 7$로 나눈 나머지를 출력하고 줄바꿈한다.
• 3 x - $x$번 방에 묵는 손님의 단체 번호를 출력하고 줄바꿈한다.

첫째 줄에 질의의 수를 나타내는 정수 $Q$ ($1 \leq Q \leq 300\,000$)가 주어진다. 다음 $Q$개 줄에 각각 질의가 주어진다. 질의에 나오는 모든 수는 정수다.

• 1 k 질의에서 $0 \leq k \leq 10^9$이다.
• 2 g x 질의에서 $g < G$이고 $1 \leq x \leq 10^9$이며, 단체 번호 $g$인 손님이 $x$명 이상 있다.
• 3 x 질의에서 $0 \leq x \leq 10^9$이다.

모든 질의를 처리하고 요구대로 출력한다. 출력이 비어 있지 않음이 보장된다.

"기수"에 대해 알고 있다면 "무한"은 "가산 무한"만을 가리킨다고 가정하자. 모른다면 걱정할 필요 없다.