CF1525C.Robot Collisions

There are $n$ robots driving along an OX axis. There are also two walls: one is at coordinate $0$ and one is at coordinate $m$.

The $i$-th robot starts at an integer coordinate $x_i~(0 \lt x_i \lt m)$ and moves either left (towards the $0$) or right with the speed of $1$ unit per second. No two robots start at the same coordinate.

Whenever a robot reaches a wall, it turns around instantly and continues his ride in the opposite direction with the same speed.

Whenever several robots meet at the same integer coordinate, they collide and explode into dust. Once a robot has exploded, it doesn't collide with any other robot. Note that if several robots meet at a non-integer coordinate, nothing happens.

For each robot find out if it ever explodes and print the time of explosion if it happens and $-1$ otherwise.

有 $n$ 个机器人沿 $OX$ 轴行驶。此外还有两堵墙：一堵位于坐标 $0$，另一堵位于坐标 $m$。

第 $i$ 个机器人起始于整数坐标 $x_i~(0 \lt x_i \lt m)$，并以每秒 $1$ 单位的速度向左（朝向 $0$）或向右运动。没有任何两个机器人起始位置相同。

每当一个机器人抵达一堵墙时，它会立即掉头，并以相同速度朝相反方向继续行驶。

当若干机器人在同一整数坐标相遇时，它们将发生碰撞并爆炸为尘埃。一旦某个机器人爆炸，它便不再与其他机器人发生碰撞。注意：若若干机器人在非整数坐标处相遇，则不会发生任何事件。

对每个机器人，请判断其是否会爆炸；若会爆炸，则输出其爆炸时刻；否则输出 $-1$。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

Then the descriptions of $t$ testcases follow.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le n \le 3 \cdot 10^5$; $2 \le m \le 10^8$) — the number of robots and the coordinate of the right wall.

The second line of each testcase contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \lt x_i \lt m$) — the starting coordinates of the robots.

The third line of each testcase contains $n$ space-separated characters 'L' or 'R' — the starting directions of the robots ('L' stands for left and 'R' stands for right).

All coordinates $x_i$ in the testcase are distinct.

The sum of $n$ over all testcases doesn't exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。

接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 3 \cdot 10^5$；$2 \le m \le 10^8$）——机器人的数量和右墙的坐标。

每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$（$0 \lt x_i \lt m$）——机器人的初始坐标。

每个测试用例的第三行包含 $n$ 个由空格分隔的字符，每个字符为 'L' 或 'R' —— 机器人初始运动方向（'L' 表示向左，'R' 表示向右）。

每个测试用例中所有坐标 $x_i$ 互不相同。

所有测试用例的 $n$ 值之和不超过 $3 \cdot 10^5$。

For each testcase print $n$ integers — for the $i$-th robot output the time it explodes at if it does and $-1$ otherwise.

对于每个测试用例，输出 $n$ 个整数——对于第 $i$ 个机器人，若其会爆炸，则输出其爆炸的时间；否则输出 $-1$。

Here is the picture for the seconds $0, 1, 2$ and $3$ of the first testcase:

Notice that robots $2$ and $3$ don't collide because they meet at the same point $2.5$, which is not integer.

After second $3$ robot $6$ just drive infinitely because there's no robot to collide with.

第一个测试用例中第 $0$、$1$、$2$ 和 $3$ 秒的示意图如下：

注意：机器人 $2$ 和 $3$ 并未发生碰撞，因为它们在同一点 $2.5$ 相遇，而该点不是整数。

第 $3$ 秒之后，机器人 $6$ 将无限行驶下去，因为其前方已无其他机器人可与其碰撞。