Consider sequences of numbers. The first sequence consists of one number K. Each next sequence of numbers describes the previous one according to this rule.
We look through the described sequence from left to right and divide it into segments consisting of consecutive equal numbers (moreover, we always combine all identical numbers in a row into one segment). Further, each such segment is described by two numbers — the first number tells how many times the same number is repeated, the second number tells which number is repeated. We write these pairs sequentially in accordance with the segments from left to right, and we get a new sequence (see examples below).
For example, for K=2, the sequences will look like this:
| # |
Sequence |
How to read it (the words in the description correspond to the numbers of the current sequence from left to right, and describe the previous sequence) |
| 1 |
2 |
Source sequence |
| 2 |
1 2 |
One "two" |
| 3 |
1 1 1 2 |
One "one", one "two" |
| 4 |
3 1 1 2 |
Three 1s, one 2 |
| 5 |
1 3 2 1 1 2 |
One 3, two 1s, one 2 |
| 6 |
1 1 1 3 1 2 2 1 1 2 |
One 1, one 3, one 2, two 1s, one 2 |
Write a program that, given the initial number K, will print the Nth resulting sequence.
Input
The number K (1 ≤ K ≤ 9) and the number N (1 ≤ N ≤ 15) are entered.
Imprint
Your program should print the Nth sequence obtained from the initial sequence consisting of a single number K. The numbers should be separated by spaces when outputting.
Examples
| # |
Input |
Output |
| 1 |
2
6 |
1 1 1 3 1 2 2 1 1 2 |
| 2 |
2
1 |
2 |
| 3 |
1
3 |
2 1 |