著名餐厅“Salt, Pepper & Garlic”的主厨 Serge 正在努力获得他的第一颗米其林星。他被告知一位秘密专家计划今晚访问他的餐厅。
尽管专家的名字尚未透露,但 Serge 确信他知道会点菜单中的哪道菜以及专家的口味偏好。也就是说,专家要求他的菜肴中盐、胡椒粉和蒜粉的比例极其精确。
Serge 在厨房的一个特殊架子上放了一套装有盐、胡椒粉和大蒜粉混合物的瓶子。对于每一瓶,他都知道每种成分的确切数量(以千克为单位)。 Serge 可以组合任意数量的瓶装混合物(或直接使用其中之一),以获得特定菜肴所需的特定比例的混合物。
幸运的是,需要添加到菜肴中的混合物的绝对量非常小,因此您可以假设瓶子中的量始终是足够的。然而,描述比例的数值可能相当大。
Serge 想知道是否有可能从可用的瓶子中获得专家最喜欢的混合物,如果可以的话,实现这一目标所需的最少瓶子数量是多少。
此外,随着 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 \\ 3 & 12 & 15 & 27 \hline \end{array} $$$$$$ 瓶子中的成分量,千克
为了获得所需的混合物,使用瓶子 1 和 2 中等量的混合物就足够了。如果瓶子 2 被移除,则不再可能获得它。
编写一个程序来帮助 Serge 解决这个任务!
输入
第一行包含三个非负整数 $$$S_f$$$、$$$P_f$$$ 和 $$$G_f$$$ ($$$0 \leq S_f, P_f, G_f$$$; $$$0 < S_f+P_f+G_f \leq 10^6$$$) 描述专家最喜欢的盐、胡椒和大蒜粉的量混合物。对于任何真实的 $$$\alpha>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 < S_i+P_i+G_i \leq 10^6$$$) 描述添加的瓶子中盐、胡椒粉和大蒜粉的量。添加的瓶子由从$$$1$$$开始的唯一整数连续编号,即第$$$i$$$个瓶子对应于输入数据中第$$$i$$$个添加的瓶子。
- 如果从货架上移除特定瓶子,则该行包含大写字母 $$$R$$$ 后跟整数 - 瓶子编号 $$$r_i$$$。清除中的所有值 $$$r_i$$$ 都是唯一的,$$$r_i$$$ 从未超过迄今为止添加的瓶子总数。
输出
输出 $$$N$$$ 行。第 $$$j$$$ 行 ($$$1 \leq j \leq N$$$) 应包含数字 $$$x_j$$$,即使用货架上第一次 $$$j$$$ 更改后可用的瓶子制备具有专家最喜欢的盐、胡椒和大蒜粉比例的混合物所需的最小瓶子数量,或者如果不可能,则为 $$$0$$$。
示例
输入 #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
注意
评分:
子任务:
1. (13 分) $$$N \leq 50$$$, $$$0 < S_i+P_i+G_i \leq 10^2$$$
2. (17 分) $$$N \leq 500$$$, $$$0 < S_i+P_i+G_i \leq 10^3$$$
3. (30 分) $$$N \leq 5000$$$, $$$0 < S_i+P_i+G_i \leq 10^4$$$
4.(40分)没有进一步的限制
请注意,在示例中,$$$1$$$ 和 $$$3$$$ 瓶子中含有相同比例的盐、胡椒粉和大蒜粉。