题目描述

题目译自 Romanian Master of Informatics 2023 Day1 T3 「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}$

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