Alice多年来一直在给Bob送礼物,她知道他最喜欢的是对有趣的整数进行按位异或。 Bob 认为正整数 $$$x$$$ 是有趣的,如果它满足 $$$x \not\equiv k (\bmod 2^i)$$$。因此,今年他的生日,她送给他一台超强的最新型号“XORificator 3000”。
Bob 对这份礼物非常满意,因为它使他能够立即计算从 $$$l$$$ 到 $$$r$$$(含)范围内的所有有趣整数的异或。毕竟,一个人还需要什么才能幸福呢?不幸的是,该设备非常强大,以至于它一度与自身进行异或运算并消失了。鲍勃非常沮丧,为了让他高兴起来,爱丽丝请你写下你版本的“异或器”。
输入
输入的第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — 段上的 XOR 查询数。以下 $$$t$$$ 行包含查询,每个查询由整数 $$$l$$$、$$$r$$$、$$$i$$$、$$$k$$$ $$$(1 \leq l \leq r \leq 10^{18}$$$、$$$0 \leq i \leq 30$$$、$$$0 \leq k < 2^i)$$$ 组成。
输出
对于每个查询,输出一个整数 - $$$[l, r]$$$ 范围内所有整数 $$$x$$$ 的异或,使得 $$$x \not\equiv k \mod 2^i$$$。
示例
输入 #1
6 1 3 1 0 2 28 3 7 15 43 1 0 57 2007 1 0 1010 1993 2 2 1 1000000000 30 1543
输出 #1
2 2 13 0 4 1000000519
注意
在第一个查询中,$$$[1, 3]$$$ 范围内的有趣整数是 $$$1$$$ 和 $$$3$$$,因此答案将是 $$$1 \oplus 3 = 2$$$。