우측 방해

베를린디아 수도 주민들은 매일 아침 출근길에 끔찍한 교통 체증 속에서 서 있어야 한다. 이 체증은 특히 수도 중앙 광장에서 심한데, 이곳은 교차로이고 게다가 비신호 교차로다. 베를린디아 사람들은 도심의 역사적 모습을 그대로 보존하려 한다.

수도 시장은 상황을 연구하기로 하고, 교통 체증이 정확히 어떻게 쌓이는지 조사하도록 지시했다. 교차로에서는 좌회전과 우회전이 금지되어 있으므로 차들은 오직 직진으로만 교차로를 통과할 수 있다. 전문가들은 특수 센서를 설치해, 매일 아침 $n$대의 차가 교차로를 통과하려 한다는 사실을 알아냈다. 교차로에는 네 방향에서 도로가 이어진다. 지도를 보면 이 도로들은 위쪽 <<U>>, 왼쪽 <<L>>, 아래쪽 <<D>>, 오른쪽 <<R>> 방향으로 뻗어 있다. 각 도로에는 교차로를 통과하는 과정에서 차들의 대기열이 쌓일 수 있다.

각 운전자는 교차로에 다가갈 때 다음과 같이 행동한다. $i$번째 운전자는 $t\_i$번째 초가 시작될 때 교차로에 다가가, 해당 도로의 대기열 끝에 서서 상황을 분석한다.

상황을 분석하는 순간 운전자 앞 대기열에 다른 차가 한 대라도 있으면, 그는 계속 기다리며 다음 초가 시작될 때 다시 상황을 분석한다. 앞에 차가 없으면 교차로를 통과하려 한다. 운전자에게 우측 방해가 없으면 대기열을 떠나 그 초에 교차로를 통과하고 이 곤란한 곳을 벗어난다. 그렇지 않으면 대기열에 남아 다음 초가 시작될 때 다시 상황을 분석한다. 운전자들은 동시에 상황을 분석하고, 그 뒤에야 대기열의 첫 번째 운전자가 출발할 수 있으므로, 매초 각 방향에서 교차로를 통과할 수 있는 차는 많아야 한 대다.

교차로 앞 운전자에게 우측 방해가 있다는 것은, 오른쪽에 있는 수직 방향의 대기열에 차가 한 대라도 있을 때를 말한다. 따라서 위쪽으로 교차로를 통과하려는 운전자는 왼쪽 방향 대기열에 서 있는 차들의 방해를 받고, 왼쪽 방향은 아래쪽 방향 대기열의 차들에게 방해를 받는 식이다. 네 대기열이 모두 비어 있지 않으면 모든 운전자에게 우측 방해가 있으므로 그들은 결코 교차로를 통과하지 못한다.

운전자들이 교차로에 다가간 시각에 대한 자료를 바탕으로, 각 운전자가 언제 교차로를 통과하는지 알아내시오. 일부 운전자는 교차로 앞 대기열에 남은 채 끝내 통과하지 못할 수도 있다.

첫째 줄에는 교차로에 다가가는 차의 수 $n$이 주어진다 ($1 \le n \le 10^5$).

다음 $n$개 줄 각각에는 수 $t\_i$와 문자 $d\_i$가 주어진다. $t\_i$는 $i$번째 차가 교차로에 다가가는 초의 번호이고, $d\_i$는 그 차가 통과하려는 방향이다 ($0 \le t\_i \le 10^9$). $d\_i$는 차가 지도에서 위로 가면 <<U>>, 왼쪽으로 가면 <<L>>, 아래로 가면 <<D>>, 오른쪽으로 가면 <<R>>이다. 입력에서 차들은 $t\_i$가 감소하지 않는 순서로 주어진다.

어느 순간에도 각 방향에서 새로운 차가 한 대를 넘게 다가가지 않음이 보장된다.

입력에 설명된 순서대로 각 차에 대해, 그 차가 교차로를 통과하는 초의 번호를 한 줄에 하나씩 출력한다. 차가 교차로에 남아 있게 되면 해당 줄에 $-1$을 출력한다.