Circulating Stones

問題文

円周上に $N$ 個の箱が並んでおり、時計回りに $1,2,\ldots,N$ の番号が付いています。箱 $1$ と箱 $N$ も隣り合っています。

はじめ、箱 $i$ には $A_i$ 個の石が入っています。次の操作を好きな回数行うことができます。

• 石が 2 個以上 入っている箱を 1 つ選び、その箱から石を 2 個取り出して、両隣の箱に 1 個ずつ入れる。

すべての箱 $i$ の石の個数を $B_i$ 個にできるか判定してください。

できる場合は、以下で説明する形式で操作手順を 1 つ出力してください。

操作手順の表し方

操作手順は、いくつかの ブロック に分けて出力します。

1 つのブロックは、正整数 $q$ と、相異なる箱番号の列 $(v_1,v_2,\ldots,v_m)$ で表します。このブロックは、箱 $v_1,v_2,\ldots,v_m$ をこの順に 1 回ずつ操作することを、$q$ 回繰り返すことを意味します。

ブロックは出力された順に実行します。なお、どの操作でも、操作する直前にその箱に石が 2 個以上入っている必要があります。

出力する操作手順は、次の条件をすべて満たさなければなりません。

• ブロック数 $K$ は $0\le K\le N-1$ を満たす。
• 各ブロックについて、$1\le q\le 10^{18}$、$1\le m\le N$ を満たす。
• 各ブロックの箱番号は $1$ 以上 $N$ 以下であり、同じブロック内に重複はない。
• すべてのブロックにおける $m$ の総和は $\dfrac{N(N-1)}2$ 以下である。

目標の配置にできる場合、上記の条件を満たす操作手順が必ず存在することが保証されます。

制約

• $3\le N\le 2000$
• $0\le A_i,B_i\le 10^9$
• 入力はすべて整数

入力

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

出力

目標の配置にできない場合は、-1 を出力してください。

できる場合は、次の形式で出力してください。

ここで、$q_j$ は $j$ 番目のブロックの反復回数、$m_j$ はそのブロックに含まれる箱の個数を表します。

条件を満たす出力が複数ある場合、どれを出力しても正解です。

入力例 1

5
0 0 4 0 0
1 0 2 0 1

出力例 1

2
1 1 3
1 3 3 2 4

箱 $3,3,2,4$ の順に操作します。石の個数は次のように変化します。

(0,0,4,0,0)
(0,1,2,1,0)
(0,2,0,2,0)
(1,0,1,2,0)
(1,0,2,0,1)

入力例 2

5
1 1 1 2 1
0 0 2 2 2

出力例 2

-1

操作を行うことはできますが、目標の配置にはできません。

入力例 3

3
1000000000 0 0
0 500000000 500000000

出力例 3

1
500000000 1 1

箱 $1$ を $500000000$ 回操作することで、目標の配置になります。

入力例 4

4
0 7 0 3
0 7 0 3

出力例 4

0

最初から目標の配置になっているため、操作は必要ありません。

入力例 5

4
2 0 0 0
1 1 0 0

出力例 5

-1