AT_future2018career_a 増減ソート

[problemUrl]: https://atcoder.jp/contests/future-meets-you-contest-2018-open/tasks/future2018career_a 長さ $ 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 $ $ 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 $ を満たす必要がある。

### 制約 - $ N\ =\ 30000 $ - $ 1000\ ≦\ K\ ≦\ 3000 $ - 与えられる $ A $ は $ 1 $ から $ N $ までの整数のランダムな順列である。 ### 採点方法 $ 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 $ 点となる。 ### Sample Explanation 1 \- この入力は制約を満たしません。 - 初期状態は $ {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} $ ### Sample Explanation 2 \[入力ファイル例はこちらから(zip)\](https://img.atcoder.jp/future-meets-you-contest-2018/4819071aa4e6deb1dbccddaa33fb8d5a.zip) 採点結果の「example\\\_01」が、こちらのデータとなります。このデータも採点対象となります。 なお、example\\\_01 は $ K=2000 $ のデータです。