Mixture

题意翻译

著名餐厅 *Salt, Pepper & Garlic* 的主厨 Serge 准备好获得第一颗米其林星。他已被告知，今晚一位秘密评审员将光临他的餐厅。 虽然他并没有得知这位评审员的姓名，但他已经得知了这位评审员将要点的菜和他的口味偏好。具体来说，这位评审员希望在菜肴中加入非常精确比例的盐，胡椒粉和大蒜粉。 Serge 在厨房的一个架子上放了若干盐，胡椒粉和大蒜粉的混合调料瓶。对于每种调料瓶，Serge 都知道该调料瓶中混合的盐，胡椒粉和大蒜粉的量（单位为千克），他可以通过将任意多瓶调料混合起来（当然也可以单独使用一瓶调料），得到所需比例的调料。 事实上菜肴里放的调料量并不多，因此可以认为调料的量是足够的。但是，评审员要求的盐，胡椒粉和大蒜粉的量之比中的数字可能非常大。 现在 Serge 想要求出，是否能够利用已有的调料瓶配制出满足评审员要求比例的调料？如果能够配制，最少需用多少个瓶子？ 此外，Serge 可能会拿到新的调料瓶，或者将架子上已有的调料瓶给其他厨师，这意味着架子上的瓶子种类会不断发生改变，Serge 希望在每次架子上的调料瓶发生变化后，再解决上面的问题。

题目描述

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!

输入输出格式

输入格式

The first row contains three non-negative integers $ S_f $ , $ P_f $ and $ G_f $ ( $ 0 \leq S_f, P_f, G_f $ ; $ 0 < 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>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 < 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.

输出格式

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. Scoring Subtasks: 1. (13 points) $ N \leq 50 $ , $ 0 < S_i+P_i+G_i \leq 10^2 $ 2. (17 points) $ N \leq 500 $ , $ 0 < S_i+P_i+G_i \leq 10^3 $ 3. (30 points) $ N \leq 5000 $ , $ 0 < S_i+P_i+G_i \leq 10^4 $ 4. (40 points) No further constraints

输入输出样例

输入样例 #1

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

输出样例 #1

0
2
0
2
1
1

说明

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