Problem C
Lista

Mirko received a birthday present from his aunt in the US – a brand-new doubly-linked list (an example of which is shown in the figure below). The list contains $N$ nodes numbered $1$ through $N$. Two types of moves can be done on the list:

1. Move node $X$ in front of node $Y$.

2. Move node $X$ after node $Y$.

Mirko played with his new toy for hours, writing down each move on a piece of paper so that he can reconstruct the list’s initial state (nodes $1$ through $N$ in order from left to right).

When he decided to reconstruct the list, Mirko was astonished to find that there is no easy way to invert the moves and restore the list’s initial state. Mirko cannot know where node $X$ was prior to each move, only where it ended up.

Seeing how Mirko is still recovering from the shock, write a program that finds a shortest sequence of moves that restores the list to its initial state from Mirko’s logs.

Input

The first line of input contains two integers $N$ and $M$ ($2\le N\le 500000$, $0\le M\le 100000$), the number of nodes and the number of moves made by Mirko.

Each of the next $M$ rows contains a description of a single move made by Mirko – the type of move(‘A’ or ‘B’) and two integers $X$ and $Y$.

Output

Output the minimum number of moves (call this number $K$) on the first line. Each of the next $K$ lines should contain a description of a single move in the same format as in the input.

Note: The sequence need not be unique.

2 1
A 2 1

1
A 1 2

4 3
B 1 2
A 4 3
B 1 4

2
A 1 2
B 4 3

6 5
A 1 4
B 2 5
B 4 2
B 6 3
A 3 5

3
A 4 5
B 6 5
A 2 3