时间片轮转

题目描述

有 $n$ 个任务，编号为 $1$ 到 $n$，它们最初按照编号顺序进入等待队列。

第 $i$ 个任务还需要 $t_i$ 个单位时间才能完成。

处理器每次从队首取出一个任务，最多执行 $k$ 个单位时间：

• 如果任务在本次执行后完成，记录它的完成时刻；
• 如果仍未完成，则把它重新放到队尾。

请按照任务完成的先后顺序，输出每个任务的编号和完成时刻。

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个正整数 $t_1,t_2,\ldots,t_n$。

输出格式

每完成一个任务输出一行：

任务编号 完成时刻

数据范围

$1\le n\le 10000$，$1\le k,t_i\le 10^6$，保证总执行轮数不超过 $2\times10^6$。

样例输入

3 2
3 1 4

样例输出

2 3
1 6
3 8