机器人巡游

时间限制:1s

空间限制:64MB

题目描述

现有一数轴。数轴上两个点\(x=0,x=m\)上各有一堵墙。

一些机器人初始在\([0,m]\)上以每秒\(1\)的速度来回巡游。若机器人碰到墙，它就会调转方向，速度的大小不变。

调转方向不计时间。

若两个 正在巡游的 机器人在 某整数时间 处于同一位置，则它们会相撞，并立刻在原地停下，不再进行巡游。由于它们已经停止巡游，所以不会和其他机器人再次相撞。特别地，若两个正在巡游的机器人在 非整数时间 处于同一位置，则 无事发生 。

现给出机器人的初始位置和初始方向，问各机器人停止巡游的时间。特别地，若机器人不会停下来，认为其停止巡游时间为\(-1\)。

输入格式

第一行两个正整数\( n,m\)。表示机器人的数量和数轴的右边界

第二行，每行\(n\)个整数\(loc_i\)，表示初始位置

第三行，每行\(n\)个整数\(v_i\)，表示初始方向。其中'R'表示机器人初始沿数轴正方向巡游，'L'表示初始沿数轴负方向巡游。

初始位置将按照从小到大的顺序给出，即\(loc_1<loc_2<...\)

输出格式

\(n\)个整数，用空格隔开。按照原先的顺序，输出各个机器人的停止巡游时间。

特别地，若某机器人不会停下来，则用\(-1\)表示。

样例输入1

2 10
1 3
L L

样例输出1

2 2

样例1解释

第0秒，两个机器人在1,3位置，方向向左

第1秒，位置是(0,2)，此时左侧的机器人方向变为右。

第2秒，(1,1)，两机器人相撞。

样例输入2

7 12
1 2 3 4 9 10 11
R R L L R R R

样例输出2

1 1 1 1 2 -1 2 

样例2解释

位于(1，3)，(2，4)的两对机器人在第一秒运动后就会相撞， 注意(2，3)是不会相撞的，因为它们在0.5秒时相遇，不是整数时间。

接下来看9,10,11的三个机器人，可以分析出第2秒\(9,11\)的两个机器人相撞，而场上仅剩下一个机器人，它将永远在数轴上巡游。

数据范围及限制

共\(25\)组测试数据，每个测试点\( 10\)分。

对于\(40\%\)的数据，\(1\le n\le m\le 15\)

对于\(80\%\)的数据，\(1\le n\le 200, 1\le m\le 10^7\)

对于\(100\%\)的数据，\(1\le n\le 10^5, 1\le m\le 10^8\)。

初始位置将按照从小到大的顺序给出，即\(loc_1<loc_2<...\)

任意两个机器人的初始位置不同。初始位置一定在\((0,m)\)之间，初始方向一定是'R'或'L'