该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题意：

有 $n$ 个提醒任务。每个任务具有唯一编号和一个正整数周期 $p$，会在时刻 $p,2p,3p,\ldots$ 各触发一次。

现在要输出最先发生的 $k$ 次触发记录。所有触发按时刻从小到大排列，同一时刻按任务编号从小到大排列。同一个任务的多次触发分别计数。

所有任务一直有效，输出完 $k$ 条记录即停止。$k=0$ 时，不输出任何记录。

输入格式：

第一行两个整数 $n$、$k$（$1 \le n \le 2\times10^5$，$0 \le k \le 2\times10^5$），分别表示任务数量和需要输出的触发次数。

接下来 $n$ 行，每行两个整数 $id$、$p$（$1 \le id,p \le 10^9$），分别表示任务编号和周期。保证所有任务编号互不相同，输入顺序不一定按编号排列。

输出格式：

输出 $k$ 行，每行两个整数，依次表示触发时刻和任务编号，以一个空格分隔。触发时刻可能超过 $32$ 位有符号整数范围。

样例：

样例输入：

3 8
8 3
2 3
5 5

样例输出：

3 2
3 8
5 5
6 2
6 8
9 2
9 8
10 5

样例解释：

时刻 $3$、$6$、$9$ 都有两个任务触发，此时编号 $2$ 必须排在编号 $8$ 前面，与它们的输入顺序无关。