28245번 - 배고파(Hard)

이 문제는 배고파(Easy)의 상위 문제이고, 배고파(Easy)에 이 문제의 정답 코드를 제출하여 맞힐 수 있다.

송도고등학교는 경관이 참 예쁘다. 도훈이는 특히 학교 뒤쪽에 만개한 벚꽃을 보고 감탄하였다.

2021년 봄에 찍은 송도고등학교 뒤쪽 벚꽃 나무들의 풍경이다.

남고에서 만개한 벚꽃을 보고 있자니 괜스레 속이 쓰린 도훈이는 밥이나 먹어야겠다고 생각했다. 그런데 도훈이에게는 치료가 필요할 정도로 심각한 결정 장애가 있어서 메뉴를 고르는 것이 쉽지 않다. 따라서 도훈이는 $n$개의 메뉴를 각각 다음과 같은 규칙으로 골라 먹을 생각이다.

• 주어진 양의 정수 $m$에 대해 $2^x + 2^y = m$인 음이 아닌 정수 $x$와 $y$를 찾은 뒤 메뉴판의 $(x,y)$ 위치에 적힌 메뉴를 고른다. 단, $x\le y$인 경우만 다룬다.
• 그런 $(x,y)$가 존재하지 않는다면, $(x,y)$가 존재하는 $m$과의 차이가 가장 작은 수로 $m$을 대체한 뒤 위와 같은 규칙으로 메뉴판의 $(x,y)$ 위치에 적힌 메뉴를 고른다. 대체할 수 있는 수가 여러 가지라면 그중 가장 작은 것으로 대체한다. 이때 $(x,y)$가 유일하게 결정됨을 증명할 수 있다.

하지만 도훈이는 $n$과 $m$이 너무 커서 메뉴를 주문하는 데 어려움을 겪고 있다. 도훈이를 도와 $n$개의 메뉴를 주문하는 프로그램을 작성하여라.

첫 번째 줄에 메뉴의 수 $n$이 주어진다.

이어서 $n$개의 각 줄에 메뉴를 고를 때 사용할 양의 정수 $m$이 하나씩 주어진다.

$n$개의 줄에 각각 주문할 메뉴의 위치 $(x,y)$의 $x$, $y$를 공백으로 구분하여 출력한다.

• $1\le n\le 10\,000$.
• $1\le m\le 10^{18}$.
• 주어진 $m$에 대해 $x\le y$인 $(x,y)$ 순서쌍이 존재하지 않을 수 있다.

• $2^0=1$이고, 양의 정수 $n$에 대해 $2^n = \overbrace{2\times 2\times \cdots \times 2}^{n}$로 정의된다.
• C/C++의 경우, 32bit 정수형 int의 범위를 넘어가는 정수를 다루게 되므로 64bit 정수형 long long 사용을 권장한다.