Vous disposez de deux permutations $A$ et $B$ de taille $n$. Les deux permutations contiennent des entiers de $1$ à $n$. Vous souhaitez transformer $A$ en $B$ en utilisant au plus $n$ opérations du type suivant :

• Choisir un sous-segment $[l; r]$ de $A$ et le trier par ordre croissant ou décroissant.

Notez qu'il n'est pas nécessaire de minimiser le nombre d'opérations ; toute séquence d'opérations de longueur inférieure ou égale à $n$ est acceptable.

Entrée

La première ligne contient un entier $n$ ($1 \le n \le 500$) — la taille des deux permutations. La deuxième ligne contient la permutation $A_1, A_2, \dots, A_n$. La troisième ligne contient la permutation $B_1, B_2, \dots, B_n$.

Sortie

Sur la première ligne, imprimez un entier $m$ ($0 \le m \le n$) — le nombre d'opérations. Sur les $m$ lignes suivantes, imprimez les descriptions des opérations. Chaque description doit être formatée comme $l_i \ r_i \ t_i$ ($1 \le l_i \le r_i \le n$, $t_i$ est 'I' ou 'D') et signifie le tri du sous-segment $[l_i; r_i]$ dans l'ordre (I)ncroissant ou (D)écroissant.

S'il existe plusieurs solutions, n'importe laquelle sera acceptée. Il est garanti qu'au moins une solution existe.

Exemples

Entrée 1

5
2 4 5 1 3
5 4 3 2 1

Sortie 1

1
1 5 D

Entrée 2

5
5 4 3 2 1
3 2 5 1 4

Sortie 2

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

Entrée 3

5
3 1 4 5 2
3 1 4 5 2

Sortie 3

0