問題文

長さ $N = 30000$ の数列 $A$ が与えられます。$A$ には $1$ から $N$ までの整数が $1$ 回ずつ現れます。ここから、あなたは以下の操作を $K$ 回行います。

• 整数 $i, j, k, l, v (1 ≦ i ≦ j ≦ N, 1 ≦ k ≦ l ≦ N, 0 ≦ v ≦ N - 1)$ を指定する。$A_i, A_{i+1}, ... , A_{j}$ の値をそれぞれ $v$ 減少させ、 $A_k, A_{k+1}, ... , A_{l}$ の値をそれぞれ $v$ 増加させる。
• ただし、$A$ のすべての要素は常に $1$ 以上 $N$ 以下でなければならない。同じ値が複数出現することは許される。
• また、区間 \[i, j\] と区間 \[k, l\] に重複があってはならず、$2$ つの区間の長さは等しくなければならない。

あなたは、この操作により、$A$ の各要素の値を $A_1 = 1$, $A_2 = 2$, ... , $A_N = N$ にできるだけ近づけたいです。 値 $|A_1 - 1| + |A_2 - 2| + … + |A_N - N|$ ができるだけ小さくなるような手順を出力してください。

制約

• $N = 30000$
• $1000 ≦ K ≦ 3000$
• 与えられる $A$ は $1$ から $N$ までの整数のランダムな順列である。

入力

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

$N$ $K$ $A_1$ $A_2$ $:$ $A_N$

出力

$K$ 回の操作を以下の形式で出力せよ。

$i_1$ $j_1$ $k_1$ $l_1$ $v_1$ $i_2$ $j_2$ $k_2$ $l_2$ $v_2$ $:$ $i_K$ $j_K$ $k_K$ $l_K$ $v_K$

ここで、任意の $t$ に対し、$i_t≦j_t$ かつ $k_t≦l_t$ かつ $j_t - i_t = l_t - k_t$ を満たす必要がある。

採点方法

$1$ つのテストケースに対する点数は、生成された数列を $A$ として $1,000,000,000 - |A_1 - 1| - |A_2 - 2| - … - |A_N - N|$ 点となる。

テストケースは $41$ ケース与えられる。それぞれのテストケースについて、$K = 1000, 1050, 1100, …, 2950, 3000$ である。すべてのテストケースに対する点数の和が、その提出の得点となる。

なお、$1$ ケースでも出力が不正であった場合、example_01 以外の点数は全て $0$ 点となる。

入力例0

10 3
8
9
1
4
6
7
3
2
10
5

• この入力は制約を満たしません。

出力例0

1 2 7 8 6
7 7 5 5 4
5 5 10 10 5  

• 初期状態は ${8,9,1,4,6,7,3,2,10,5}$ です。以下次のように変化します。
• ${2,3,1,4,6,7,9,8,10,5}$
• ${2,3,1,4,10,7,5,8,10,5}$
• ${2,3,1,4,5,7,5,8,10,10}$

入力例1

入力ファイル例はこちらから(zip)

採点結果の「example_01」が、こちらのデータとなります。このデータも採点対象となります。 なお、example_01 は $K=2000$ のデータです。