Prologin, le concours national d'informatique

Énoncé¶

Une fois la tâche accomplie, votre correspondant laisse une autre lettre pour donner rendez-vous à Joseph Marchand. Cependant, le message est chiffré d'une manière très spécifique. À l'aide d'un message connu et de sa version chiffrée, Joseph va essayer de comprendre comment fonctionne le chiffrement.

Le message en clair et le message chiffré sont encodés en deux listes, contenant une fois chaque entier de $1$ à $N$.

Pour dériver le message chiffré depuis le message en clair, Joseph suppose que deux opérations ont pu être utilisées :

EMPILE : Déplacer le dernier élément du message chiffré à la fin d'un registre temporaire;
DEPILE : Déplacer le dernier élément du registre temporaire à la fin du message chiffré.

Aidez Joseph à déterminer, si elle existe, la suite d'instruction permettant de dériver le message chiffré depuis le message en clair.

Entrée¶

L’entrée contiendra :

Sur la première ligne, un entier : N, taille des messages.
Sur la ligne suivante, une liste de N entiers séparés par des espaces : clair, message en clair.
Sur la ligne suivante, une liste de N entiers séparés par des espaces : chiffre, message chiffré.

Sortie¶

Afficher une instruction par ligne parmi EMPILE / DEPILE afin de dériver le message chiffré depuis le message en clair. Si cela est impossible, afficher sur une seule ligne IMPOSSIBLE.

Contraintes¶

$1 \le N \le 100$
$\mathtt{clair}$ et $\mathtt{chiffre}$ sont des permutations de $[1; N]$

Contraintes de performance¶

$1 \le N \le 100\,000$

Contraintes d'exécution

Utilisation mémoire maximum: 100000 kilo-octets
Temps d'exécution maximum: 1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

5
5 4 3 2 1
1 3 5 4 2

Exemple de sortie

EMPILE
DEPILE
EMPILE
EMPILE
DEPILE
EMPILE
EMPILE
DEPILE
DEPILE
DEPILE

Commentaire

Voici une image décrivant la suite des actions permettant d'ordonner les nombres de la manière désirée dans la pile de sortie :

piles

Les étapes se lisent de gauche à droite, puis de haut en bas. La pile de gauche est la pile d'entrée, la pile du milieu représente la pile temporaire, et la pile de sortie est la plus à droite.