希尔伯特旅馆拥有无穷多个房间，编号为 $0, 1, 2, \dots$。每个房间最多容纳一名客人。由于人们倾向于成群结队地办理入住，旅馆设有一个团体计数变量 $G$。

希尔伯特旅馆今天盛大开业。不久之后，无穷多的人同时到达，填满了旅馆的每一个房间。所有客人的团体编号均为 $0$，且 $G$ 被设为 $1$。

具有讽刺意味的是，即使每个房间都已住满，旅馆仍然可以接纳更多的客人：

• 如果有 $k$ ($k \ge 1$) 个人到达旅馆，那么对于每个房间号 $x$，原先在房间 $x$ 的客人会移动到房间 $x + k$。此后，新来的客人会填满从 $0$ 到 $k - 1$ 的所有房间。
• 如果有无穷多的人到达旅馆，那么对于每个房间号 $x$，原先在房间 $x$ 的客人会移动到房间 $2x$。此后，新来的客人会填满所有编号为奇数的房间。

你需要编写一个程序来处理以下查询：

• 1 k - 如果 $k \ge 1$，则有 $k$ 个人到达旅馆。如果 $k = 0$，则有无穷多的人到达旅馆。将团体编号 $G$ 分配给这些新客人，然后将 $G$ 增加 $1$。
• 2 g x - 找到包含团体编号为 $g$ 的客人的第 $x$ 小的房间号。输出其对 $10^9 + 7$ 取模的结果，并换行。
• 3 x - 输出房间 $x$ 中客人的团体编号，并换行。

输入格式

第一行包含一个整数 $Q$ ($1 \le Q \le 300,000$)，表示查询的数量。接下来的每一行包含一个查询。查询中的所有数字均为整数。

• 对于 1 k 查询，$0 \le k \le 10^9$。
• 对于 2 g x 查询，$g < G$，$1 \le x \le 10^9$，且保证至少有 $x$ 名客人的团体编号为 $g$。
• 对于 3 x 查询，$0 \le x \le 10^9$。

输出格式

处理所有查询并按要求输出。保证输出不为空。

样例

输入 1

10
3 0
1 3
2 1 2
1 0
3 10
2 2 5
1 5
1 0
3 5
2 3 3

输出 1

0
1
0
9
4
4

说明

如果你了解“基数”的概念，请假设“无穷”仅指“可数无穷”。如果你不了解这个概念，则不必担心。