CF1386B.Mixture

Serge, the chef of the famous restaurant "Salt, Pepper & Garlic" is trying to obtain his first Michelin star. He has been informed that a secret expert plans to visit his restaurant this evening.

Even though the expert's name hasn't been disclosed, Serge is certain he knows which dish from the menu will be ordered as well as what the taste preferences of the expert are. Namely, the expert requires an extremely precise proportion of salt, pepper and garlic powder in his dish.

Serge keeps a set of bottles with mixtures of salt, pepper and garlic powder on a special shelf in the kitchen. For each bottle, he knows the exact amount of each of the ingredients in kilograms. Serge can combine any number of bottled mixtures (or just use one of them directly) to get a mixture of particular proportions needed for a certain dish.

Luckily, the absolute amount of a mixture that needs to be added to a dish is so small that you can assume that the amounts in the bottles will always be sufficient. However, the numeric values describing the proportions may be quite large.

Serge would like to know whether it is possible to obtain the expert's favourite mixture from the available bottles, and if so—what is the smallest possible number of bottles needed to achieve that.

Furthermore, the set of bottles on the shelf may change over time as Serge receives new ones or lends his to other chefs. So he would like to answer this question after each such change.

For example, assume that expert's favorite mixture is $1:1:1$ and there are three bottles of mixtures on the shelf:

\\begin{array}{cccc} \\hline \\text{Mixture} & \\text{Salt} & \\text{Pepper} & \\text{Garlic powder} \\\\ \\hline 1 & 10 & 20 & 30 \\\\ 2 & 300 & 200 & 100 \\\\ 3 & 12 & 15 & 27 \\\\ \\hline \\end{array} $$ Amount of ingredient in the bottle, kg To obtain the desired mixture it is enough to use an equivalent amount of mixtures from bottles 1 and 2. If bottle 2 is removed, then it is no longer possible to obtain it. Write a program that helps Serge to solve this task! 著名餐厅“盐、胡椒与大蒜”（Salt, Pepper & Garlic）的主厨塞尔日（Serge）正努力争取他的第一颗米其林星级。他获知，一位神秘专家将于今晚造访他的餐厅。 尽管这位专家的真实姓名尚未透露，塞尔日却确信自己已知晓专家将点哪道菜品，以及其口味偏好：专家对菜品中盐、胡椒和大蒜粉三者的比例有着极为严苛的要求。 塞尔日在厨房的一处专用架子上摆放着若干瓶混合物，每瓶均含有盐、胡椒和大蒜粉。对于每一瓶，塞尔日都精确知晓其中每种成分的质量（单位：千克）。他可以通过任意组合若干瓶中的混合物（或直接单独使用其中一瓶），配制出某道菜品所需的特定比例的混合物。 幸运的是，实际需加入菜品的混合物总量极小，因此可假定各瓶中所含原料的量始终充足。但描述所需比例的数值可能非常大。 塞尔日希望知道：能否利用现有瓶装混合物配制出专家最钟爱的混合物？若可以，最少需要使用多少个瓶子？ 此外，架子上的瓶装混合物集合会随时间动态变化——例如，塞尔日会收到新瓶子，或把瓶子借给其他厨师。因此，他希望在每次此类变动后，都能快速回答上述问题。 例如，假设专家最钟爱的混合物比例为 $1:1:1$，而架子上当前有三瓶混合物： $$ \begin{array}{cccc} \hline \text{混合物} & \text{盐} & \text{胡椒} & \text{大蒜粉} \\ \hline 1 & 10 & 20 & 30 \\ 2 & 300 & 200 & 100 \\ 3 & 12 & 15 & 27 \\ \hline \end{array}

瓶中各成分的质量（单位：千克）

为获得目标混合物，只需取等质量的第1号瓶与第2号瓶中的混合物即可。若将第2号瓶移走，则无法再配制出该混合物。

请编写一个程序，帮助塞尔日解决这一任务！

The first row contains three non-negative integers $S_f$, $P_f$ and $G_f$ ($0 \leq S_f, P_f, G_f$; $0 \lt S_f+P_f+G_f \leq 10^6$) describing the amount of salt, pepper and garlic powder in the expert's favourite mixture. For any real $\alpha \gt 0$, $(\alpha{S_f}, \alpha{P_f}, \alpha{G_f})$ also is an expert's favourite mixture.

In the second row, there is a positive integer $N$ (number of changes on the shelf, $N \leq 100\,000$). You should assume that initially the shelf is empty.

Each of the next $N$ rows describes a single change on the shelf:

• If a new bottle is added, the row contains capital letter $A$ followed by three non-negative integers $S_i$, $P_i$ and $G_i$ ($0 \leq S_i, P_i, G_i$; $0 \lt S_i+P_i+G_i \leq 10^6$) describing the amount of salt, pepper and garlic powder in the added bottle. Added bottles are numbered consecutively by unique integers starting from $1$, that is, the $i$-th bottle corresponds to the $i$-th added bottle in the input data.
• If a particular bottle is removed from the shelf, the row contains capital letter $R$ followed by the integer—the bottle number $r_i$. All values $r_i$ in the removals are unique, $r_i$ never exceeds total number of bottles added thus far.

第一行包含三个非负整数 $S_f$、$P_f$ 和 $G_f$（满足 $0 \leq S_f, P_f, G_f$ 且 $0 \lt S_f+P_f+G_f \leq 10^6$），表示专家最喜爱的混合物中盐、胡椒和大蒜粉的含量。对于任意实数 $\alpha \gt 0$，$(\alpha{S_f}, \alpha{P_f}, \alpha{G_f})$ 同样构成专家最喜爱的混合物。

第二行是一个正整数 $N$（表示货架上发生的变更次数，$N \leq 100\,000$）。初始时货架为空。

接下来的 $N$ 行，每行描述一次货架上的变更：

• 若向货架添加一个新瓶子，则该行包含大写字母 $A$，后跟三个非负整数 $S_i$、$P_i$ 和 $G_i$（满足 $0 \leq S_i, P_i, G_i$ 且 $0 \lt S_i+P_i+G_i \leq 10^6$），分别表示该添加瓶子中盐、胡椒和大蒜粉的含量。添加的瓶子按输入顺序依次编号为从 $1$ 开始的唯一整数，即第 $i$ 个瓶子对应输入数据中第 $i$ 次添加操作所对应的瓶子。
• 若从货架上移除某个特定瓶子，则该行包含大写字母 $R$，后跟一个整数——瓶子编号 $r_i$。所有移除操作中的 $r_i$ 均互不相同，且 $r_i$ 不会超过截至目前已添加的瓶子总数。

Output $N$ rows. The $j$-th row ($1 \leq j \leq N$) should contain the number $x_j$, the smallest number of bottles needed to prepare a mixture with the expert's favourite proportions of salt, pepper and garlic powder using the bottles available after the first $j$ changes on the shelf, or $0$ if it is not possible.

输出 $N$ 行。第 $j$ 行（$1 \leq j \leq N$）应包含数值 $x_j$，即在货架完成前 $j$ 次更改后，利用当前可用的瓶子配制出专家最喜爱的盐、胡椒与蒜粉比例混合物所需的最少瓶子数量；若无法配制，则输出 $0$。

Pay attention that in the example, bottles $1$ and $3$ contain the same proportions of salt, pepper and garlic powder.

请注意，在示例中，瓶子 $1$ 和 $3$ 中盐、胡椒粉和大蒜粉的比例相同。