Copying Books

Problem Description

Most people's mistake is to let the people at the front copy as few pages as possible: if the first few people could be given no books, one might output 0 0 for them. The test data has been adjusted so that everyone is guaranteed to have at least one book to copy.

You are given $m$ books with a fixed order and must distribute them to $k$ people to copy. Everyone copies at the same speed. A book may not be copied by two (or more) people, and the books assigned to any one person must be consecutive — for example, you cannot give book $1$, book $3$, and book $4$ to the same person.

Design a plan that minimizes the total copying time. The copying time is the time used by the person who copies the most pages.

Input Format

The first line contains two integers $m, k$.

The second line contains $m$ integers; the $i$-th integer is the number of pages in book $i$.

Output Format

Output $k$ lines. Line $i$ contains two integers: the first and last book numbers copied by person $i$. The starting book numbers across the $k$ lines must be in increasing order. If several answers exist, give as few pages as possible to the people at the front.

Sample Input

9 3
1 2 3 4 5 6 7 8 9

Sample Output

1 5
6 7
8 9

Hint

$1 \le k \le m \le 500$.