Kth Lex Min Min Min Subpalindromes

Time limit3sMemory limit1024 MB

Summary

Find the k-th lexicographically smallest length-n array over 1 to m that has the fewest palindromic subarrays, or print -1 if there are fewer than k such arrays.

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

Problem

Consider all arrays of length $n$ whose elements are integers from $1$ to $m$ . Let $P$ be the minimum number of contiguous subarrays that are palindromic that such an array can have. An array is palindromic if it is equal to its own reverse.

From all arrays of length $n$ with integers from $1$ to $m$ , keep only those that have the minimum number of palindromic contiguous subarrays, and sort them lexicographically. Find the $k$ -th array in this order.

Input

The only line contains three integers $n$ , $m$ , and $k$ ( $1 \le n \le 10^6$ , $1 \le m \le 10^6$ , $1 \le k \le 10^{18}$ ).

Output

If there are fewer than $k$ valid arrays, print -1. Otherwise, print the $k$ -th lexicographically smallest of them.

Hint

Did we put the minimum number of min in the title? Min.

Examples5

Example 1
Input
```
1 1 1
```
Expected output
```
1
```
Example 2
Input
```
2 2 2
```
Expected output
```
2 1
```
Example 3
Input
```
3 3 3
```
Expected output
```
2 1 3
```
Example 4
Input
```
9 9 8244353
```
Expected output
```
2 4 1 2 6 8 1 2 7
```
Example 5
Input
```
10 7 998244353
```
Expected output
```
-1
```