Problem Description

You are given a sequence $ A $ of length $ N = 30000 $. The sequence $ A $ contains each integer from $ 1 $ to $ N $ exactly once. You are allowed to perform the following operation $ K $ times:

• Specify integers $ i, j, k, l, v $ such that $ 1 ≦ i ≦ j ≦ N, 1 ≦ k ≦ l ≦ N, 0 ≦ v ≦ N - 1 $. Decrease each value in $ A_i, A_{i+1}, ..., A_{j} $ by $ v $ and increase each value in $ A_k, A_{k+1}, ..., A_{l} $ by $ v $.
• However, all elements of $ A $ must always be between $ 1 $ and $ N $ inclusive. Duplicate values are allowed.
• The intervals $ [i, j] $ and $ [k, l] $ must not overlap, and the lengths of these two intervals must be equal.

Your goal is to get as close as possible to the sequence $ A_1 = 1, A_2 = 2, ..., A_N = N $ by performing these operations. Output the steps to make the value $ |A_1 - 1| + |A_2 - 2| + … + |A_N - N| $ as small as possible.

Input Format

The input is given in the following format:

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

Output Format

Output the $ K $ operations in the following format:

$ 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 $

Here, for any $ t $, it must satisfy $ i_t ≦ j_t $ and $ k_t ≦ l_t $ and $ j_t - i_t = l_t - k_t $.

Sample Input and Output

Sample Input #1

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

Sample Output #1

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

Sample Input #2

Sample Output #2

None

Notes/Hints

Constraints

• $ N = 30000 $
• $ 1000 ≦ K ≦ 3000 $
• The given $ A $ is a random permutation of integers from $ 1 $ to $ N $.

Scoring Method

The score for one test case is calculated as $ 1,000,000,000 - |A_1 - 1| - |A_2 - 2| - … - |A_N - N| $.

There are $ 41 $ test cases provided, each with $ K = 1000, 1050, 1100, …, 2950, 3000 $. The sum of the scores for all test cases is the score for the submission.

If the output is incorrect for even one test case, the score for all test cases except example_01 will be $ 0 $.

Sample Explanation 1

• This input does not satisfy the constraints.
• The initial state is $ {8,9,1,4,6,7,3,2,10,5} $. It changes as follows:
• $ {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

Input file example is available here (zip)
The scoring result for example_01 corresponds to this data. This data is also part of the scoring. Note that example_01 has $ K = 2000 $.

见题面 Input 部分

见题面 Output 部分