3623 - CATS

CATS(Counter and Two Stacks)是一门有一个counter和两个栈的语言。S1和S2是两个栈，初始时候每个栈中有无数个0，压栈和出栈的操作分别为“PUSH”和“POP”。“ADD”取出栈顶两个元素，并把和重新压栈。下程序中T1，T2分别表示S1，S2的栈顶元素。 COUNTER = X WHILE COUNTER > 0 S2 PUSH T1 //把S1栈顶元素压入S2 S1 POP //S1栈顶元素出栈 FLIP LAST BINARY BIT OF ALL NUMBERS IN S1 //把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 求该程序对于给定输入X,L,N的输出。

第一行一个整数Q，接下来Q行每行有三个正整数分别为X,L和N，其中L不是N的倍数。

输出共Q行，每行一个整数，为题目程序对于每组X,L和N的输出。

数据规模：OJ中只有一组数据，Q=223100，X,N,L<=2^60-1。