Bạn được cho hai hoán vị $A$ và $B$ có kích thước $n$. Cả hai hoán vị đều chứa các số nguyên từ $1$ đến $n$. Bạn muốn biến đổi $A$ thành $B$ trong không quá $n$ thao tác thuộc loại sau:

• Chọn một đoạn con $[l; r]$ của $A$ và sắp xếp nó theo thứ tự tăng dần hoặc giảm dần.

Lưu ý rằng bạn không cần phải tối thiểu hóa số lượng thao tác, bất kỳ chuỗi thao tác nào có độ dài không quá $n$ đều được chấp nhận.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 500$) — kích thước của cả hai hoán vị. Dòng thứ hai chứa hoán vị $A_1, A_2, \dots, A_n$. Dòng thứ ba chứa hoán vị $B_1, B_2, \dots, B_n$.

Dữ liệu ra

Trên dòng đầu tiên, in ra một số nguyên $m$ ($0 \le m \le n$) — số lượng thao tác. Trên $m$ dòng tiếp theo, in ra mô tả của các thao tác. Mỗi mô tả nên được định dạng là $l_i \ r_i \ t_i$ ($1 \le l_i \le r_i \le n$, $t_i$ là 'I' hoặc 'D') và có nghĩa là sắp xếp đoạn con $[l_i; r_i]$ theo thứ tự (I)ncreasing (tăng dần) hoặc (D)ecreasing (giảm dần).

Nếu có nhiều lời giải khác nhau, bất kỳ lời giải nào cũng sẽ được chấp nhận. Đảm bảo rằng luôn tồn tại ít nhất một lời giải.

Ví dụ

Dữ liệu vào 1

5
2 4 5 1 3
5 4 3 2 1

Dữ liệu ra 1

1
1 5 D

Dữ liệu vào 2

5
5 4 3 2 1
3 2 5 1 4

Dữ liệu ra 2

4
2 5 I
1 4 I
1 3 D
3 4 D

Dữ liệu vào 3

5
3 1 4 5 2
3 1 4 5 2

Dữ liệu ra 3

0