P - Make Testcase Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

Universal Cup 参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

PCT 君は次のような問題を作りました。

Shuffle and Increasing

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

A を並び替えて得られる列のうち、A_i < A_{i+1} を満たす i がちょうど M 個あるものの個数を 998244353 で割ったあまりを求めてください。

制約
  • 1 \le N \le 30
  • 0 \le M \le N-1
  • 1 \le A_i \le N

PCT 君は上記の問題で答えが X になる入力を作りたいです。そのような入力が存在するか判定し、存在するならば 1 個構築してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \le T \le 10^4
  • 0 \le X < 998244353

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

ここで、\mathrm{case}_i とは i 個目のテストケースである。それぞれのテストケースは以下の形式で与えられる。

X

出力

T 個のテストケースへの出力を改行区切りで出力せよ。

それぞれのテストケースについては、もし条件を満たす入力が存在しないならば -1 を、するならば以下のように出力せよ。

N M
A_1 A_2 \dots A_N

入力例 1

4
4
131
333854876
620963539

出力例 1

4 2
1 3 3 2
6 3
6 2 6 4 5 1 
17 10
8 7 1 14 8 5 12 5 2 17 7 16 15 17 14 15 6 
24 14
16 8 14 18 15 16 21 4 10 14 3 4 22 8 16 11 22 17 11 5 12 2 13 18

1 個目のテストケースについて、A を並び替えて得られる列のうち条件を満たすものは以下の 4 個です。よってこの入力は条件を満たしています。

  • (1,2,3,3)
  • (1,3,2,3)
  • (2,3,1,3)
  • (3,1,2,3)