题目背景

Mirko 收到了一份礼物——一个崭新的双向链表！

题目描述

这个长度为 $n$ 的链表包含 $1\sim n$ 这 $n$ 个节点，从左到右排列。

可以对这个链表执行两种操作：

• A x y：把 $x$ 节点放到 $y$ 节点前。

• B x y：把 $x$ 节点放到 $y$ 节点后。

例如：

这是一个有 $6$ 个节点的链表的初始状态。

这是进行操作 A 1 4 后的链表状态。

这是再进行操作 B 3 5 后的链表状态。

Mirko 把这个链表玩了几个小时。每进行一次操作，他都会在纸上记录下来。

当他兴致已尽，打算把链表恢复时，他惊讶地发现自己不知道最快的恢复方法，因为他只知道这些节点的结束位置。

请你运用 A B 两个操作，找出操作数最少的恢复方案并输出每一次的操作。

输入格式

输入第一行为两个整数 $n,k$，表示链表的节点个数和 Mirko 的操作次数。

接下来的 $k$ 行，每行描述一个 Mirko 在纸上记录下来的操作，格式如题目描述所示。

输出格式

输出第一行为一个整数 $K$，表示最少的恢复方案。

接下来的 $K$ 行，每行描述一个恢复时的操作，格式与输入相同。

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

提示

数据规模与约定

对于 $100\%$ 的数据，$2\le n\le 5\times 10^5$，$0\le m\le 1\times 10^5$。

说明

题目译自 COCI2006-2007 CONTEST #3 T6 BICIKLI

感谢

PJ。