Doubly Linked List

Changyeong gave Sanggeun the source code for a doubly linked list as a birthday present. Sanggeun was delighted to receive code with the exact features he wanted, and he plans to spend the whole day playing with the list.

The list contains N nodes. Initially, the leftmost node is numbered 1, and the numbers increase by 1 from left to right. The list supports two operations:

A) Move node X immediately before node Y.

B) Move node X immediately after node Y.

The following picture shows a doubly linked list with 6 nodes.

If the operation A 1 4 is performed, the list changes as shown below. Node 1 is moved immediately before node 4.

Next, if the operation B 3 5 is performed, the list becomes the one shown below. Node 3 is moved immediately after node 5.

After Sanggeun finishes playing with the list, it must be restored to its initial order. Therefore, he wrote down every operation he entered.

Given all operations Sanggeun entered, write a program that outputs operations that restore the list to its initial order. Use as few operations as possible.

The first line contains the number of nodes N and the number of operations M. (2 <= N <= 500,000, 0 <= M <= 100,000)

Each of the next M lines contains one operation entered by Sanggeun, in the format described above.

On the first line, print the minimum number of operations needed to restore the initial order. Let this value be K.

On each of the next K lines, print one operation that the list should perform, in order.

If there are several minimum-length restoration sequences, any one of them is valid.