405956: GYM102191 G Next Number

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.

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

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

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

3 10
9 2 6

9 2 7 

4 11
10 5 5 1

10 5 6 0 

4 4
3 2 0 1

3 2 1 0 

2 5
4 3

1 0 2