每年春天，猎魔人 Gebyte 都会踏上他的旅程，计划在磨练猎魔技艺的同时赚取一些钱财。小径从西向东延伸，全长 $n$ 英里；每一英里都有三种物体之一在等待着他：

• $B\ b_i$：凶猛野兽的巢穴，在当地农民中令人闻风丧胆。当 Gebyte 踏入巢穴时，里面的野兽会立即攻击他，使猎魔人受伤。如果 Gebyte 在第一次攻击中幸存下来，他会迅速拔出银剑并杀死野兽。结果，Gebyte 的生命值变化如下： 如果 $H \leqslant b_i$，则 $death$，否则 $H := H - b_i$。

• $K\ k_i$：当地的一家旅店，Gebyte（以贪杯闻名）一定会去光顾。如果他待在旅店时生命值低于 $k_i$，由于多喝了一桶酒，他会在黎明前死去。否则，带着严重的宿醉，生命值降至 $k_i$，他继续他的旅程。Gebyte 的生命值变化如下： 如果 $H < k_i$，则 $death$，否则 $H := k_i$。

• $C\ c_i$：一位强大女巫的住所，她的魔法和药水可以治愈伤口并消除宿醉。如果 Gebyte 在生命值低于 $c_i$ 时遇见女巫，通过女巫的咒语和药剂，他的生命值会提升至 $c_i$。Gebyte 的生命值变化如下： $H := \max(H, c_i)$。

现在，猎魔人想知道他应该游历小径的哪一部分，这样他既能享受乐趣又能保住性命。日子一天天过去，第 $i$ 天会发生两件事之一：

• 小径上的某个物体发生了变化，例如女巫的房子被当地商人买下并改成了旅店，或者一只新野兽从地下爬出，烧毁了一家旅店并在原址建了一个巢穴；
• Gebyte 走出家门，坐在树下思考：如果他从第 $l_i$ 个物体开始他的旅程，并向东行进，他能在不丧命的情况下走多远？这些问题超出了普通猎魔人的能力范围，因此他请求你——一位以神秘编程魔法闻名的术士——来回答它们。

请注意，猎魔人只是在思考该怎么做，而并没有真正踏上旅程，因此虽然对小径的改变是永久的，但 Gebyte 的每一个问题都是独立的，且在每次询问中他的初始生命值都等于 $H$。

输入格式

第一行包含测试用例的数量 $z$ ($1 \leqslant z \leqslant 100\,000$)。接下来是各测试用例的描述。 每个测试用例的第一行包含三个整数 $n, q$ 和 $H$ ($1 \leqslant n \leqslant 2\,000\,000, 1 \leqslant q \leqslant 4\,000\,000, 1 \leqslant H \leqslant 10^{12}$) —— 小径长度、天数和 Gebyte 的初始生命值。 接下来的 $n$ 行描述了小径的初始状态；第 $i$ 行包含一个字母，表示第 $i$ 个物体的类型（$B, K$ 或 $C$），以及一个整数（$b_i, k_i$ 或 $c_i$；$1 \leqslant b_i, k_i, c_i \leqslant 10^{12}$），含义如前所述。 接下来的 $q$ 行描述了随后的日子。第 $i$ 行以字母 $Z$ 开头（如果第 $i$ 天小径发生了变化），或者以 $D$ 开头（如果 Gebyte 想象了另一段旅程）。 如果是小径变化，该行的其余部分包含：一个整数 $x_i$ ($1 \leqslant x_i \leqslant n$)，表示发生变化的物体索引，后跟一个字母和一个整数，格式与初始状态描述相同，表示新物体。如果是 Gebyte 想象的旅程，该行包含一个整数 $l_i$ ($1 \leqslant l_i \leqslant n$)，表示旅程应开始的物体索引。 所有小径的总长度不超过 $2\,000\,000$，总天数不超过 $4\,000\,000$。

输出格式

对于每个测试用例，按输入顺序输出 Gebyte 所有问题的答案。对于每个问题，输出一个整数，表示 Gebyte 可以到达（并幸存）的最远物体索引 $r_i$ ($l_i \leqslant r_i \leqslant n$)，如果他会在第 $l_i$ 个物体处被杀死，则输出 $-1$。第 $i$ 天提出的问题的答案应考虑之前所有对小径的更改。

样例

样例输入 1

1
4 12 10
C 10
B 5
K 5
B 6
Z 3 K 6
Z 1 C 11
D 2
D 1
Z 3 C 1
D 3
Z 3 B 20
D 3
Z 1 C 31
D 1
Z 4 K 6
D 1

样例输出 1

2
3
4
-1
3
4

说明

小径发生了六次变化，方式如下： $[C\ 10, B\ 5, K\ 5, B\ 6]$（初始状态） $[C\ 10, B\ 5, K\ 6, B\ 6]$（第 1 天） $[C\ 11, B\ 5, K\ 6, B\ 6]$（第 2 天） $[C\ 11, B\ 5, C\ 1, B\ 6]$（第 5 天） $[C\ 11, B\ 5, B\ 20, B\ 6]$（第 7 天） $[C\ 31, B\ 5, B\ 20, B\ 6]$（第 9 天） * $[C\ 31, B\ 5, B\ 20, K\ 6]$（第 11 天）

在剩下的六天里，Gebyte 想象了各种旅程。 在第三天，Gebyte 从第二个物体开始。在杀死野兽后，他剩下 5 点生命值——不足以在下一个物体（旅店 $K\ 6$）中幸存。因此，Gebyte 能到达的最远物体是第二个。 在第四天，Gebyte 从第一个物体开始；多亏了女巫，他获得了额外的 1 点生命值，并幸存于第三个物体（旅店），但在最后一个物体（野兽）处失败了。 在第六天，Gebyte 从第三个物体开始，现在是女巫 $C\ 1$。在生命值不变的情况下，他继续前进并杀死了野兽，这是小径上的最后一个物体。 在第八天，Gebyte 从野兽 $B\ 20$ 开始，他无法击败它，所以答案是 $-1$。 在第十天，Gebyte 从强大的 $C\ 31$ 开始，多亏了它，他击败了前两只野兽，在最后一个物体处失败。 在最后一天，Gebyte 成功走完了整条小径。