Mirko nhận được quà sinh nhật từ cô của anh ấy ở Mỹ - mộ danh sách liên kết đôi (như hình dưới). Danh sách gồm ~N~ nút dược đánh số từ 1 tới ~N~. 2 loại di chuyển có thể được hoàn thành trên danh sách là:

A) Di chuyển nút X đến trước nút Y.

B) Di chuyển nút X ra sau nút Y.

Mirko đã chơi với đồ chơi của mình hàng giờ, viết các bước di chuyển cho mỗi mảnh giấy do đố anh ấy có thể xây dựng lại trạng thái ban đầu của danh sách (nút 1 đến ~N~ theo thứ tự từ trái sang phải).

Khi anh ấy quyết định xây dựng lại danh sách, Mirko đã ngạc nhiên khi phát hiện ra không có cách đơn giản nào để có thể đảo ngược các bước di chuyển và khôi phục lại trạng thái ban đầu. Mirko không thể biết nút X ở đâu trước mỗi lần di chuyển, chỉ biết nó kết thúc ở đâu.

Mirko vẫn đang hồi phục lại sau cú sốc, bạn hãy viết một chương trinh để tìm đoạn di chuyển nhỏ nhất để khôi phục lại trạng thái ban đầu của danh sách từ nhật ký của Mirko

Input

Dòng đầu tiên gồm 2 số ~N~ và ~M~ (~2 <= N <+ 500000, 0 <= M <= 100000~), số lượng nút và số bước di chuyển của Mirko.

M dòng tiếp theo chứa mô tả về các bước đi của Mirko - loại di chuyển ('A' hoặc 'B') và 2 số nguyên ~X~, ~Y~.

Output

In ra số bước di chuyển ít nhất (gọi số này là ~K~) trên một dòng.

~K~ dòng tiếp theo chứa mô tả về bước di chuyển có cùng định dạng như Input.

Note: Dãy không nhất thiết phải là duy nhất.

Sample Input 1

2 1
A 2 1

Sample Output 1

1
A 1 2

Sample Input 2

4 3
B 1 2
A 4 3
B 1 4

Sample Output 2

2
A 1 2
B 4 3

Sample Input 3

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

Sample Output 3

3
A 4 5
B 6 5
A 2 3