Una regla de sustitución describe cómo tomar una secuencia de símbolos y convertirla en una secuencia diferente de símbolos. Por ejemplo, ABA → BBB, es una regla de sustitución que significa que ABA se puede reemplazar con BBB. Usando esta regla, la secuencia AABAA se transformaría en la secuencia ABBBA (los símbolos sustituidos están en negrita).

En esta tarea, se le darán tres reglas de sustitución, una secuencia inicial de símbolos y una secuencia final de símbolos. Debe usar las reglas de sustitución para convertir la secuencia inicial en la secuencia final, utilizando un número específico de sustituciones.

Por ejemplo, si las tres reglas de sustitución fueran:

• AA → AB
• AB → BB
• B → AA

podríamos convertir la secuencia AB en AAAB en 4 pasos, mediante las siguientes sustituciones:

AB → BB → AAB → AAAA → AAAB,

donde los símbolos a reemplazar se muestran en negrita.

Entrada

Las primeras tres líneas contendrán las reglas de sustitución. Cada regla de sustitución será una secuencia de A y B, seguida de un espacio seguido de otra secuencia de A y B. Ambas secuencias tendrán entre uno y cinco símbolos.

La siguiente línea contiene tres valores separados por espacios, S, I y F. El valor \(S (1≤S≤6)\) es un número entero que especifica el número de pasos que se deben usar y los valores I (la secuencia inicial) y F ( la secuencia final) son secuencias de A y B, donde hay al menos uno y como máximo 5 símbolos en I y al menos uno y como máximo 50 símbolos en F.

Las siguientes L líneas contienen cada una un número entero positivo menor que 80, seguido de un espacio, seguido de un carácter (sin espacio).

Salida

La salida tendrá una longitud de S líneas y describe las sustituciones en orden.

La línea i de la salida contendrá tres valores separados por espacios, Ri, Pi y Wi:

• Ri es el número de la regla de sustitución (1, 2 o 3) que se utilizará.
• Pi es el índice de posición inicial de donde se aplicará la regla de sustitución en la secuencia. Observe que la cadena tiene un índice 1 (es decir, el primer carácter de la cadena está en el índice 1).
• Wi es la secuencia que resulta de esta sustitución. Específicamente, Wi es la secuencia de símbolos que resulta de aplicar la regla de sustitución Ri comenzando en la posición Pi de la secuencia previa de símbolos, Wi − 1, donde definimos W0 como la secuencia inicial I. Note que WS = F, la secuencia final .
• Siempre habrá al menos una secuencia de sustituciones S que convertirá I en F. Se garantiza que solo hay una secuencia válida en cada caso.

Ejemplo de Entrada 1

AA AB
AB BB
B AA
4 AB AAAB

Ejemplo de Salida 1

2 1 BB
3 1 AAB
3 3 AAAA
1 3 AAAB