O arquivo de entrada consiste de varios conjuntos de dados. Cada conjunto consiste em uma linha contendo duas strings do alfabeto Ingles de mesmo comprimento "n" separadas por um ou mais espacos em branco. Um conjunto em que as duas strings sao "#" indica o final do arquivo.

OBS: 0 <= n <= 5000

Entrada exemplo:
abcd dabc
a a
adcdefg nmhrtdt
mtrsu trsum
# #

Para cada conjunto, voce deve imprimir duas linhas. Na primeira linha, imprima o numero do conjunto, como mostrado na saida exemplo. Na proxima linha imprima um inteiro k, se existe 0 <= k <= n-1 tal que ai = b[(k+i) mod n], para todo i de 0 a n-1, caso contrario deixe a llinha em branco.

Saida exemplo correspondente à entrada acima:
Conjunto #1
1

Conjunto #2
0

Conjunto #3
 

Conjunto #4
4
 

Obs.:

* O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.
 
 

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 caracteres. As duas strings podem estar separadas por um ou mais espacos em branco. A primeira string e' o texto e a segunda e' o padrao. Um conjunto em que as duas strings sao "#" indica o final do arquivo.

Considere que 0 <= n <= 5000.

Entrada exemplo:
xyxxyxyxyyxyxyxxxyxx xyxyyxyxyxx
aabbaabab aba
# #
 

Para cada conjunto, voce deve imprimir tres linhas. Na primeira linha, imprima o numero do conjunto, como mostrado na saida exemplo. Na segunda, imprima "s" se o padrao ocorre no texto ou "n" se o padrao nao ocorre no texto. Na terceira, imprima o numero de comparacoes.
 

Saida exemplo correspondente à entrada acima:
Conjunto #1
s
16

Conjunto #2
s
8

Obs.:

* O formato dos arquivos de saída deverá seguir EXATAMENTE o padrão estabelecido nos exemplos acima.
 
 

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.

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
D g 7
R h 6
M e 5
M d 4
M c 3
M b 2
M a 1

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

Conjunto #3
3
M e 5
I f 5
R 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