Даны две перестановки $A$ и $B$ размера $n$. Обе перестановки содержат целые числа от $1$ до $n$. Вам необходимо преобразовать $A$ в $B$ не более чем за $n$ операций следующего вида:

• Выбрать подотрезок $[l; r]$ перестановки $A$ и отсортировать его в порядке возрастания или убывания.

Обратите внимание, что минимизировать количество операций не требуется, подойдет любая последовательность операций длиной не более $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)ncreasing (возрастания) или (D)ecreasing (убывания).

Если существует несколько решений, допустимо любое из них. Гарантируется, что решение существует.

Примеры

Входные данные 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