Background

Zhang Hua got into Peking University; Li Ping entered a secondary technical school; Little E carries bricks on a construction site: they all have a bright future.

Problem Description

Friendly reminder: Please do not imitate Little E’s way of carrying bricks; it is very tiring.

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

Suppose there are $n$ stacks of bricks in front of him. Within one hour, he will carry away the top $d$ bricks from each stack. Here, $d$ is Little E’s current energy value. If a stack has fewer than $d$ bricks, Little E will carry away all remaining bricks in that stack.

After Little E finishes one hour of work, if he finds that he has emptied at least one stack of bricks, he will feel happy and continue working for another hour; however, since part of the work has been completed, Little E may become lazy, causing his energy value to decrease. Specifically, each stack has an attribute $b$. When Little E empties that stack, his energy value decreases by $b$.

If no stack is emptied, Little E will stop working. If his energy value 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 carried away, he will spend this hour doing something else, but this hour is still counted as Little E’s working time.

Bricks on the construction site keep being added. Given that Little E’s initial energy value is $d$, how many consecutive hours can he work?

Input Format

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

In the next $T$ lines, each line contains several integers, where the first integer is $op$, indicating the event type.

If $op=1$, it is followed by two integers $a,b$, meaning a new stack of bricks is added. The stack has $a$ bricks, and after it is emptied, Little E’s energy value will decrease by $b$.

If $op=2$, it is followed by a positive integer $d$, asking: if Little E’s initial energy value is $d$, how many consecutive hours can he work?

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

Output Format

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

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

3
4

4
1 2 1
2 2
1 2 1
2 2

2
1

Hint

[Sample Explanation]

First query:

Initially there are $3$ stacks of bricks, with quantities $(6,3,9)$. Little E’s initial energy is $3$.

In the first hour, Little E carries $3$ bricks from each stack, and the quantities become $(3,0,6)$. The second stack is emptied, so Little E’s energy decreases by $0$, and he continues working for another hour.

In the second hour, Little E carries $3$ bricks from each stack, and the quantities become $(0,0,3)$. The first stack is emptied, so Little E’s energy decreases by $1$, and he continues working for another hour.

In the third hour, Little E carries $2$ bricks from each stack, and the quantities become $(0,0,1)$. Since no new stack is emptied, Little E stops working.

Second query:

Initially there are $3$ stacks of bricks, with quantities $(6,3,9)$. Little E’s initial energy is $4$.

In the first hour, Little E carries $4$ bricks from each stack (the second stack has only $3$ bricks so he carries only $3$ bricks; the same is omitted below), and the quantities become $(2,0,5)$. The second stack is emptied, so Little E’s energy decreases by $0$, and he continues working for another hour.

In the second hour, Little E carries $4$ bricks from each stack, and the quantities become $(0,0,1)$. The first stack is emptied, so Little E’s energy decreases by $1$, and he continues working for another hour.

In the third hour, Little E carries $3$ bricks from each stack, and the quantities become $(0,0,0)$. The third stack is emptied, so Little E’s energy decreases by $2$, and he continues working for another hour.

In the fourth hour, Little E carries $1$ brick from each stack, but in fact there are no bricks at this time. However, this hour is still counted as Little E’s working time. Since no new stack is emptied, Little E stops working.

[Sample Explanation 2]

First query:

Initially there is $1$ stack of bricks, with quantity $2$. Little E’s initial energy is $2$.

In the first hour, Little E carries $2$ bricks from the stack, and the quantity becomes $0$. This stack is emptied, so Little E’s energy decreases by $1$, and he continues working for another hour.

In the second hour, Little E carries $1$ brick from the stack, but in fact there are no bricks at this time. However, this hour is still counted as Little E’s working time. Since no new stack is emptied, Little E stops working.

Second query:

Initially there are $2$ stacks of bricks, with quantities $(2,2)$. Little E’s initial energy is $2$.

In the first hour, Little E carries $2$ bricks from each stack, and the quantities become $(0,0)$. Both stacks are emptied, 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$.

Translated by ChatGPT 5