题目描述

著名餐厅 Salt, Pepper & Garlic 的主厨 Serge 准备好成为一名米其林一星厨师。他已被告知，今晚一位秘密评审员将光临他的餐厅。

虽然他并没有得知这位评审员的姓名，但他已经得知了这位评审员将要点的菜和他的口味偏好。具体来说，这位评审员希望在菜肴中加入非常精确比例的盐，胡椒粉和大蒜粉。

Serge 在厨房的一个架子上放了若干盐，胡椒粉和大蒜粉的混合调料瓶。对于每种调料瓶，Serge 都知道该调料瓶中混合的盐，胡椒粉和大蒜粉的量（单位为千克），他可以通过将任意多瓶调料混合起来（当然也可以单独使用一瓶调料），得到所需比例的调料。

事实上菜肴里放的调料量并不多，因此可以认为调料的量是足够的。但是，评审员要求的盐，胡椒粉和大蒜粉的量之比中的数字可能非常大。

现在 Serge 想要求出，是否能够利用已有的调料瓶配制出满足评审员要求比例的调料？如果能够配制，最少需用多少个瓶子？

此外，Serge 可能会拿到新的调料瓶，或者将架子上已有的调料瓶给其他厨师，这意味着架子上的瓶子种类会不断发生改变，Serge 希望在每次架子上的调料瓶发生变化后，再解决上面的问题。

举个例子，假如评审员要求的盐，胡椒粉和大蒜粉的量的比例为 $1:1:1$，架子上有以下几种调料瓶：

则只需将瓶子 $1$ 中的全部调料，和瓶子 $2$ 中的 $60$ 千克调料（其中包括盐 $30$ 千克，胡椒粉 $20$ 千克，大蒜粉 $10$ 千克）混合即可满足要求。一旦取走瓶子 $2$，则无法满足评审员的要求。

输入格式

输入第一行包含三个整数 $S_f,P_f,G_f$，表示评审员要求的盐，胡椒粉，大蒜粉的量之比为 $S_f:P_f:G_f$，$\forall \alpha \gt 0$，$(\alpha S_f,\alpha P_f, \alpha G_f)$ 的混合调料也满足评审员要求。

下一行一个整数 $N$，表示架子上的瓶子要进行 $N$ 次变动。最开始架子上没有瓶子。

接下来 $N$ 行，每行描述一次变动。

• 若架子上新增了瓶子，则该行包含一个大写字母 A 和三个整数 $S_i,P_i,G_i$，分别代表该瓶中盐，胡椒粉，大蒜粉的量。瓶子按加入的先后顺序从 $1$ 开始编号，即如果该瓶子是第 $i$ 个加入架子的，则其编号为 $i$。
• 若架子上移除了瓶子，则该行包含一个大写字母 R 和一个整数 $r_i$，代表移除的瓶子编号。保证该编号的瓶子在架子上。

输出格式

输出 $N$ 行。第 $i$ 行输出在第 $i$ 次变动后，满足评审员要求所需的最少瓶子数量。特别地，若不存在一种方案满足评审员的要求，输出 $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

提示

所有数据均满足：$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$。

• 子任务 1（13 分）：$N \leq 50$，$0 \lt S_i+P_i+G_i \leq 10^2$；
• 子任务 2（17 分）：$N \leq 500$，$0 \lt S_i+P_i+G_i \leq 10^3$；
• 子任务 3（30 分）：$N \leq 5000$，$0 \lt S_i+P_i+G_i \leq 10^4$；
• 子任务 4（40 分）：无特殊限制。