CATS Batch 컴파일 명령

난해한 프로그래밍 언어는 프로그래밍의 한계를 시험하기 위해, 또는 단지 사람들을 웃기기 위해 만들어진 프로그래밍 언어입니다. 어느 날, 승현이는 Counter and Two Stacks (CATS)라고 불리는 난해한 프로그래밍 언어를 가지고 놀고 있었습니다. 이 언어는 여러 가지 기본적인 연산들을 통하여 카운터 (COUNTER)와 두 개의 스택(S1과 S2)를 다룰 수 있도록 설계되었습니다.

초기에, 두 스택 모두 무한한 수의 0들로 초기화되어 있습니다. 데이터들은 PUSH 또는 POP 연산을 통하여 스택에 더해지거나 빼내질 수 있습니다. 추가적인 연산인 ADD는 스택의 맨 위에 있는 두 개의 원소를 빼내고, 이들을 더한 뒤 그 값을 해당하는 스택에 다시 넣습니다. 승현이는 이 언어를 사용한지 얼마 안 됐기 때문에 단순한 문제를 해결하기로 했습니다: "세 개의 정수 $X, L, N$이 주어질 때, $L$보다 큰 $N$의 배수들 중 $X$번째로 작은 것의 값을 구하시오." 승현이는 편의상 코드를 짤 때 프로그램이 음수를 사용하도록 했으며, $L$이 $N$의 배수인 경우는 고려하지 않았습니다.

승현이는 이 언어를 처음 다루어 보았기 때문에 정확한 답을 출력하지 않습니다. 더욱이, 그는 이 언어에서 사용하는 스택들이 음수를 다룰 수 없다는 사실을 몰랐습니다. CATS에서, 코드가 PUSH 연산을 사용하여 스택에 음수를 넣으려고 시도하면, 이 숫자는 스택에 들어가지 않습니다. 대신 CATS는 이상하게 동작하여 그 스택 안에 있는 모든 숫자들의 마지막 비트가 뒤집힐 것입니다. (스택의 크기가 무한함에 유의하세요) 예로 들어, $4 = 100_{2}$는 $5 = 101_{2}$로 변할 것입니다. 숫자 $X$의 마지막 비트를 뒤집는 것은 C/C++에서 (X ^ 1)을 행하는 것과 같습니다.

게다가 승현이는 실수로 몇 개의 연산들을 두 번 행하도록 했습니다. 결과적으로 승현이가 짠 코드는 아래와 같이 쓸 수 있습니다. 여기서 T1과 T2는 각각 스택 S1과 S2의 맨 위에 위치한 원소를 가리킵니다.

COUNTER = X
WHILE COUNTER > 0
    S2 PUSH T1  //Push the top element of S1 onto S2
    S1 POP      //Pop the top element of S1
    FLIP LAST BINARY BIT OF ALL NUMBERS IN S1
    IF T2 > L
        COUNTER = COUNTER - 1
        IF COUNTER == 0 PRINT T2
    ELSE
        S2 PUSH N
        S2 PUSH N
        S2 ADD
        S2 ADD
        S1 PUSH T2
        S1 PUSH T2
        S2 POP
        S2 POP

승현이의 코드는 동작하는 데 너무 오래 걸려서 버그를 잡는 게 너무 힘들다고 합니다. 승현이가 출력값을 빠르게 알 수 있도록 도와주세요!

입력 형식

첫 번째 줄에는 쿼리의 수 $Q$가 주어집니다. 다음 $Q$개 줄에는 3개의 자연수 $X, L, N$이 공백을 사이로 두고 주어집니다. 위에서 명시했듯이 $L$은 $N$의 배수가 아닙니다.

출력 형식

각 쿼리마다 승현이의 코드가 출력한 값을 한 줄에 하나씩 출력합니다. 승현이의 코드가 각 쿼리마다 정확히 1개의 정수를 출력한다는 것은 보장됩니다.

서브태스크

1. (4점) $Q = 1$, $X \le 1,000,000$, $L \le 20$, $N \le 20$.
2. (4점) $Q \le 50$, $X \le 1,000,000$, $L \le 50$, $N \le 20$.
3. (4점) $Q \le 500$, $X \le 1,000,000$, $L \le 80$, $N \le 20$.
4. (4점) $Q \le 1,000$, $X \le 1,000,000$, $L \le 1,000,000$, $N \le 1,000,000$.
5. (4점) $Q \le 10,000$, $X \le 2^{30} - 1$, $L \le 2^{30} - 1$, $N \le 2^{30} - 1$.
6. (5점) $Q \le 100,000$, $X \le 2^{60} - 1$, $L \le 2^{60} - 1$, $N \le 2^{60} - 1$.

첫 번째 쿼리가 주어질 때, 승현이의 코드에서 WHILE 루프가 반복될 때마다 COUNTER의 값과 S1 내부의 값들을 추적한 결과입니다. 편의상 S1의 맨 위 4개 원소만 보여집니다. 각 줄의 가장 왼쪽에 위치한 숫자가 S1의 맨 위에 있는 원소를 의미합니다.

COUNTER: 4
S1: 0000...

COUNTER: 4
S1: 4411...

COUNTER: 4
S1: 8850...

COUNTER: 3
S1: 9411...

COUNTER: 2
S1: 5000...

COUNTER: 2
S1: 9911...

COUNTER: 1
S1: 8000...

다음 반복에서 COUNTER는 0이 되어 8이 출력됩니다.