You are given a binary array \(A\) with elements \(0\) and \(1\) of size \(N\), and integer \(K\). Let's call the score of an array the difference between the maximum and minimum element within the array. For example \([1,0,0,1,0,0]\), the Score of this given array is \(1-0 = 1\).

Now you have to partition the array into \(K\) continuous subarrays such that the summation of the score of all the subarrays is minimum. You also have to output starting and ending points of the subarrays corresponding to the minimum score, in increasing order of starting point. If there are multiple possibilities then output the subarrays such that starting points will be lexicographically smallest.

Input format

• The first line contains two space-separated integers \(N\), and \(K\) denoting the size of the array and the number of subarrays in which you have to divide the array respectively.
• The second line contains \(N\) space-separated integers denoting array \(A\).

Output format

• In the first line print the minimum score.
• Then print \(K\) lines, each line will contain starting and ending points of the subarray.

Constraints

• \( 2 \leq N \leq 10^6 \)
• \(1 \leq K \leq N\)