O arquivo de entrada consiste de vários conjuntos de duas sequencias de caracteres. Cada conjunto consiste em uma linha contendo duas strings do alfabeto Ingles com no máximo n e m caracteres, respectivamente. As duas strings podem estar separadas por um ou mais espacos em branco. Um conjunto em que as duas strings sao "#" indica o final do arquivo. Cada caracter das strings serao minusculos como no exemplo abaixo.

OBS: 0 <= n <= 100 e 0 <= m <= 100, n pode ser diferente de m

Entrada exemplo:

abcdefg abcdeh
bcd abcde
abcde bcgfe
# #
 

Para cada conjunto, voce deve imprimir uma serie de linhas. Na primeira linha, imprima o numero do conjunto, como mostrado na saida exemplo. Na proxima linha imprima o custo "c" mínimo de edicao e nas proximas linhas quais os passos para transformar a cadeia A na cadeia B com este custo.

Os passos podem ser:
R c n - replace A[n] por c;
M c n - ocorreu match de c na posicao n de A;
D c n - delete c da posicao n de A;
I c n - insert c na posicao n de A.

Os passos devem ser apresentados na ordem inversa (como são identificados pelo retrocesso na matriz). Quando houver mais de uma possibilidade de movimento, a escolha deve obedecer à seguinte ordem de prioridades: (1) Match/Substituição, (2) Remoção, (3) Inserção.

Exemplo:

----------------
     A | B
----------------
M e 5 abcde  | bcgfe
I f 5 abcde  | bcgf
R g 4 abcdfe | bcg
M c 3 abcgfe | bc
M b 2 abcgfe | b
D a 1 abcgfe |
bcgfe | <-- A se transformou em B
 

Saida exemplo correspondente a entrada acima:
Conjunto #1
2
R h 7
D f 6
M e 5
M d 4
M c 3
M b 2
M a 1

Conjunto #2
-1
I e 4
M d 3
M c 2
M b 1
I a 1

Conjunto #3
-2
M e 5
R f 4
I g 4
M c 3
M b 2
D a 1
 
 

O arquivo de entrada consiste de vários conjuntos de duas sequencias de caracteres. Cada conjunto consiste em uma linha contendo duas strings do alfabeto Ingles com no máximo n e m caracteres, respectivamente. As duas strings podem estar separadas por um ou mais espacos em branco. Um conjunto em que as duas strings sao "#" indica o final do arquivo. Cada caracter das strings serao minusculos como no exemplo abaixo.

OBS: 0 <= n <= 100 e 0 <= m <= 100, n pode ser diferente de m

Entrada exemplo:

abca bcab
x b
# #

Para cada conjunto, voce deve imprimir tres linhas. Na primeira linha,
imprima o numero do conjunto, como mostrado na saida exemplo. Na segunda,
imprima uma maior subsequencia das duas sequencias e na terceira, uma menor
supersequencia. Caso alguma das subsequencias ou supersequencias for
vazia, imprima uma linha em branco.

Saida exemplo correspondente a entrada acima:

Conjunto #1
bca
abcab

Conjunto #2

xb