Zhang Hua was admitted to Peking University; Li Ping entered a technical school; Little E is moving bricks at a construction site: they all have bright futures.

Friendly reminder: Please do not imitate Little E's way of moving bricks, as it is very tiring.

To move bricks happily, Little E has a special method.

Suppose there are $n$ stacks of bricks in front of him. In one hour, he will remove $d$ bricks from the top of every stack, where $d$ is Little E's current energy level. If a stack has fewer than $d$ bricks, Little E will remove all the remaining bricks in that stack.

After working for an hour, if Little E finds that he has finished at least one stack of bricks, he will feel happy and continue to work for another hour. However, because part of the work is completed, Little E may become complacent, causing his energy level to decrease. Specifically, each stack of bricks has an attribute $b$; when Little E finishes that stack, his energy level decreases by $b$.

If no stack of bricks is finished, Little E will stop working. If his energy level drops to $0$ or below, Little E will also stop working. If Little E finds that he needs to work but all bricks have already been moved, he will spend the hour in another way, but this hour still counts as Little E's working time.

Bricks at the construction site are constantly increasing. Given that Little E's initial energy level is $d$, how many hours can he work continuously?

Input

The first line contains a positive integer $T$, representing the total number of events.

The next $T$ lines each contain several integers, where the first integer $op$ represents the event type.

If $op=1$, it is followed by two integers $a$ and $b$, representing that a new stack of bricks has been added, with $a$ bricks, and Little E's energy level will decrease by $b$ after finishing this stack.

If $op=2$, it is followed by a positive integer $d$, asking how many hours Little E can work continuously if his initial energy level is $d$.

Note that the $op=2$ operation does not change the number of bricks in any stack.

Output

For each query, output one integer per line representing the answer.

Examples

Input 1

5
1 6 1
1 3 0
1 9 2
2 3
2 4

Output 1

3
4

Note 1

For the first query: Initially, there are $3$ stacks of bricks with quantities $(6, 3, 9)$, and Little E's initial energy is $3$. In the first hour, Little E removes $3$ bricks from each stack, and the quantities become $(3, 0, 6)$. The second stack is finished, so Little E's energy decreases by $0$, and he continues to work for another hour. In the second hour, Little E removes $3$ bricks from each stack, and the quantities become $(0, 0, 3)$. The first stack is finished, so Little E's energy decreases by $1$, and he continues to work for another hour. In the third hour, Little E removes $2$ bricks from each stack, and the quantities become $(0, 0, 1)$. Since no new stack of bricks is finished, Little E stops working.

For the second query: Initially, there are $3$ stacks of bricks with quantities $(6, 3, 9)$, and Little E's initial energy is $4$. In the first hour, Little E removes $4$ bricks from each stack (the second stack only had $3$ bricks, so only $3$ were removed, and so on), and the quantities become $(2, 0, 5)$. The second stack is finished, so Little E's energy decreases by $0$, and he continues to work for another hour. In the second hour, Little E removes $4$ bricks from each stack, and the quantities become $(0, 0, 1)$. The first stack is finished, so Little E's energy decreases by $1$, and he continues to work for another hour. In the third hour, Little E removes $3$ bricks from each stack, and the quantities become $(0, 0, 0)$. The third stack is finished, so Little E's energy decreases by $2$, and he continues to work for another hour. In the fourth hour, Little E removes $1$ brick from each stack, but there are no bricks left; however, this hour still counts as Little E's working time. Since no new stack of bricks is finished, Little E stops working.

Input 2

4
1 2 1
2 2
1 2 1
2 2

Output 2

2
1

Note 2

For the first query: Initially, there is $1$ stack of bricks with quantity $2$, and Little E's initial energy is $2$. In the first hour, Little E removes $2$ bricks from the stack, and the quantity becomes $0$. The stack is finished, so Little E's energy decreases by $1$, and he continues to work for another hour. In the second hour, Little E removes $1$ brick from the stack, but there are no bricks left; however, this hour still counts as Little E's working time. Since no new stack of bricks is finished, Little E stops working.

For the second query: Initially, there are $2$ stacks of bricks with quantities $(2, 2)$, and Little E's initial energy is $2$. In the first hour, Little E removes $2$ bricks from each stack, and the quantities become $(0, 0)$. Both stacks are finished, so Little E's energy decreases by $1+1=2$. Since Little E's energy drops to $0$, he stops working.

Constraints

It is guaranteed that $T \le 351493$, $1 \le op \le 2$, $1 \le a \le 100000$, $0 \le b \le 100000$, $1 \le d \le 100000$.