Efficient Evaluation

Starting from year 20xx, the organizers of all Olympiads in informatics for high school students decided to hold their competitions online. An Organization of Online Olympiads (OOO) was created to monitor that nobody proposes an onsite competition. Such an organization needs its own contest management system. Efficient managers have already been hired, and sticks and blue tape have been bought.

To speed up solution evaluation, a new architecture was introduced. Initially, there are $m$ tests in the testing queue, in order from test 1 to test $m$. The scheduling module performs $n$ moves in sequence. On the $i$-th move, it picks the segment of queue positions from $l_i$ to $r_i$ inclusive and runs the solution on the tests at positions $l_i, l_i + 2, l_i + 4, \ldots, r_i$ ($l_i$ and $r_i$ have the same parity). After that, all tests the solution ran on are removed from the queue, and the remaining tests shift so that no gaps remain. For example, if the queue holds tests with initial indices 2, 3, 4, 5, 10, 12, 13, 20 and the move is $l_i = 3$, $r_i = 7$, the solution runs on the tests at positions 3, 5, and 7, which have initial indices 4, 10, and 13. Afterward the queue looks like 2, 3, 5, 12, 20.

Your goal is to implement the part of this module that, for each of the $n$ moves, finds the minimum and maximum initial index of the tests the solution ran on.

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 100\,000$, $1 \leq m \leq 10^{18}$), the number of moves and the number of tests initially in the queue.

Each of the following $n$ lines contains two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq m$), the parameters of the $i$-th move. It is guaranteed that before the $i$-th move there are at least $r_i$ tests in the queue, and that $l_i$ and $r_i$ have the same parity.

For each of the $n$ moves, print two integers on one line: the minimum and the maximum initial index of the test that the solution ran on (and that was then removed) during that move.

Consider the first sample. 1. Initially, all tests from 1 to 10 are in the queue: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. 2. During the first move, tests 2, 4, 6, and 8 are removed. The queue becomes 1, 3, 5, 7, 9, 10. 3. During the second move, tests 1 and 5 are removed, and the queue becomes 3, 7, 9, 10.