Mirko 收到了一份来自他在美国的阿姨送的生日礼物——一个全新的双向链表（其示例如下图所示）。该链表包含 $N$ 个节点，编号为 $1$ 到 $N$。在链表上可以进行两种操作：

• A：将节点 $X$ 移动到节点 $Y$ 的前面。
• B：将节点 $X$ 移动到节点 $Y$ 的后面。

拥有 6 个节点的链表示例。

执行操作 "A 1 4" 后的链表。

再执行操作 "B 3 5" 后的链表。

Mirko 玩了几个小时这个新玩具，并在纸上记录下了每一次操作，以便他能够重建链表的初始状态（即节点 $1$ 到 $N$ 从左到右依次排列）。

当他决定重建链表时，Mirko 惊讶地发现，并没有一种简单的方法可以逆转这些操作并恢复链表的初始状态。Mirko 无法知道在每次操作之前节点 $X$ 处于什么位置，只知道它最终到了哪里。

看到 Mirko 仍在震惊中恢复，请编写一个程序，根据 Mirko 的记录，找出能够将链表恢复到初始状态的最少操作序列。

输入格式

第一行包含两个整数 $N$ 和 $M$（$2 \le N \le 500\,000$，$0 \le M \le 100\,000$），分别表示节点的数量和 Mirko 进行的操作次数。

接下来的 $M$ 行，每行包含一个 Mirko 进行的操作的描述——操作类型（'A' 或 'B'）以及两个整数 $X$ 和 $Y$。

输出格式

第一行输出最少操作次数（设为 $K$）。

接下来的 $K$ 行，每行应包含一个操作的描述，格式与输入相同。

注意：操作序列不唯一，输出任意一种满足要求的最少操作序列即可。

子任务

如果输出的次数 $K$ 和操作序列均正确，您将获得该测试点的满分。

如果您的程序输出了正确的次数 $K$，但没有输出操作序列，或者操作序列不正确，您将获得该测试点 $60\%$ 的分数。

样例

输入样例 1

2 1
A 2 1

输出样例 1

1
A 1 2

输入样例 2

4 3
B 1 2
A 4 3
B 1 4

输出样例 2

2
A 1 2
B 4 3

输入样例 3

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

输出样例 3

3
A 4 5
B 6 5
A 2 3