Combination Lock

Interview

Time limit2sMemory limit1024 MB

Summary

Given an n-digit number m in base k, find the smallest larger n-digit number in base k with the same digit sum, or report that none exists.

Level: Medium5 of 10
Topics: Greedy, Math
Solved: No attempts yet

Problem

Vasya really likes using combination locks. A combination lock has a drum with several rings. Each ring has several positions, and each position corresponds to a digit in base $k$ . So the state of a lock with $n$ rings can be written as an $n$ -digit number in base $k$ . The lock opens in only one fixed state.

Because codes are easy to forget, Vasya uses a trick. After locking the lock, he turns it so that its number is the previous one (in increasing order) among all numbers with exactly the same digit sum as the number that opens the lock.

To open the lock, Vasya only needs to find the next number (in increasing order) with the same digit sum as the current one. That number opens the lock.

After a month of using this lock, Vasya got tired of solving this tricky problem by hand every time, so he asked you for help.

Write a program that, given a number $m$ in base $k$ , finds the next number (in increasing order) in the same base with the same digit sum.

Input

The first line contains two natural numbers $k$ and $n$ ( $2 \le k \le 36$ ). The second line contains the number $m$ in base $k$ . It has $n$ digits and no leading zeros. Digits 10 to 35 are written as the uppercase Latin letters A to Z. The number $m$ does not exceed $100000$ .

Output

Print the answer: the required number in base $k$ with exactly $n$ digits and no leading zeros. If Vasya made a mistake and no such number exists, print the single word <<Impossible>>.

Examples3

Example 1
Input
```
10 2
23
```
Expected output
```
32
```
Example 2
Input
```
16 2
FF
```
Expected output
```
Impossible
```
Example 3
Input
```
26 2
HP
```
Expected output
```
IO
```