Kinesis, en explorant Chu Chu Island pour vaincre le Mage Noir, a rencontré Muto l'affamé. Simia, qui nourrit Muto chaque jour, a demandé de l'aide à Kinesis pour préparer une pizza géante pour Muto, qui se plaint de sa faim. Comme Muto, avec sa grande taille, bloque le chemin vers le Mage Noir, Kinesis n'a d'autre choix que d'accepter la demande de Simia.
La grande pizza que Muto désire est une grille de taille $N \times N$. La case en haut à gauche est la ligne $1$, colonne $1$, et la case en bas à droite est la ligne $N$, colonne $N$. La recette donnée par Simia montre la disposition des boulettes de viande à placer sur la pizza, et Kinesis doit garnir la pizza selon cette recette. Au départ, une boulette de viande placée par Simia se trouve à la ligne $R$, colonne $C$ de la pizza. La forme d'une boulette de viande correspond exactement à une case de la grille, et il ne peut y avoir plus d'une boulette par case.
État de la pizza et positions où la télékinésie peut être utilisée depuis l'extérieur pour $N=5, R=3, C=2$
Comme marcher sur la pizza la rendrait immangeable, Kinesis doit utiliser la télékinésie depuis l'extérieur de la pizza pour la compléter. Le processus d'utilisation de la télékinésie une fois est le suivant :
- Choisir la position pour utiliser la télékinésie. Les positions possibles sont le haut, le bas, la gauche ou la droite de la pizza. La télékinésie commence à partir de l'endroit où se trouve Kinesis : si elle est utilisée depuis le haut, elle agit dans la direction où le numéro de ligne augmente ; depuis le bas, où le numéro de ligne diminue ; depuis la gauche, où le numéro de colonne augmente ; et depuis la droite, où le numéro de colonne diminue.
- Choisir le numéro de la ligne ou de la colonne où appliquer la télékinésie. La télékinésie doit être utilisée parallèlement à la ligne ou à la colonne, et ne peut pas être utilisée sur plus d'une ligne ou colonne à la fois.
- Utiliser la télékinésie. Il existe deux types de télékinésie :
- Pousser (push) : Pousse une boulette de viande pour la placer dans la case juste devant la première boulette rencontrée. Si, avant de pousser, il y a déjà une boulette dans la première case dans la direction de la télékinésie, ou si la boulette poussée ne peut pas être placée à l'intérieur de la pizza parce qu'il n'y a pas de boulette dans cette direction, la boulette poussée disparaît.
- Tirer (pull) : Retire la première boulette de viande rencontrée par la télékinésie hors de la pizza. S'il n'y a pas de boulette de viande dans la direction utilisée, rien ne se passe.
Utilisation de la télékinésie pour pousser (push) et tirer (pull)
Si la pizza est garnie selon la recette de Simia, Muto mangera la pizza avec plaisir et ouvrira le chemin vers la région suivante. Cependant, comme on ne sait jamais quand le Mage Noir détruira le monde, Kinesis ne peut pas perdre de temps à préparer la pizza.
Affichez une méthode pour compléter la pizza en utilisant la télékinésie au plus $2N^2$ fois.
Entrée
La première ligne contient la taille de la pizza $N$ ($3 \leq N \leq 50$).
La deuxième ligne contient deux entiers $R$ et $C$ séparés par un espace, représentant la ligne et la colonne de la boulette de viande initialement placée par Simia ($1 \leq R, C \leq N$).
Ensuite, $N$ lignes suivent, représentant la disposition des boulettes de viande selon la recette de Simia. Chaque ligne contient une chaîne de caractères de longueur $N$. Le $j$-ième caractère de la $i$-ième ligne indique la présence d'une boulette de viande à la ligne $i$, colonne $j$ : . signifie une case vide, et # signifie une case avec une boulette de viande.
Sortie
S'il est possible de compléter la pizza en utilisant la télékinésie au plus $2N^2$ fois, affichez sur la première ligne le nombre de fois $M$ que Kinesis a utilisé la télékinésie. Notez que $M$ n'a pas besoin d'être minimal ($0 \leq M \leq 2N^2$).
Si $M \geq 1$, affichez les actions effectuées par Kinesis sur les $M$ lignes suivantes, une par ligne. Chaque ligne doit contenir la position utilisée (haut : U, bas : D, gauche : L, droite : R), le numéro de la ligne ou de la colonne $X$ ($1 \leq X \leq N$), et le type de télékinésie (push pour pousser, pull pour tirer), séparés par des espaces.
S'il est impossible de compléter la pizza en utilisant la télékinésie au plus $2N^2$ fois, affichez uniquement -1 sur la première ligne.
Exemples
Entrée 1
3 2 2 .#. ##. ...
Sortie 1
2 U 2 push L 2 push
Entrée 2
3 1 2 ... #.# .#.
Sortie 2
6 D 2 push D 2 push L 2 push R 2 push U 2 pull U 2 pull
Entrée 3
4 1 1 .... .... .... ....
Sortie 3
1 L 1 pull