Código de Compressão

Em computação, compressão de arquivos é o processo de reduzir o tamanho de arquivos. Uma técnica simples mas eficiente de compressão para alguns tipos de arquivos é RLE, cujo o nome é derivado das letras iniciais do nome em inglês, que pode ser traduzido por codificação por comprimento de repetições.

Em RLE, cada sequência de valores repetidos no arquivo é substituída pelo número de repetições seguido do valor a ser repetido. Por exemplo, a sequência ‘AAAAAA’ seria substituída por ‘6 A’. Se o arquivo tem muitas sequências de valores repetidos, a técnica RLE é bem eficiente (por exemplo, considere um arquivo de imagem branco e preto em que grande parte dos valores é branco). Por outro lado, se o arquivo não possui muitas repetições, a técnica RLE pode aumentar o tamanho do arquivo, ao invés de diminuir.

Nesta tarefa, dada uma cadeia de caracteres, você deve escrever um programa que produza a sequência de caracteres comprimida com a técnica RLE.

Entrada

A primeira linha contém um inteiro $N$, o comprimento da cadeia de caracteres. A segunda linha contém a cadeia de caracteres, com $N$ caracteres $C_i$.

Saída

Seu programa deve produzir uma única linha, contendo a cadeia de caracteres codificada com a técnica RLE. A codificação consiste em uma sequência de pares, separados por espaços, em que cada par é um inteiro (indicando o número de repetições), seguido de um espaço, seguido do caractere a ser repetido.

Restrições

• $1 \leq N \leq 1\ 000$
• $C_i$ é uma letra, maiúscula ou minúscula, não acentuada.

Informações sobre a pontuação

A tarefa vale $100$ pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:

• Subtarefa 1 (21 pontos): Não há repetições na cadeia de entrada (veja exemplo 2).
• Subtarefa 2 (23 pontos): $C_i =$ ‘a’ ou $C_i =$ ‘b’ para todo $i$ (veja exemplo 3).
• Subtarefa 3 (56 pontos): Nenhuma restrição adicional.

Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.

Exemplos

Exemplo de entrada 1

8
TAAAAxxx

Exemplo de saída 1

1 T 4 A 3 x

Explicação do exemplo 1: o primeiro caractere da cadeia, ‘T’, não tem repetição e portanto sua codificação é o par ‘1 T’. A seguir na cadeia de caractere aparecem quatro caracteres ‘A’ repetidos, e portanto a codificação dessa sequência é o par ‘4 A’. Finalmente na cadeia de caractere aparecem três caracteres ‘x’ repetidos, e portanto a codificação dessa sequência é o par ‘3 x’. Os pares devem ser separados por um espaço em branco, e portanto a resposta é ‘1 T 4 A 3 x’.

Exemplo de entrada 2

4
XYZX

Exemplo de saída 2

1 X 1 Y 1 Z 1 X

Exemplo de entrada 3

21
aaaaaaaaaabbbbbbbbbbb

Exemplo de saída 3

10 a 11 b