Background

Most people's mistake: try to make earlier people copy as little as possible; if the first few people can skip, then let them skip, and output 0 0 for the corresponding person. However, the testdata has been modified to ensure that everyone has work to do.

Problem Description

We need to distribute $m$ ordered books to $k$ people for copying. Each person has the same copying speed. A book cannot be assigned to two (or more) people. The books assigned to each person must form a contiguous block; for example, you cannot assign the 1st, 3rd, and 4th books to the same person.

Please design a plan that minimizes the total copying time. The copying time is the time taken 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 indicates the number of pages in the $i$-th book.

Output Format

Output $k$ lines, each with two integers. On the $i$-th line, output the starting and ending book indices assigned to the $i$-th person. The $k$ lines’ starting indices should be in increasing order. If there are multiple solutions, make the earlier people copy as little as possible.

9 3
1 2 3 4 5 6 7 8 9

1 5
6 7
8 9

Hint

Constraints: $1\le k \le m \le 500$, and the number of pages of each book is a positive integer not exceeding $10^4$.

Translated by ChatGPT 5