#P18654. Kth Lex Min Min Min Subpalindromes

Kth Lex Min Min Min Subpalindromes

Kth Lex Min Min Min Subpalindromes

考虑所有长度为 nn、每个元素都是 11 到 mm 之间整数的数组。在这些数组中,一个数组包含的回文连续子数组数量最少能是多少?将这个最小值记为 PP。

保留所有恰好包含 PP 个回文连续子数组的数组,按字典序从小到大排序,请输出其中第 kk 个。

如果一个数组与自身反转后的数组相同,就称它为回文数组。连续子数组由一段连续下标确定;即使不同下标段的内容相同,也分别计数,长度为 11 的子数组也算回文。

两个不同数组按字典序比较时,找到第一个元素不同的位置,该位置元素较小的数组在前。

输入格式

一行三个整数 n,m,kn,m,k:

  • 1≤n≤1061\le n\le10^6;
  • 1≤m≤1061\le m\le10^6;
  • 1≤k≤10181\le k\le10^{18}。

输出格式

如果满足要求的数组不足 kk 个,输出 -1。

否则输出一行 nn 个整数,表示所求的第 kk 个数组。

样例输入 1

1 1 1

样例输出 1

1

样例输入 2

2 2 2

样例输出 2

2 1

样例输入 3

3 3 3

样例输出 3

2 1 3

样例输入 4

9 9 8244353

样例输出 4

2 4 1 2 6 8 1 2 7

样例输入 5

10 7 998244353

样例输出 5

-1

样例输入 6

3 1000 994253860

样例输出 6

998 244 353

说明

原题最后的文字是关于题名中“Min”数量的玩笑,不增加任何额外限制。