— 冷静一点……

我们有一个位于 $X$ 轴上的球，初始位置在坐标 $0$ 处。我们还有 $N$ 组位于 $X$ 轴上的墙。每组墙由一个元组 $(dir, len, freq)$ 描述，其中：

• $dir$ 表示墙放置的方向，可以是 L（左）或 R（右）。
• 如果 $dir=$ L，则该组墙放置在 $-len, -2 \cdot len, -3 \cdot len, \dots, -freq \cdot len$ 处。
• 如果 $dir=$ R，则该组墙放置在 $len, 2 \cdot len, 3 \cdot len, \dots, freq \cdot len$ 处。

注意，根据这些信息，多个墙可能位于同一个坐标上。

在时间 $T=0$ 时，球开始以每秒一个单位的速度向右移动。当球撞到一堵墙时，该墙会被自动摧毁，且球会反转运动方向。如果同一坐标处有多堵墙，则只有其中一堵会被摧毁。

任务

给定 $Q$ 次询问。对于每次询问，给定一个整数 $T$。输出 $T$ 秒后球的坐标。

输入格式

第一行包含两个整数 $N$ 和 $Q$，中间用空格分隔。

接下来的 $N$ 行，每行包含三个由空格分隔的参数 $dir, len, freq$，描述墙的放置方式。

接下来的 $Q$ 行，每行包含一个整数 $T$，描述一次询问。

输出格式

输出 $Q$ 行，第 $i$ 行应包含第 $i$ 次询问的答案。

数据范围与约定

• $1 \leq N, Q \leq 250 \ 000$
• $1 \leq T \leq 10^{12}$
• $dir \in \{$L$,$ R$\}$
• $1 \leq len, freq \leq 10^{12}$

样例

输入格式 1

3 12
R 3 2
R 6 1
L 3 2
0
1
2
3
4
5
6
7
17
18
19
200

输出格式 1

0
1
2
3
2
1
0
-1
5
6
5
-152