405956: GYM102191 G Next Number

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Next Numbertime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a number with n digits written in base b. For example, our monetary system is written in base 10 (i.e. 926 JOD) and a binary number is written in base 2 (i.e. 10101110).

Your task is to find the next greater number that consists of distinct digits (no digit is repeated twice).

It is guaranteed that there is an answer for the given number.

Input

The first line of input contains two integers n and b (1 ≤ n ≤ 3 × 105) (2 ≤ b ≤ 3 × 105), the number of digits of the number and the base it is written in.

The second line of input contains n integers ai (0 ≤ ai < b), where ai is the ith digit in the number. It is guaranteed that the number has no leading zeros.

Output

Output a single line with the next greater number that consists of distinct digits. Separate the digits by a single space.

ExamplesInput
3 10
9 2 6
Output
9 2 7 
Input
4 11
10 5 5 1
Output
10 5 6 0 
Input
4 4
3 2 0 1
Output
3 2 1 0 
Input
2 5
4 3
Output
1 0 2 

加入题单

上一题 下一题 算法标签: