题目描述

有 $n$ 个必须按编号顺序完成的任务，第 $i$ 个任务需要 $t_i$ 个单位时间。现有 $k$ 名研究员，每名研究员可以领取一段编号连续的任务，也可以不领取任务；每个任务必须且只能分配给一名研究员。

所有研究员可以同时工作。一名研究员的完成时间为他所领取任务的总用时，整个项目的完成时间为所有研究员完成时间的最大值。

请在项目完成时间最短的分配方案中，按照研究员编号从大到小依次分配：每名研究员从尚未分配的任务末尾开始，在不超过最短项目完成时间的条件下尽可能多地领取连续任务。

输出所有非空任务区间，并按区间起点从小到大排列。

输入格式

第一行包含两个整数 $n,k$，分别表示任务数量和研究员数量。

第二行包含 $n$ 个整数 $t_1,t_2,\ldots,t_n$，其中 $t_i$ 表示第 $i$ 个任务所需的时间。

输出格式

输出若干行，每行包含两个整数 $l,r$，表示一名研究员领取编号从 $l$ 到 $r$ 的所有任务。

所有区间按 $l$ 从小到大输出。未领取任务的研究员不需要输出。

9 3
1 2 3 4 5 6 7 8 9

1 5
6 7
8 9

数据范围与提示

• $1 \le k \le n \le 10^5$
• $1 \le t_i \le 1000$