著名餐厅“盐、胡椒与大蒜”的主厨塞尔日（Serge）正努力争取他的第一颗米其林星。他获悉，一位神秘的专家计划今晚光顾他的餐厅。

尽管专家的身份尚未公开，但塞尔日确信他知道专家会点菜单上的哪道菜，也知道专家的口味偏好。具体来说，专家要求菜肴中盐、胡椒和大蒜粉的比例极其精确。

塞尔日厨房的架子上放着一套装有盐、胡椒和大蒜粉混合物的瓶子。对于每一瓶，他都知道其中每种成分的精确重量（以千克为单位）。塞尔日可以组合任意数量的瓶装混合物（或者直接使用其中一瓶）来获得特定菜肴所需的特定比例的混合物。

幸运的是，菜肴中需要添加的混合物总量非常小，因此你可以假设瓶中的量总是充足的。然而，描述比例的数值可能非常大。

塞尔日想知道是否可以利用现有的瓶子获得专家喜爱的混合物，如果可以，实现这一目标所需的最少瓶数是多少。

此外，架子上的瓶子集合会随时间变化，因为塞尔日会收到新的瓶子或将自己的瓶子借给其他厨师。因此，他希望在每次变动后都能回答这个问题。

例如，假设专家喜爱的混合物比例为 $1 : 1 : 1$，架子上有三瓶混合物（表 1）：

表 1：架子上的瓶子

要获得所需的混合物，只需使用来自瓶子 1 和瓶子 2 的等量混合物即可。如果移除了瓶子 2，则无法再获得该混合物。

请编写一个程序来帮助塞尔日解决这个问题！

输入格式

第一行包含三个非负整数 $S_f, P_f$ 和 $G_f$ ($0 \le S_f, P_f, G_f$；$0 < S_f + P_f + G_f \le 10^6$)，描述专家喜爱的混合物中盐、胡椒和大蒜粉的含量。对于任何实数 $\alpha > 0$，$(\alpha S_f, \alpha P_f, \alpha G_f)$ 也是专家喜爱的混合物。

第二行包含一个正整数 $N$（架子上的变动次数，$N \le 100\,000$）。你应该假设架子最初是空的。

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

• 如果添加了一个新瓶子，该行包含大写字母 $A$，后跟三个非负整数 $S_i, P_i$ 和 $G_i$ ($0 \le S_i, P_i, G_i$；$0 < S_i + P_i + G_i \le 10^6$)，描述添加的瓶子中盐、胡椒和大蒜粉的含量。添加的瓶子按从 1 开始的唯一整数依次编号，即第 $i$ 个瓶子对应输入数据中第 $i$ 个添加的瓶子。
• 如果从架子上移除了某个特定的瓶子，该行包含大写字母 $R$，后跟整数 $r_i$（瓶子编号）。所有移除操作中的 $r_i$ 值都是唯一的，$r_i$ 永远不会超过目前为止添加的瓶子总数。

输出格式

输出 $N$ 行。第 $j$ 行 ($1 \le j \le 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 和瓶子 3 含有相同比例的盐、胡椒和大蒜粉。

子任务

1. (13 分) $N \le 50, 0 < S_i + P_i + G_i \le 10^2$
2. (17 分) $N \le 500, 0 < S_i + P_i + G_i \le 10^3$
3. (30 分) $N \le 5000, 0 < S_i + P_i + G_i \le 10^4$
4. (40 分) 无其他限制