Problem Background

Mirko received a gift — a brand new doubly linked list!

Problem Description

This list of length $n$ contains nodes $1$ through $n$, arranged from left to right.

Two operations can be performed on this list:

• A x y: Move node $x$ to the position before node $y$.
• B x y: Move node $x$ to the position after node $y$.

Example:

This is the initial state of a list with 6 nodes.

This is the state of the list after performing operation A 1 4.

This is the state of the list after performing operation B 3 5.

Mirko played with this list for hours. Each time he performed an operation, he recorded it on paper.

When he was done and wanted to restore the list, he was surprised to find that he didn't know the fastest way to do it, as he only knew the final positions of the nodes.

Please use operations A and B to find the minimum number of operations needed to restore the list and output each operation.

Input Format

The first line of input contains two integers $n$ and $k$, representing the number of nodes in the list and the number of operations Mirko performed, respectively.

The next $k$ lines each describe an operation that Mirko recorded on paper, in the format described in the problem.

Output Format

The first line of output should contain a single integer $K$, representing the minimum number of operations needed to restore the list.

The next $K$ lines should each describe an operation to restore the list, in the same format as the input.

Sample Input and Output

Sample Input #1

2 1
A 2 1 

Sample Output #1

1
A 1 2 

Sample Input #2

4 3
B 1 2
A 4 3
B 1 4 

Sample Output #2

2
A 1 2
B 4 3 

Sample Input #3

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

Sample Output #3

3
A 4 5
B 6 5
A 2 3

Notes

Data Range and Constraints

For $100\%$ of the data, $2 \le n \le 5 \times 10^5$, $0 \le m \le 1 \times 10^5$.

Note

Translated from COCI2006-2007 CONTEST #3 T6 BICIKLI

Thanks to @andyli for providing the SPJ.

见题面 Input 部分

见题面 Output 部分