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