复制书稿问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在复印机发明之前,复制一本书是非常困难的,书中的所有内容只能请抄写员用手工重新抄写。一个抄写员要完成复制一本书的工作,往往需要几个月的时间。15世纪中期有一个著名的抄写员名叫Xerox。但是无论如何,复制书稿这种工作是非常令人讨厌的,而提高复制速度的惟一方法只能是雇佣更多的抄写员。

很久以前,有一个戏院的艺术团准备演出一场著名的古代悲剧,这个古代悲剧的原著被分成了许多本书。显然,表演者需要这些书稿的副本,所以,他们雇佣了许多抄写员来复制这些书稿。现在请你主持复制工作,假设你有m本书(编号为1,2,...,m),想将这些书每本复制一份,m本书的页数有可能不同(页数分别是P1,P2,...,Pm)。你的任务是将这m本书分给k个抄写员(k<=m),每本书只能分配给一个抄写员进行复制,而每个抄写员所分配到的书必须是连续顺序的。意思是说,存在一个连续升序数列0=b012<...k-1k=m,这样,第i号抄写员得到的书稿是从第bi-1+1本书到第bi本书。复制工作是同时开始进行的,并且每个抄写员复制的速度都是一样的,所以,复制完所有书稿所需的时间决定于分配得到最多工作地那个抄写员的复制时间。

因此,你的任务是找到一个最优分配方案,尽量平均分配工作量,使得分配给每一个抄写员的页数的最大值尽可能的小(如果存在多个最优分配方案,只要输出其中一种)。

Input

输入数据的第1行是两个整数m和k(1<=k<=m<=500)。

第2行有m个整数P1,P2,...,Pm,这m个整数均为正整数且都不超过1000000。每两个整数之间用空格分开。

Output

输出数据有k行,每行有两个正整数。整数之间用空格分开。

第i行的两个整数ai和bi,表示第i号抄写员所分配得到的书稿的起始编号和终止编号,即从第ai本书到第bi本书是第i号抄写员复制。

Sample Input

9 3
100 200 300 400 500 600 700 800 900

Sample Output

1 5
6 7
8 9

Hint

Source