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.

The 2023 ICPC Training Camp powered by Huawei. Day 1: Um_nik mod 998 244 353 Contest.