题目描述

现有 $2^n$ 张牌，每张牌由 $1$ 到 $2^n$ 记上数字，为了公平，现需进行洗牌，每次洗牌操作如下：

1. 讲所有奇数位上的牌依次取出组成新的一堆牌。
2. 将新的一堆牌放在旧有的牌前面。

如 $12345678$ 洗一次后变为 $13572468$ 再洗一次变为 $15263748$。

现在有 $6$ 个长度为 $m$ 的组，$n,x,l,r,t,ans$。

其中 $ans_i$ 等于 $2^{n_i}$ 张牌洗了 $x_i$ 次牌后，把第 $l_i$ 到 $r_i$ 张牌上的数字均加 $t_i$ 并依次异或后的异或值 $\mod2^{n-1}$。

已知当 $i\ge 1$ 时 $n,x,l,r,t$ 数组满足以下公式：

1. $n_i=(ans_{i-1}+i-1)\mod5+base$
2. $l_i=(ans_{i-1}\times2+l_{i-1}+i-1)\mod2^{n_i}+1$
3. $r_i=(ans_{i-1}+1+l_i\mod2^{\lfloor\frac{n_i}{2}\rfloor}\times2^{\lfloor\frac{n_i}{2}\rfloor}))\mod2^{n_i}+1$
4. $if(l_i>r_i) swap(l_i,r_i)$
5. $x_i=(r_i-l_i+t_{i-1}+i)\mod2^{n_i}$
6. $t_i=(l_i+r_i)\mod2^{n_i}$

现给出 $n_0,x_0,l_0,r_0,t_0$ 的数值，求 $ans_{m-1}$ 为多少。

输入格式

第一行包含一个整数 $m$，表示数据个数。

接下来一行包含六个整数，分别为 $n,x,l,r,t,Base$。

输出格式

输出包含 $m$ 行，每行一个数，表示最后的答案。

2
5 1 4 27 3 15

2700

数据规模与约定

对于 $100\%$ 的数据，$m \le 5 \times 10^6$，$n \le 60$，$0<l \le r \le 2^n$，$0<x,t<10^9$，$Base \le 55$。

题目来源

By 佚名提供