题目描述

有m本按顺序编号的书，需要分给k个人同时抄写。每个人的抄写速度相同，每本书只能由一个人抄写。每个人必须分到至少一本书，且分到的书的编号必须连续。

总完成时间由抄写页数最多的人决定，请使最大抄写页数尽可能小。若最优方案有多个，优先使第1个人抄写页数最少；仍有多个则使第2个人最少，依此类推。

输入格式

第一行两个整数m、k。第二行m个正整数，依次表示各本书的页数。

输出格式

输出k行，每行两个整数，表示对应的人抄写的书的起始编号和终止编号。按起始编号从小到大输出，方案须满足题目中的最优和优先级要求。

样例

9 3
1 2 3 4 5 6 7 8 9

1 5
6 7
8 9

数据范围

1≤k≤m≤500；每本书页数为1至10000。