Furiosa AI développe une NPU (Neural Processing Unit) capable d'accélérer l'apprentissage et l'inférence de modèles d'intelligence artificielle par rapport aux unités de traitement classiques. Un programme s'exécutant sur une unité de traitement classique traite les données stockées sur un hôte (host) en utilisant divers types d'opérateurs pour calculer les valeurs souhaitées. Dans ce problème, nous simplifions ce processus et considérons l'environnement suivant :

• L'hôte dispose d'un espace permettant de stocker $1\,000\,000$ données, chaque emplacement étant numéroté de $0$ à $999\,999$.
• Chaque opérateur reçoit une ou plusieurs données en entrée et calcule une donnée en sortie. Les opérateurs sont également numérotés de $0$ à $999\,999$.

• Le programme est exprimé selon la forme BNF (Backus-Naur Form) suivante :

  <number> ::= 0 | 1 | ... | 999999 <value> ::= <number> | <number>(<list>) <list> ::= <value> | <list>,<value>

• Le programme calcule une valeur unique. En d'autres termes, le programme est une chaîne de caractères correspondant à <value>.

• La valeur de <value> est calculée comme suit :
  • Si <value> est représenté par <number>, il s'agit de la donnée stockée à l'emplacement <number> de l'hôte avant le début du programme.
  • Si <value> est représenté par <number>(<list>), il s'agit de la donnée de sortie calculée en utilisant l'opérateur numéro <number> avec les <value> de la <list> comme données d'entrée successives.
• Un même <number> n'apparaît pas plusieurs fois dans un même programme.

La NPU développée par Furiosa AI peut exécuter le même programme plus rapidement qu'une unité de traitement classique, mais cela nécessite un compilateur pour recompiler le programme en instructions de bas niveau utilisées par la NPU. Comme l'utilisation de la mémoire et le temps d'exécution d'un programme varient en fonction de la compilation, un compilateur optimisé est nécessaire pour utiliser efficacement la NPU.

La NPU dispose d'une mémoire capable de stocker $M$ données, chaque emplacement mémoire étant numéroté de $0$ à $M-1$. La NPU prend en charge les trois types d'instructions suivants :

• a >> b
  • Copie la donnée a de l'hôte vers l'emplacement b de la mémoire. ($0 \le a < 1\,000\,000$ ; $0 \le b < M$). Si une donnée existe déjà, elle est écrasée.
• a << b
  • Copie la donnée de l'emplacement b de la mémoire vers l'emplacement a de l'hôte. ($0 \le a < 1\,000\,000$ ; $0 \le b < M$). Si une donnée existe déjà, elle est écrasée.
• o = w | m1 m2 ... ml
  • Calcule la sortie de l'opérateur w en utilisant les valeurs aux adresses mémoire m1, m2, ..., ml comme données d'entrée successives, et stocke le résultat à l'emplacement o de la mémoire.
  • L'emplacement de stockage de la donnée de sortie doit être différent de l'emplacement des données d'entrée. C'est-à-dire que $o \neq m_i$ ($1 \le i \le l$) doit être respecté.

Un programme NPU est une séquence des instructions ci-dessus ; lorsqu'il est exécuté, les instructions qui le composent sont exécutées séquentiellement.

L'efficacité d'un programme est déterminée par divers facteurs, mais un programme utilisant un nombre minimal d'instructions est généralement plus efficace. Étant donné une chaîne de caractères correspondant à <value>, convertissez-la en un programme NPU qui calcule la valeur de <value> et la stocke dans l'emplacement mémoire $0$, en utilisant le moins d'instructions possible.

Entrée

La première ligne contient la taille $M$ de la mémoire de la NPU. ($1 \le M \le 1\,000\,000$) La deuxième ligne contient la chaîne de caractères correspondant à <value> à calculer. La longueur de cette chaîne est inférieure ou égale à $1\,000\,000$.

Sortie

Si la mémoire de la NPU est insuffisante pour compiler le programme, affichez $-1$. Si le programme peut être compilé, affichez sur la première ligne le nombre minimal d'instructions nécessaires pour calculer <value>. À partir de la ligne suivante, affichez les instructions composant le programme, une par ligne, dans l'ordre. Tous les jetons d'une instruction sont séparés par un espace.

Si plusieurs solutions sont possibles, affichez-en n'importe laquelle.

Exemples

Exemples 1

7
71(72(41,42),73(43,44))

7
41 >> 3
42 >> 4
43 >> 5
44 >> 6
1 = 72 | 3 4
2 = 73 | 5 6
0 = 71 | 1 2

Exemples 2

3
71(72(41,42),73(43,44))

9
43 >> 2
44 >> 0
1 = 73 | 2 0
59 << 1
41 >> 2
42 >> 0
1 = 72 | 2 0
59 >> 2
0 = 71 | 1 2

Exemples 3

2
71(72(41,42),73(43,44))

-1