Sequência look-and-say

Dado um número n, uma sequência look-and-say (sequência de “olhar e dizer”) é gerada ao lermos os dígitos de n na ordem em que aparecem. Assim, se o número n for 43556777, lemos da seguinte forma:

• Um 4 (14)

• Um 3 (13)

• Dois 5 (25)

• Um 6 (16)

• Três 7 (37)

Logo, o próximo elemento na sequência, após o número 43556777, seria 1413251637.

Dado um número inicial n, a tarefa é calcular o número resultante após k etapas.

Input

A primeira linha da entrada contém o número inicial n (1 ≤ n ≤ ).

A segunda linha da entrada contém o número de etapas k (0 ≤ k ≤ 30).

Output

O programa deve imprimir o número resultante após k etapas na sequência look-and-say, iniciando com o número n.

Examples

Explicação

1. 6 → 16 → 1116 → 3116 → 132116

2. 33333 → 53