효율적인 평가

20xx년부터 고등학생을 위한 정보올림피아드의 모든 대회는 온라인으로 열리기로 했다. 현장 대회를 제안하는 사람이 없도록 감시하기 위해 온라인 올림피아드 조직(OOO)이 만들어졌다. 이런 조직에는 자체 대회 관리 시스템이 필요하다. 유능한 관리자들이 이미 고용되었고, 막대기와 파란 테이프도 구입되었다.

솔루션 평가의 효율을 높이기 위해 새로운 구조가 도입되었다. 처음에 테스트 대기열에는 1번부터 $m$번까지 순서대로 테스트가 놓여 있다. 스케줄링 모듈은 $n$번의 이동을 차례로 수행한다. $i$번째 이동에서는 대기열의 $l_i$번 위치부터 $r_i$번 위치까지(양 끝 포함) 구간을 고르고, $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 100\,000$, $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. 처음에는 1번부터 10번까지의 모든 테스트가 대기열에 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 순서로 있다. 2. 첫 번째 이동에서 2, 4, 6, 8번 테스트가 제거된다. 대기열은 1, 3, 5, 7, 9, 10이 된다. 3. 두 번째 이동에서 1번과 5번 테스트가 제거되고, 대기열은 3, 7, 9, 10이 된다.