Ants on a Stick

There are many ants on an infinitely long stick. Each ant has a unique initial position and an initial direction. The ants move at a speed of 1 unit per second. When two ants meet, they immediately reverse their directions (the turning time is negligible).

Your task is to determine the final position and direction of each ant after t seconds.

Note: Although it appears that the ants interact, a well‐known trick is that the ants can be thought of as passing through each other. However, because each ant has an identity, when two ants meet, their identities swap. In other words, if you compute the position of each ant if they moved without colliding (called the "ghost positions") and then assign these positions in sorted order to the ants arranged by their initial positions, you obtain the final positions. Moreover, if two or more ghost positions coincide (indicating a collision exactly at time t), the corresponding ant’s direction is reversed compared to that ghost state.

Input Format: The first line contains two integers n and t — the number of ants and the time in seconds. Then follow n lines, each containing an integer and a character. The integer is the initial position and the character is either 'L' (for left) or 'R' (for right). All initial positions are distinct.

Output Format: Output n lines. For each ant (in the same order as the input), print its final position and final direction (separated by a space) after t seconds.

Example:

Input:
2 5
0 R
10 L
Output:
5 L
5 R

</p>

inputFormat

The first line contains two integers n and t ($1 \le n \le 10^5$, $0 \le t \le 10^9$), representing the number of ants and the time in seconds respectively. The following n lines each contain an integer p and a character d separated by a space, where p is the initial position of an ant and d is its initial direction ('L' for left or 'R' for right). All positions are distinct.

outputFormat

For each ant (in the same order as input), output one line with two items: the final position (an integer) and the final direction ('L' or 'R') after t seconds, separated by a space.

sample

2 5
0 R
10 L

5 L
5 R

</p>