题目描述

题目译自 Open Olympiad in Informatics 2017 Day1 T3 「Эффективное тестирование / Efficient Evaluation」。

从 $20$xx 年开始，所有编程奥林匹克竞赛的组织者一致同意仅通过互联网举办比赛，为此成立了有限责任公司「在线奥林匹克组织」（简称 OOO）。显然，这样一个重要的组织不能没有自己的评测系统，因此他们聘请了高效的经理，购买了白板，并准备了蓝色胶带。

为了提高评测过程的效率，开发了以下架构。最初，任务的所有 $m$ 个测试点按照从 $1$ 到 $m$ 的顺序排列在评测队列中。然后，规划模块依次执行 $n$ 个操作。第 $i$ 个操作包括选择队列中从位置 $l_i$ 到 $r_i$（包含两端，以 $1$ 开始编号）的片段，并在该片段上每隔一个测试点进行解决方案的检查，即在队列位置 $l_i, l_i + 2, l_i + 4, \ldots, r_i$ 上的测试点（保证 $l_i$ 和 $r_i$ 具有相同的奇偶性）。随后，被检查的测试点从队列中删除，剩余的测试点向前移动以填补空位，确保队列中没有空隙。例如，如果队列中包含测试点的原始编号为 $2, 3, 4, 5, 10, 12, 13, 20$，并且执行了一个操作 $l_i = 3$，$r_i = 7$，那么解决方案将在位置 $3$、$5$ 和 $7$ 的测试点上进行评测，这些测试点的原始编号为 $4, 10, 13$。操作完成后，评测队列将包含原始编号为 $2, 3, 5, 12, 20$ 的测试点。

你的任务是实现一个模块，对于上述 $n$ 个操作中的每一个，确定在该步骤中检查的测试点中，原始编号的最小值和最大值。

输入格式

输入数据的第一行包含两个数字 $n$ 和 $m$ $(1 \leq n \leq 100000, 1 \leq m \leq 10^{18})$，分别表示规划模块的操作数量和任务中的测试点数量。

接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$ $(1 \leq l_i \leq r_i \leq m)$，表示第 $i$ 个规划模块操作的参数。保证在执行第 $i$ 个操作之前，评测队列中至少有 $r_i$ 个测试点，并且 $l_i$ 和 $r_i$ 具有相同的奇偶性。

输出格式

对于 $n$ 个规划模块操作中的每一个，输出两个整数，即在该步骤中检查的测试点中，原始编号的最小值和最大值。

样例 1

输入

2 10
2 8
1 3

输出

2 8
1 5

让我们看一下第一个样例中评测队列是如何变化的：

• 最初，评测队列包含从 $1$ 到 $10$ 的所有测试点，即队列为 $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$。
• 执行第一个请求时，将删除测试点 $2, 4, 6, 8$，队列变为 $1, 3, 5, 7, 9, 10$。
• 执行第二个请求时，将删除测试点 $1$ 和 $5$，队列变为 $3, 7, 9, 10$。

样例 2

输入

4 6
1 1
1 1
1 1
2 2

输出

1 1
2 2
3 3
5 5

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。