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
- 6 → 16 → 1116 → 3116 → 132116
- 33333 → 53
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB