잠시드의 잔

고대 페르시아의 위대한 왕 잠시드는 우주의 모든 것을 내려다볼 수 있는 신비한 잔, 점복의 잔을 찾고 있다. 그는 알보르즈 산맥에 사는 위대한 마법사 샤흐라스브에게 도움을 청했다.

샤흐라스브는 잠시드에게 그 잔이 고대 페르시아 중앙의 큰 사막인 대염호 사막 어딘가에 숨겨져 있다고 말했지만, 정확한 위치는 알지 못한다. 잠시드는 그에게 여러 번 질문할 수 있다. 각 질문에서 잠시드는 페르시아 안의 임의의 점(사막 안이든 밖이든)을 고르고, 샤흐라스브는 마법의 힘으로 그 잔과 고른 점 사이의 카투지안 거리를 알아낼 수 있다.

페르시아의 모든 점은 $\[-10^9, 10^9]$ 범위의 정수 $x$, $y$ 좌표를 가진다. 사막은 중앙에 있는 정사각형 영역으로, $x$, $y$ 좌표가 $\[-5 \times 10^8, 5 \times 10^8]$ 범위에 있다. 두 점 $(x, y)$와 $(p, q)$ 사이의 카투지안 거리는 $|x - p| \oplus |y - q|$로 계산한다. 여기서 $|x - p|$는 $(x-p)$의 절댓값이고, $\oplus$는 비트 XOR(배타적 논리합)을 나타낸다.

여러분의 임무는 잠시드가 샤흐라스브에게 여러 번 질문하여 잔을 찾도록 돕는 것이다.

• $1 \leq T \leq 1000$,
• $-5 \times 10^8 \leq a[i], b[i] \leq 5 \times 10^8$.