题目描述
这是一道模板题。
对于两个非负整数 x,y 我们定义其 Nim 积 x⊗y:
x⊗y=mex{(a⊗b)⊕(a⊗y)⊕(x⊗b)∣0≤a<x∧0≤b<y}
其中 ⊕ 是异或运算,mex 是集合中不存在的最小非负整数。
输入格式
第一行输入四个整数 T,SA,SB,SC。
为了测试效率,询问数量 T 可能很大,使用如下代码生成询问的输入:
unsigned int SA, SB, SC;
unsigned int rng() {
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
在接下来 T 组询问中,设 lastans 最初为 0,则按顺序有
unsigned int x = rng() + lastans;
unsigned int y = rng();
lastans = nim_mul(x, y);
如此进行 T 次循环。
输出格式:
输出一行一个整数,表示最后一组解的答案。
样例数据
样例输入
5 171380702 78283356 95463589
样例输出
1145338263
样例解释
各组询问的 x,y 解码后以及 Nim 积分别是:
- 256959001⊗2376274030=32929940
- 2087417067⊗3383958306=1591092706
- 2004390948⊗1462129087=601753157
- 1466470965⊗4216679711=1115264544
- 94560729⊗4273456727=1145338263
子任务
生成的数据均在 232 范围以内,故保证 0≤x,y<232。
四组数据中的 T 分别为 10,1000,3×104,3×107。