Equalizing Consecutive Block Columns

Byteasar once arranged his building blocks into n columns of varying heights. He then selected an integer k and attempted to make k consecutive columns equal in height by adding blocks to, or removing blocks from, the top of any column. Each move consists of either placing one block onto a column (there is an unlimited supply) or removing one block from the top of a column.

Your task is to determine an optimal (i.e. minimum number of moves) sequence of moves to achieve that some segment of k consecutive columns all have the same height. In doing so, you are allowed to adjust only the columns in the chosen segment; the other columns remain unchanged.

The optimal target height for a segment is the integer median of the segment’s heights. (When k is even, you may choose the lower median, i.e. the element at index \(\lfloor\frac{k-1}{2}\rfloor\) of the sorted segment.)

Input Format: Two lines. The first line contains two integers n and k (with \(1 \le k \le n\)). The second line contains n space-separated non-negative integers representing the initial heights of the columns.

Output Format: The first line should output the minimum number of moves required. Each of the following lines should describe one move in the format:

column_index operation

Where column_index is the 1-indexed position of a column within the array, and operation is either add or remove representing the action taken (adding a block or removing a block, respectively).

inputFormat

The input consists of two lines:

• The first line contains two integers n and k separated by a space.
• The second line contains n non-negative integers separated by spaces, representing the heights of the columns.

outputFormat

The output begins with a single integer m, the minimum number of moves required. This is followed by m lines, each describing a move. A move is represented by two tokens: the 1-indexed column number and the operation (add or remove).

If no moves are necessary, output 0 on the first line and nothing else.

sample

5 3
3 1 2 2 2

0