题目描述
题目译自 Romanian Master of Informatics $2023$ Day$1$ T$3$ 「Pinball」

—— 大家稍微冷静一下……

想象一个球，它静静地躺在 $X$ 轴上，初始位置是坐标 $0$。与此同时，$X$ 轴上分布着 $N$ 组墙壁。每组墙壁可以用一个三元组 $(dir, len, freq)$ 来描述：

• $dir$ 表示墙壁的摆放方向，可以是 $\texttt{L}$（向左）或 $\texttt{R}$（向右）。
• 如果 $dir=\texttt{L}$，那么这组墙壁会出现在位置 $-len$, $-2 \cdot len$, $-3 \cdot len$, $\ldots$, $-freq \cdot len$。
• 如果 $dir=\texttt{R}$，那么这组墙壁会出现在位置 $len$, $2 \cdot len$, $3 \cdot len$, $\ldots$, $freq \cdot len$。

需要注意的是，由于这些信息的特性，同一个坐标上可能会同时存在多堵墙。

在时间 $T=0$ 时，球开始以每秒一单位的速度向右移动。每当球撞上一堵墙，那堵墙就会立刻被撞毁，同时球会掉头反向移动。如果某个坐标有多堵墙，球撞击时只会毁掉其中一堵。

现在给你 $Q$ 个问题。每个问题会给出一个整数 $T$，请你算出经过 $T$ 秒后，球所在的坐标是多少。

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

接下来的 $N$ 行，每行有三个用空格分隔的整数 $dir$, $len$, $freq$，描述一组墙壁的摆放方式。

再接下来的 $Q$ 行，每行有一个整数 $T$，表示一个询问。

输出格式
输出 $Q$ 行，第 $i$ 行给出第 $i$ 个询问的答案。

样例

输入

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

输出

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

数据范围与提示
对于所有输入数据，满足：

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

详细子任务附加限制及分值如下表所示。