CATS

CATS(Counter and Two Stacks)는 카운터 COUNTER와 두 스택 S1, S2를 다루는 난해한 언어이다. 두 스택은 처음에 무한히 많은 $0$으로 채워져 있다.

PUSH는 값을 넣고, POP은 꺼낸다. ADD는 위에서 두 값을 더해 다시 넣는다. 음수를 PUSH하려 하면 값은 들어가지 않고, 그 스택의 모든 원소(무한 꼬리 포함)의 최하위 비트가 뒤집힌다 ($X \oplus 1$).

Mr. Panda는 $X$, $L$, $N$을 받아 $L$보다 큰 $N$의 배수 중 $X$번째를 출력하려 했지만, 아래 버그 있는 의사코드는 다른 값을 출력한다. $L$은 $N$의 배수가 아니다.

COUNTER = X
WHILE COUNTER > 0
     S2 PUSH T1
     S1 POP
     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

T1, T2는 각각 S1, S2의꼭짓값이다. ELSE 블록 안의 S1 PUSH T2는 ADD 이후의 T2를 쓴다. 각 쿼리마다 의사코드가 출력하는 정수를 구하라.

첫 줄에 쿼리 수 $Q$가 주어진다.

다음 $Q$줄에 $X$, $L$, $N$이 주어진다. $L$은 $N$의 배수가 아니다.

각 쿼리에 대해 의사코드가 출력하는 정수를 한 줄에 하나씩 출력한다.

무한 $0$ 꼬리는 하나의 패리티 비트로 두고, 유한 접두사만 배열로 저장한다. FLIP과 음수 PUSH는 꼬리 비트와 접두사 전체에 XOR $1$을 적용한다. POP으로 접두사가 비면 꼬리만 남는다.