外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

S - Power PAKUPAKU Warp Device

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、tau0529、trueryob

配点 525 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

わりとねこくんは、11 から NN までの番号がついた NN 個のワープ装置を開発しました。

装置 ii の飛び先を AiA_i とします。わりとねこくんは、(A1,A2,…,AN)(A_1, A_2, \dots, A_N) が (1,2,…,N)(1, 2, \dots, N) の順列になるように飛び先を設定できます。Ai=iA_i=i と設定することもできます。

装置 uu を起動すると、わりとねこくんは装置 AuA_u に移動します。このとき、移動先の番号に等しい AuA_u だけ電力を消費します。

わりとねこくんは装置 11 から出発し、設定した飛び先に従ってちょうど MM 回ワープします。MM 回目のワープで装置 11 に戻り、かつ MM 回のワープで消費する電力の総和がちょうど WW になるような設定を 11 つ求めてください。途中で装置 11 に戻っても構いません。

より厳密には、v0=1v_0=1 とし、1≤t≤M1 \le t \le M に対して vt=Avt−1v_t=A_{v_{t-1}} とします。次の条件を両方満たす順列 (A1,A2,…,AN)(A_1,A_2,\dots,A_N) を求めてください。

  • vM=1v_M=1
  • ∑t=1Mvt=W\sum_{t=1}^{M}v_t=W

制約

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤M≤1091 \le M \le 10^9
  • M≤W≤M×NM \le W \le M \times N
  • 入力はすべて整数

入力

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

NMWN \quad M \quad W

出力

条件を満たす設定が存在しない場合は、-1 を 11 行に出力してください。

存在する場合は、A1,A2,…,ANA_1,A_2,\dots,A_N を空白区切りで 11 行に出力してください。条件を満たす設定が複数ある場合は、どれを出力しても構いません。

入力例 1

4 6 12

出力例 1

3 2 1 4

装置 11 から出発すると、3,1,3,1,3,13,1,3,1,3,1 の順に到着します。66 回目のワープで装置 11 に戻り、消費する電力の総和は 3+1+3+1+3+1=123+1+3+1+3+1=12 となり、これは WW と等しいので条件を満たしています。

入力例 2

3 4 5

出力例 2

-1

入力例 3

6 6 20

出力例 3

3 2 6 4 5 1

スペシャルジャッジ問題です。

参加受付は終了しました。