如您所知,伯兰的所有孩子都喜欢玩立方体。小彼佳有 n 座由相同大小的立方体组成的塔。编号为 i 的塔由一个叠放在另一个顶部的 ai 立方体组成。 Petya 将一组塔的不稳定性定义为等于最高塔和最低塔的高度之差的值。例如,如果 Petya 建造了五个高度为 (8, 3, 2, 6, 3) 的立方体塔,则该组塔的不稳定性等于 6(最高的塔的高度为 8,最低的塔的高度为 2)。
男孩希望他的塔组的不稳定性尽可能低。他所能做的就是多次执行以下操作:从某个塔中取出顶部的立方体并将其放在他的集合中的其他塔的顶部。请注意,Petya 永远不会将立方体放在其被移除的同一座塔上,因为他认为这是浪费时间。
在上学之前,男孩将有时间执行不超过 k 个这样的操作。 Petya不想上课迟到,所以你必须帮助他完成这项任务。
输入
第一行包含两个以空格分隔的正整数 n 和 k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1000) — 给定集合中塔的数量以及 Petya 可以执行的最大操作数。第二行包含 n 个空格分隔的正整数 ai (1 ≤ ai ≤ 104) — 塔的初始高度。
输出
在第一行中打印两个空格分隔的非负整数 s 和 m (m ≤ k)。第一个数字是执行最多 k 个操作后可以获得的最小可能的不稳定性值,第二个数字是所需的操作数。
在接下来的 m 行中,将每个操作的描述打印为两个正整数 i 和 j,每个都在 1 到 n 的范围内。它们表示 Petya 从第 i 个塔中取出顶部的立方体并放入第 j 个塔中(i ≠ j)。请注意,在执行操作的过程中,某些塔的高度可能会为零。
如果存在多个正确的序列,并且可以实现最小可能的不稳定性,则允许打印其中任何一个。
示例
输入 #1
3 2 5 8 5
输出 #1
0 2 2 1 2 3
输入 #2
3 4 2 2 4
输出 #2
1 1 3 2
输入 #3
5 3 8 3 2 6 3
输出 #3
3 3 1 3 1 2 1 3
注意
在第一个示例中,您需要将立方体移动两次,从第二个塔到第三个塔,从第二个塔到第一个塔。那么塔的高度都相同并且等于6。