시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 11 3 3 27.273%

문제

You are given two permutations $A$ and $B$ of size $n$. You want to transform $A$ to $B$ in no more than $n$ operations of the following kind:

  • Choose a subsegment $[l;r]$ of $A$ and sort it in either increasing or decreasing order.

Note that you don't have to minimize the number of operations, any sequence of operations of length not more than $n$ is ok.

입력

The first line contains one integer $n$ ($1 \le n \le 500$) --- the sizes of both permutations.

The second line contains the permutation $A_{1}, A_{2}, \ldots, A_{n}$.

The third line contains the permutation $B_{1}, B_{2}, \ldots, B_{n}$.

출력

On the first line print one integer $m$ ($0 \le m \le n$) --- the number of operations.

On the next $m$ lines print the descriptions of operation. One description has a form $l_{i}$ $r_{i}$ $t_{i}$  ($1 \le l_{i} \le r_{i} \le n$, $t_{i}$ is 'I' or 'D') and means sort the subsegment $[l_{i};r_{i}]$ in (I)ncreasing or (D)ecreasing order.

If there are different solutions any one will be accepted. It is guaranteed that there is at least one solution.

예제 입력 1

5
2 4 5 1 3
5 4 3 2 1

예제 출력 1

1
1 5 D

예제 입력 2

5
5 4 3 2 1
3 2 5 1 4

예제 출력 2

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

예제 입력 3

5
3 1 4 5 2
3 1 4 5 2

예제 출력 3

0