CF1386B Mixture

著名餐厅 “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 \\ \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$ 均唯一，且不会超过当前已添加瓶子的总数。

输出 $N$ 行。第 $j$ 行（$1 \leq j \leq N$）输出一个整数 $x_j$，表示在第 $j$ 次变化后，最少需要多少瓶才能配出专家喜欢的混合物比例；如果无法配出，输出 $0$。

注意，在示例中，瓶 1 和瓶 3 含有相同的盐、胡椒和大蒜粉比例。 由 ChatGPT 4.1 翻译