你是 Linetopia 的居民，这里有 $n$ 个主要城市，它们等距分布在一条东西向的直线上。事实上，它们通常按顺序编号为 $1$ 到 $n$，其中 $1$ 是最西端的城市，$n$ 是最东端的城市。在邻近的 Trapez 军队入侵之前，Linetopia 是一个宜居的美好地方。作为 Linetopia“守护生命与保护公民”倡议的一部分，你被召集来处理有关 Trapez 军队动向的信息，以便我们确定哪些城市受到的打击最严重，并知道该向何处派遣增援部队。

Linetopia 情报部门发现，Trapez 军队的攻击模式如下：他们派遣大型飞机在 Linetopia 的城市上空投放部队。每架飞机从某个城市 $i$ 开始，投放 $s$ 名士兵。随后，飞机向东或向西飞行。每飞过另一个城市，它投放的士兵数量就比上一个经过的城市多 $a$ 名。在完成 $d$ 次投放后，飞机返回 Trapez 进行补给。

你将收到情报更新，告知你每架经过 Linetopia 上空的 Trapez 飞机的规格。你需要回答询问特定城市被投放了多少 Trapez 士兵的查询。你准备好迎接挑战了吗？

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。每个测试用例的第一行包含两个整数：$m$ ($1 \le m \le 10,000$)，表示更新和查询的总数；$n$ ($1 \le n \le 500,000$)，表示 Linetopia 的城市数量。

接下来的 $m$ 行输入要么是更新，要么是查询。更新行以大写字母 U 开头，然后包含一个大写字母 E（东）或 W（西）以指示方向，接着包含四个整数 $i$ ($1 \le i \le n$)、$s$ ($1 \le s \le 10,000$)、$a$ ($0 \le a \le 10,000$) 和 $d$ ($1 \le d \le n$)。这些整数分别表示起始城市、起始士兵数量、每个城市增加的士兵数量以及投放次数。你可以假设 $d$ 永远不会导致飞机飞到城市 $1$ 的西侧或城市 $n$ 的东侧。

查询行以大写字母 Q 开头，然后包含一个整数 $i$ ($1 \le i \le n$)，表示被查询的城市。

输出格式

对于输入中的每个查询，输出一行，包含在该城市投放的 Trapez 士兵数量。

样例

输入 1

1
8 3
U E 1 5 2 3
Q 1
Q 2
Q 3
U W 3 10 10 2
Q 1
Q 2
Q 3

输出 1

5
7
9
5
27
19

说明

两架飞机飞过 Linetopia。第一架从城市 $1$ 开始向东飞行。它在城市 $1$ 投放了 $5$ 名士兵，在城市 $2$ 投放了 $7$ 名士兵，在城市 $3$ 投放了 $9$ 名士兵。第二架从城市 $3$ 开始向西飞行。它在城市 $3$ 投放了 $10$ 名士兵，在城市 $2$ 投放了 $20$ 名士兵。