Description

The head chef Serge of the famous restaurant Salt, Pepper & Garlic is ready to become a Michelin one-star chef. He has been told that tonight a secret judge will visit his restaurant.

Although he does not know the judge's name, he does know what dish the judge will order and the judge's taste preferences. Specifically, the judge wants the dish to contain salt, pepper powder, and garlic powder in a very precise ratio.

On a shelf in the kitchen, Serge has several bottles of mixed spices containing salt, pepper powder, and garlic powder. For each bottle, Serge knows the amounts of salt, pepper powder, and garlic powder in the mixture (in kilograms). By mixing spices from any number of bottles (and of course he may also use just one bottle), he can obtain spices in the required ratio.

In fact, not much spice is used in the dish, so we can assume the available amounts are sufficient. However, the numbers in the ratio of salt, pepper powder, and garlic powder required by the judge may be very large.

Now Serge wants to determine whether he can use the existing bottles to prepare a mixture that matches the judge's required ratio. If he can, what is the minimum number of bottles needed?

In addition, Serge may receive new bottles, or give existing bottles on the shelf to other chefs, meaning the set of bottles on the shelf will keep changing. Serge wants to solve the above problem after each change to the shelf.

For example, suppose the judge requires the ratio of salt, pepper powder, and garlic powder to be $1:1:1$, and the shelf contains the following bottles:

Then it is enough to mix all spices from bottle $1$ and $60$ kg of spices from bottle $2$ (which includes $30$ kg of salt, $20$ kg of pepper powder, and $10$ kg of garlic powder) to meet the requirement. Once bottle $2$ is removed, it becomes impossible to satisfy the judge's requirement.

Input Format

The first line contains three integers $S_f,P_f,G_f$, meaning the ratio of salt, pepper powder, and garlic powder required by the judge is $S_f:P_f:G_f$. For all $\alpha \gt 0$, the mixture $(\alpha S_f,\alpha P_f, \alpha G_f)$ also satisfies the judge's requirement.

The next line contains an integer $N$, meaning there will be $N$ changes to the bottles on the shelf. Initially, there are no bottles on the shelf.

The next $N$ lines each describe one change.

• If a bottle is added to the shelf, the line contains an uppercase letter A and three integers $S_i,P_i,G_i$, representing the amounts of salt, pepper powder, and garlic powder in that bottle. Bottles are numbered starting from $1$ in the order they are added; that is, if this bottle is the $i$-th bottle added to the shelf, then its ID is $i$.
• If a bottle is removed from the shelf, the line contains an uppercase letter R and an integer $r_i$, representing the ID of the bottle to remove. It is guaranteed that the bottle with this ID is on the shelf.

Output Format

Output $N$ lines. On the $i$-th line, output the minimum number of bottles needed to satisfy the judge's requirement after the $i$-th change. In particular, if there is no way to satisfy the judge's requirement, output $0$.

1 2 3
6
A 5 6 7
A 3 10 17
R 1
A 15 18 21
A 5 10 15
R 3

0
2
0
2
1
1

Hint

All testdata satisfy: $1 \leq N \leq 10^5$, $S_f,P_f,G_f \geq 0$, $0 \lt S_f+P_f+G_f \leq 10^6$, $S_i,P_i,G_i \geq 0$, $0 \lt S_i+P_i+G_i \leq 10^6$.

• Subtask 1 (13 points): $N \leq 50$, $0 \lt S_i+P_i+G_i \leq 10^2$.
• Subtask 2 (17 points): $N \leq 500$, $0 \lt S_i+P_i+G_i \leq 10^3$.
• Subtask 3 (30 points): $N \leq 5000$, $0 \lt S_i+P_i+G_i \leq 10^4$.
• Subtask 4 (40 points): No special constraints.

Translated by ChatGPT 5