← 返回题目列表

Codeforces · 652/F

F. 圆圈上的蚂蚁

中文机器翻译题面 查看原题

n 只蚂蚁在长度为 m 的圆上。一只蚂蚁每单位时间移动一单位距离。最初,蚂蚁编号 i 位于位置 si 并面向方向 di(L 或 R)。位置从某个点开始按逆时针顺序编号。所有蚂蚁的位置都是不同的。

所有蚂蚁同时移动,每当两只蚂蚁接触时,它们都会改变方向。请注意,蚂蚁有可能在某个方向上移动一半的时间单位,并在相反的方向上移动另一半的时间单位。

打印 t 时间单位后蚂蚁的位置。

输入

第一行包含三个整数 n、m 和 t (2 ≤ n ≤ 3·105, 2 ≤ m ≤ 109, 0 ≤ t ≤ 1018) — 蚂蚁的数量、圆圈的长度和时间单位的数量。

接下来的 n 行中的每一行都包含整数 si 和符号 di (1 ≤ si ≤ m 且 di 是 L 或 R)——第 i 只蚂蚁在开始时的位置和方向。方向L和R分别对应于顺时针方向和逆时针方向。

保证所有位置 si 都是不同的。

输出

打印 n 个整数 xj — t 时间单位后第 j 只蚂蚁的位置。蚂蚁按照它们在输入中出现的顺序从 1 到 n 编号。

示例

输入 #1

2 4 8
1 R
3 L

输出 #1

1 3

输入 #2

4 8 6
6 R
5 L
1 R
8 L

输出 #2

7 4 2 7

输入 #3

4 8 2
1 R
5 L
6 L
8 R

输出 #3

3 3 4 2