Algorithms and Data Structures

Look-and-say sequence

Having a number n, a look-and-say sequence is generated by reading the digits of n as they appear in the number. So, if the number n is 43556777, we would read it as:
  • One 4 (14)
  • One 3 (13)
  • Two 5s (25)
  • One 6 (16)
  • Three 7s (37)
So, the next element in the sequence following the number 43556777, would be 1413251637.
Given an initial number n, you are asked to calculate the resulting number after k steps.

Input

The first line of the input contains the initial number n (1 ≤ n ≤ ).
The second line of the input contains the number of steps k (0 ≤ k ≤ 30).

Output

The program should print the resulting number after k steps in the look-and-say sequence when starting with the number n.

Examples

Input
Output
6 4
132116
33333 1
53

Explanation

  1. 6 → 16 → 1116 → 3116 → 132116
  1. 33333 → 53
 

Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in