이중 연결 리스트

창영이는 1학년 때 숙제로 만들었던 이중 연결 리스트 소스를 상근이에게 생일 선물로 보내주었다. 상근이는 자신이 원하던 기능이 있는 소스를 받게 되어 매우 기뻤고, 하루 종일 이 리스트를 가지고 놀려고 한다.

리스트에는 총 N개의 노드가 있다. 처음에는 가장 왼쪽 노드가 1번이고, 오른쪽으로 갈수록 번호가 1씩 증가한다. 이 리스트는 다음 두 가지 연산을 수행할 수 있다.

A) 노드 X를 노드 Y의 바로 앞으로 이동한다.

B) 노드 X를 노드 Y의 바로 뒤로 이동한다.

아래 그림은 노드가 6개인 이중 연결 리스트의 모습이다.

여기에 A 1 4 연산을 수행하면 아래와 같이 된다. 노드 1을 노드 4의 바로 앞으로 이동한 것이다.

그 다음 B 3 5 연산을 수행하면 아래 그림과 같은 모습이 된다. 노드 3을 노드 5의 바로 뒤로 이동한 것이다.

상근이가 리스트를 가지고 다 논 뒤에는 리스트를 처음 상태로 되돌려야 한다. 그래서 상근이는 자신이 입력한 연산을 모두 종이에 적어 두었다.

상근이가 입력한 모든 연산이 주어졌을 때, 리스트를 처음 상태로 만들기 위해 수행해야 하는 연산을 출력하는 프로그램을 작성하시오. 이때 사용하는 연산의 수는 가능한 한 적어야 한다.

첫째 줄에 노드의 수 N과 연산의 수 M이 주어진다. (2 <= N <= 500,000, 0 <= M <= 100,000)

다음 M개 줄에는 상근이가 입력한 연산이 위에서 설명한 형식으로 주어진다.

첫째 줄에 처음 상태로 되돌리기 위해 필요한 연산 수의 최솟값을 출력한다. 이 값을 K라고 하자.

다음 K개 줄에는 리스트가 수행해야 하는 연산을 순서대로 출력한다.

최소 횟수의 복원 방법이 여러 가지라면 그중 아무 것이나 출력해도 된다.