← 返回题目列表

Codeforces · 2036/F

F. 异或器 3000

中文机器翻译题面 查看原题

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$$$。