시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB52240.000%

문제

Каждое утро жители столицы Берляндии вынуждены стоять в ужасных пробках по дороге на работу. Особенно сильно эти пробки заметны на центральной площади столицы, которая представляет собой перекресток, да еще и нерегулируемый --- берляндцы стремятся сохранить нетронутым исторический облик центра города.

Решив заняться исследованием ситуации, мэр столицы поручил изучить, как именно скапливаются пробки. Ведь на перекрестке запрещены повороты, таким образом, машины могут проезжать перекресток только прямо. Установив специальные датчики, специалисты выяснили, что каждое утро перекресток пытаются проехать $n$ машин. К перекрестку подходят улицы с четырех сторон: если посмотреть на карту, то эти улицы идут в направлении вверх <<U>>, влево <<L>>, вниз <<D>> и вправо <<R>>. На каждой из улиц в процессе проезда перекрестка может скапливаться очередь из машин.

Каждый водитель при подъезде к перекрестку действует следующим образом: $i$-й водитель подъезжает к перекрестку в начале $t_i$-й секунды, встает в конец очереди на этой улице и анализирует ситуацию.

Если в момент анализа ситуации перед водителем в очереди есть хотя бы одна другая машина, он продолжает ждать и в следующий раз анализирует ситуацию в начале следующей секунды. Если машин перед ним в очереди нет, он пытается проехать перекресток. Если у водителя нет помехи справа, то он покидает очередь, проезжает перекресток за эту секунду и уезжает из трудного места. Иначе он остается в очереди и анализирует ситуацию еще раз в начале следующей секунды. Водители анализируют ситуацию одновременно, и лишь затем первый в очереди водитель может начать движение, поэтому каждую секунду в каждом направлении перекресток может проехать не более одной машины.

У водителя перед перекрестком есть помеха справа, если на перпендикулярном направлении справа в очереди есть хотя бы одна машина. Таким образом, водителям, пытающимся проехать перекресток в направлении вверх, мешают машины, стоящие в очереди в направлении влево, направлению влево мешают машины из очереди в направлении вниз, и так далее. Заметим, что если все четыре очереди непусты, то у каждого водителя есть помеха справа, и они уже никогда не проедут перекресток.

По данным о времени, когда водители подъезжали к перекрестку, помогите выяснить, когда каждый из них проедет перекресток. Обратите внимание, что некоторые водители могут так и не проехать перекресток, оставшись в очереди перед ним.

입력

Первая строка содержит целое число $n$ --- количество машин, подъезжающих к перекрестку ($1 \le n \le 10^5$).

В каждой из следующих $n$ строк содержится число $t_i$ и символ $d_i$ --- номер секунды, в начале которой $i$-я машина подъезжает к перекрестку, и направление, в котором она пытается его проехать ($0 \le t_i \le 10^9$, $d_i$ равно <<U>>, если машина едет вверх по карте, <<L>>, если машина едет влево, <<D>>, если вниз, и <<R>>, если вправо). Машины во вводе заданы в порядке неубывания $t_i$.

Гарантируется, что в каждый момент времени с каждой стороны подъезжает не более одной новой машины.

출력

Для каждой машины в порядке их описания во вводе выведите в отдельной строке номер секунды, когда она проедет перекресток. Если машина останется стоять на перекрестке, выведите в соответствующей строке число $-1$.

예제 입력 1

4
0 R
0 U
0 L
5 D

예제 출력 1

2
1
0
5

예제 입력 2

7
0 U
0 D
1 L
1 D
2 D
2 R
2 U

예제 출력 2

0
0
-1
1
-1
-1
-1