크기가 $n$인 두 순열 $A$와 $B$가 주어진다. 두 순열 모두 $1$부터 $n$까지의 정수를 포함한다. $A$를 $B$로 변환하기 위해 다음 종류의 연산을 최대 $n$번 수행하고자 한다.

• $A$의 부분 구간 $[l, r]$을 선택하여 오름차순 또는 내림차순으로 정렬한다.

연산 횟수를 최소화할 필요는 없으며, $n$번 이하의 연산으로 이루어진 임의의 순서라면 충분하다.

입력

첫 번째 줄에는 두 순열의 크기인 정수 $n$ ($1 \le n \le 500$)이 주어진다. 두 번째 줄에는 순열 $A_1, A_2, \dots, A_n$이 주어진다. 세 번째 줄에는 순열 $B_1, B_2, \dots, B_n$이 주어진다.

출력

첫 번째 줄에 연산 횟수 $m$ ($0 \le m \le n$)을 출력한다. 다음 $m$개의 줄에는 각 연산에 대한 설명을 출력한다. 각 설명은 $l_i \ r_i \ t_i$ ($1 \le l_i \le r_i \le n$, $t_i$는 'I' 또는 'D') 형식이어야 하며, 이는 부분 구간 $[l_i, r_i]$를 (I)오름차순 또는 (D)내림차순으로 정렬함을 의미한다.

여러 가지 해답이 존재할 경우 그중 아무거나 출력해도 된다. 적어도 하나의 해답이 존재함이 보장된다.

예제

입력 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