D - Stick Combination Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : {200}

問題文

長さが 1,3,5,7,...,2N-1 の棒がそれぞれ 1 本ずつ、合計 N 本の棒があります。

あなたは棒売りから、店で売るために棒を接着剤で繋げて棒の長さを揃えるよう頼まれました。

接着後に 2 本以上の棒が残り、接着後に残る全ての棒の長さが等しくなるような棒の接着方法を一つ出力してください。

そのような接着方法が存在しない場合はimpossibleを出力してください。

ただし複数の棒を接着するとき、接着後の棒の長さは接着に使用した棒の長さの和になり、棒を捨てることや切断することはできません。

制約

  • 入力は全て整数である。
  • 2 \leq N \leq 10^5

入力

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

N

出力

問題文の条件を満たす接着方法が存在する場合は 1 行目に接着後に残る棒の本数 M を、続く m + 1 (1 \leq m \leq M) 行目の先頭に m 番目の棒を作るため接着する棒の本数 l_m を、同じ行に m 番目の棒を作るため接着する棒の長さ x_{m,i} (1 \leq i \leq l_m) を空白区切で l_m 個出力せよ。

なお,問題文中の条件を満たす接着の組み合わせが複数存在する場合は、そのうちのどれを出力しても構わない。

条件を満たす接着方法が存在しない場合はimpossibleを出力せよ。

  • 2 \leq M \leq N
  • 1 \leq l_m \leq N (1 \leq m \leq M)
  • \sum_{m}{l_m} = N
  • x_{m,i} \in \{1, 3, 5, ..., 2N-1\} (1 \leq i \leq l_m)
  • x_{m,i} は相異なる。
  • \sum_{i}{x_{1,i}} = \sum_{i}{x_{2,i}} = ... = \sum_{i}{x_{M,i}}
  • 出力は全て整数で行うこと。
M
l_1 x_{1,1} x_{1,2} ... x_{1,l_1}
l_2 x_{2,1} x_{2,2} ... x_{1,l_2}
:
l_M x_{M,1} x_{M,2} ... x_{M,l_M}

入力例 1

4

出力例 1

2
2 1 7
2 3 5

長さ 1,3,5,7 の棒を 1, 73, 5 に分けてそれぞれ接着すると、長さ 8 の棒が 2 つ得られ、これは条件を満たします。


入力例 2

2

出力例 2

impossible

長さ 1 と長さ 32 本をどのように接着しても、同じ長さの 2 本以上の棒になりません。


入力例 3

3

出力例 3

impossible

長さ 1,3,53 本しかない場合も条件を満たす接着方法が存在しません。