28199번 - Kth Lex Min Min Min Subpalindromes 다국어

Consider all arrays with length $n$ consisting of integers from $1$ to $m$. Let $P$ be the minimum number of continuous subarrays that are palindromic one such array can have. Recall that an array is palindromic if it is equal to its own reverse.

Find the $k$-th lexicographically minimal array with $P$ continuous subarrays that are palindromic. We are still only considering arrays with length $n$ consisting of integers from $1$ to $m$.

In other words, let's take all arrays with length $n$ consisting of integers from $1$ to $m$, leave only those of them that have the minimum number of continuous subarrays that are palindromic, and sort them lexicographically. Your task is to find $k$-th of them in this order.

The only line of input 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}$).

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

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