Dane są dwie permutacje $A$ oraz $B$ o rozmiarze $n$. Obie permutacje zawierają liczby całkowite od $1$ do $n$. Chcesz przekształcić $A$ w $B$ w nie więcej niż $n$ operacjach następującego rodzaju:

• Wybierz podprzedział $[l; r]$ permutacji $A$ i posortuj go w porządku rosnącym lub malejącym.

Zauważ, że nie musisz minimalizować liczby operacji; dowolna sekwencja operacji o długości nie większej niż $n$ jest dopuszczalna.

Wejście

Pierwsza linia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 500$) — rozmiar obu permutacji. Druga linia zawiera permutację $A_1, A_2, \dots, A_n$. Trzecia linia zawiera permutację $B_1, B_2, \dots, B_n$.

Wyjście

W pierwszej linii wypisz jedną liczbę całkowitą $m$ ($0 \le m \le n$) — liczbę operacji. W kolejnych $m$ liniach wypisz opisy operacji. Każdy opis powinien być sformatowany jako $l_i \ r_i \ t_i$ ($1 \le l_i \le r_i \le n$, $t_i$ to 'I' lub 'D'), co oznacza posortowanie podprzedziału $[l_i; r_i]$ odpowiednio w porządku (I)rosnącym lub (D)malejącym.

Jeśli istnieje wiele rozwiązań, każde z nich zostanie zaakceptowane. Gwarantuje się, że istnieje co najmniej jedno rozwiązanie.

Przykład

Wejście 1

5
2 4 5 1 3
5 4 3 2 1

Wyjście 1

1
1 5 D

Wejście 2

5
5 4 3 2 1
3 2 5 1 4

Wyjście 2

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

Wejście 3

5
3 1 4 5 2
3 1 4 5 2

Wyjście 3

0