Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
106 - ZOJ Monthly, May 2011 - F
Yet Another Set of Numbers

Time Limit: 2 Seconds      Memory Limit: 65536 KB

You are given yet another set of numbers. The numbers in this set obey these rules:

  1. Each number will start with a non-zero digit.
  2. Each number contains at most N digits and only 0, 1, 2 and 3 are available.
  3. All the adjacent digits won't be the same (e.g. 301 is legal while 300 is illegal).
  4. The comparison is the same as strings (e.g. 1 < 123 < 20 < 21 < 3).

Given a number B belonging to this set, you have to find out the number A such that there are exactly K-1 numbers larger than A and smaller than B in this set.

Input

Input contains multiple test cases.

The first line of each test case contains two integers 0 < N < 20 and K > 0. The second line contains only a number B. It's guaranteed that the solution exists

Output

For each case, output the number A in a single line.

Sample Input

2 5
3
5 50
12301

Sample Output

13
1021

Hint

In the first case, there are 12 numbers in the set. And they are sorted in following order:
1 < 10 < 12 < 13 < 2 < 20 < 21 < 23 < 3 < 30 < 31 < 32


Author: MO, Luyi
Submit    Status