Problem G
Gas Station

You are a late night attendant at a busy gas station. You can only go home after all the cars have topped up their fuel tanks and left the gas station. The gas station you work at has $P$ gas pump columns, counting from left to right, and each column has two gas pumps, pump A and pump B. A pump can serve cars with left side fuel doors on its right side, or cars with right side fuel doors on its left side. A pump can serve a car on its left side and a car on its right side simultaneously. Thus, each pump column has two lanes for cars.

Cars arriving at the gas station follow strict rules. A car will go to the leftmost open lane that is suitable for its fuel door side. If there are no open lanes, the car will queue up for the suitable lane with the shortest queue. If there are multiple lanes with the shortest queue, the car will queue up in the leftmost one. Once a car has joined a queue, it cannot switch to a different one. After cars leave after refueling and a lane becomes open, the next car in the queue for that lane will go to use a pump.

A lane is open if pump A is available. If pump B is available but pump A is occupied, the lane is not open. When a car goes to an open lane, if both pumps are available, the car will go to pump B, otherwise it will go to pump A. If a car arrives at the same time as some other cars have just finished filling up and left, the new car waits for all other cars in the queues to move to the open pumps (if any) before deciding where to queue. When a car leaves from a pump A, but the pump B ahead of it is occupied, the car is stil able to leave immediately.

You know that Car $i$ arrives at time $t_ i$, requires just under $f_ i$ minutes to fill up and leave, and has its fuel door on the $s_ i$ side.

Knowing all this, you want to know when you will be able to go home.

Input

The first line of input contains two space separated integers, $1\leq P\leq 10$, the number of gas pump columns, and $1\leq N\leq 1000$, the total number of cars that will arrive.

The next $N$ lines each contains two integers $1\leq t_ i\leq 10^{5}$, $1\leq f_ i\leq 100$, and a single character R or L for $s_ i$, all separated by a space.

It is guaranteed that $t_ i < t_{i+1}$ for all $1 \leq i < N$.

Output

Output $N$ lines containing the time when each car leaves the gas station, in the order that the cars are listed in the input.

1 4
1 9 L
2 5 L
3 10 L
4 10 L

10
7
17
27

1 4
1 9 L
2 9 L
3 10 L
4 10 L

10
11
21
21

1 2
8 11 R
9 10 L

19
19

2 10
1 10 R
2 3 R
3 10 R
4 12 R
5 1 R
6 5 R
7 10 R
10 2 R
11 7 R
13 4 R

11
5
13
16
6
11
21
18
18
22