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.