Right-hand obstruction

Every morning the residents of the capital of Berland have to stand in terrible traffic jams on their way to work. These jams are especially bad at the central square of the capital, which is an intersection and, moreover, an uncontrolled one: the people of Berland want to keep the historic look of the city center untouched.

Having decided to study the situation, the mayor of the capital ordered an investigation into exactly how the jams pile up. Turns are forbidden at the intersection, so cars can only drive straight through it. After installing special sensors, the specialists found that every morning $n$ cars try to drive through the intersection. Streets approach the intersection from four sides: if you look at a map, these streets run in the directions up <<U>>, left <<L>>, down <<D>>, and right <<R>>. On each street, a queue of cars can accumulate while they pass through the intersection.

When approaching the intersection, each driver acts as follows. The $i$-th driver arrives at the intersection at the beginning of second $t\_i$, joins the end of the queue on that street, and analyzes the situation.

If at the moment of analysis there is at least one other car ahead of the driver in the queue, he keeps waiting and analyzes the situation again at the beginning of the next second. If there are no cars ahead of him in the queue, he tries to drive through the intersection. If the driver has no right-hand obstruction, he leaves the queue, drives through the intersection during that second, and gets out of the trouble spot. Otherwise he stays in the queue and analyzes the situation again at the beginning of the next second. Drivers analyze the situation simultaneously, and only after that can the first driver in the queue start moving, so at most one car per second can pass through the intersection from each direction.

A driver at the intersection has a right-hand obstruction if there is at least one car in the queue on the perpendicular direction to his right. So drivers trying to pass the intersection in the up direction are obstructed by cars standing in the queue in the left direction, the left direction is obstructed by cars from the queue in the down direction, and so on. Note that if all four queues are non-empty, then every driver has a right-hand obstruction, and they will never pass the intersection.

Given the times at which the drivers arrived at the intersection, find out when each of them passes the intersection. Note that some drivers may never pass the intersection, remaining in the queue in front of it.

The first line contains an integer $n$, the number of cars approaching the intersection ($1 \le n \le 10^5$).

Each of the next $n$ lines contains a number $t\_i$ and a character $d\_i$: the number of the second at the beginning of which the $i$-th car arrives at the intersection, and the direction in which it tries to pass it ($0 \le t\_i \le 10^9$; $d\_i$ is <<U>> if the car goes up on the map, <<L>> if it goes left, <<D>> if down, and <<R>> if right). The cars are given in nondecreasing order of $t\_i$.

It is guaranteed that at any moment at most one new car approaches from each side.

For each car, in the order it is described in the input, output on a separate line the number of the second when it passes the intersection. If a car remains standing at the intersection, output $-1$ on the corresponding line.