Background

Mirko received a gift—a brand-new doubly linked list.

Problem Description

This linked list of length $n$ contains $n$ nodes labeled $1\sim n$, arranged from left to right.

Two types of operations can be performed on this linked list:

• A x y: move node $x$ to be placed before node $y$.

• B x y: move node $x$ to be placed after node $y$.

Example

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

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

This is the state after then performing the operation B 3 5.

Mirko played with the linked list for several hours. Every time he performed an operation, he wrote it down on paper.

When he got tired and planned to restore the linked list, he was surprised to find that he did not know the fastest way to restore it, because he only knows the final positions of these nodes.

Please use operations A and B to find a restoration plan with the minimum number of operations, and output each operation.

Input Format

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

The next $k$ lines each describe an operation Mirko wrote down, in the format shown in the statement.

Output Format

The first line outputs an integer $K$, representing the minimum number of operations in the restoration plan.

The next $K$ lines each describe an operation during restoration, in the same format as the input.

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

Hint

Constraints

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

Notes

This problem is translated from COCI2006-2007 CONTEST #3 T6 BICIKLI.

Thanks to

Translated by ChatGPT 5