P12616 [RMI 2023] Pinball

翻译来自 [LibreOJ](https://loj.ac/p/4801)。

**题目译自 [Romanian Master of Informatics 2023](https://rmi.lbi.ro/rmi_2023/) Day1 T3 「[Pinball](https://csacademy.com/contest/rmi-2023-day-1/task/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$ 个询问的答案。

对于所有输入数据，满足： * $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}$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :---: | :---: | :--: | | $1$ | $13$ | $N, Q \leq 1\ 000$| | $2$ | $8$ | $Q, T \leq 1\ 000$ | | $3$ | $16$ | $1 \leq len \leq 10$ | | $4$ | $10$ | $T \leq 10^6$ | | $5$ | $11$ | $len \cdot freq \leq 10^6$ | | $6$ | $9$ | 令 $S$ 为输入中所有 $freq$ 的总和，$S \leq 10^6$ | | $7$ | $33$ | 无附加限制 |