Efficient Evaluation

문제

Starting from year $20xx20xx$ organizers of all Olympiads in Informatics for high school students decided to conduct their competitions online. An Organization of Online Olympiads (OOO) was created to control and monitor that no one thinks of announcing an onsite competition. Of course, such a powerful and respectful organization needs its own contest managing system. Efficient managers were already hired, sticks and blue tape bought.

In order to increase the efficiency of solutions evaluation a new architecture was introduced. Initially, there are $mm$ tests located in the testing queue in order from test $11$ to test $mm$. Scheduling module consequently performs $nn$ moves. On the $ii$-th move it picks a segment of elements of the queue consisting of elements on positions from $l_{i}l\_i$ to $r_{i}r\_i$ inclusive (positions are numbered starting with $11$) and runs the solution on tests on the positions of $l_i,l_i+2,l_i+4,\dots ,r_{i}l\_i,\; l\_i\; +\; 2,\; l\_i\; +\; 4,\; \backslash ldots,\; r\_i$ (its guaranteed that $l_{i}l\_i$ and $r_{i}r\_i$ are of the same parity). After this is done, all the tests that solution have already been run on are removed from the testing queue and the remaining tests are shifted such that no empty space is left between them. For example, if the testing queue contains tests with initial indices $2,3,4,5,10,12,13,202,\; 3,\; 4,\; 5,\; 10,\; 12,\; 13,\; 20$ and scheduling module applies operation $l_i=3l\_i\; =\; 3$, $r_i=7r\_i\; =\; 7$, the solution will run on tests at position $33$, $55$ and $77$, that have initial indices $44$, $1010$ and $1313$. After this the testing queue will look like $2,3,5,12,202,\; 3,\; 5,\; 12,\; 20$.

Your goal is to implement the part of this module that for each of the $nn$ moves determines the minimum and the maximum initial index of the test that solution was run on at this move.

입력

The first line of the input contains two integers $nn$ and $mm$ ($1\le n\le 1000001\; \backslash leq\; n\; \backslash leq\; 100\backslash ,000$, $1\le m\le {10}^{18}1\; \backslash leq\; m\; \backslash leq\; 10^\{18\}$) — the number of moves that the scheduling module is going to make and the number of tests initially located in the testing queue.

Each of the following $nn$ lines contains two integers $l_{i}l\_i$ and $r_{i}r\_i$ (1 ≤ l_i ≤ r_i ≤ m) — parameters of the $ii$-th move of testing module. It’s guaranteed that before the module applies the $ii$-th move there are at least $r_{i}r\_i$ tests in the queue and that $l_{i}l\_i$ and $r_{i}r\_i$ are of the same parity.

출력

For each of the $nn$ moves of the testing module print two integers — the minimum and the maximum initial index of the test that will be used to test solution (and then removed) during the $ii$-th move.

힌트

Consider the first sample.

0. Initially, there are all tests from $11$ to $1010$ in the queue, it looks like $1,2,3,4,5,6,7,8,9,101,\; 2,\; 3,\; 4,\; 5,\; 6,\; 7,\; 8,\; 9,\; 10$.
1. During the first move tests $2,4,6,82,\; 4,\; 6,\; 8$ will be removed. The queue will look like $1,3,5,7,9,101,\; 3,\; 5,\; 7,\; 9,\; 10$.
2. During the second move tests $11$ and $55$ will be removed and the queue will transform to $3,7,9,103,\; 7,\; 9,\; 10$.

2 10
2 8
1 3

2 8
1 5

4 6
1 1
1 1
1 1
2 2

1 1
2 2
3 3
5 5