[SCOI2014]方伯伯打扑克

题目描述

方伯伯有一些空白的扑克牌。方伯伯想要用这些牌来玩一个数学游戏。 方伯伯首先决定好他要用这些空白的扑克牌组成 $m$ 个牌堆,每一堆牌的张数都是 $2$ 的整数次幂。确切地说,第 $i$ 堆(**注意**:从 $0$ 开始计数)牌将会有 $2^{n_i}$ 张牌。方伯伯首先决定好第 $0$ 堆牌要有 $2^{n_0}$ 张牌,然后将这堆牌从上到下按次序标记 $1 \sim 2^{n_0}$ 的十进制数字。 方伯伯开始游戏前决定要先洗牌,他决定好要洗 $x_0$ 次牌。他洗牌有一个固定的模式,每次洗牌操作等同于以下两个步骤的操作: 1. 将所有奇数位上的牌依次取出组成新的一堆牌。 2. 将新的一堆牌放在旧有的牌前面。 如当 $n_0=3$ 时,第 $0$ 堆牌从上到下一开始为 ``12345678``,洗一次牌得到 ``13572468``,洗两次牌得到 ``15263748``。 洗完牌后,方伯伯在心中决定好把其中从上往下数第 $l_0$ 到第 $r_0$ 张牌上的数字均加上一个数字 $t_0$,并依次(转换成二进制)异或之后得到一个异或值;方伯伯把第 $0$ 堆牌的这个异或值取模 $\bmod \ 2^{n_0-1}$ 的值记作 $\mathrm{ans}_0$。 类似地,方伯伯将按同样的方式用剩下的 $m-1$ 个牌堆。具体地说,他决定按照如下几个公式来对每一堆牌组进行游戏: 1. 对于第 $i$ 堆牌,牌堆中将会有 $2^{n_i-1}$ 张牌,并从上到下标有 $1\sim 2^{n_i-1}$ 的十进制整数。其中,$n_i=(\mathrm{ans}_{i-1}+i-1) \bmod 5 \mathrel{+} \mathrm{base}$, $\mathrm{base}$ 是一个方伯伯事先决定好的正整数。 2. 方伯伯将会先决定好自己用来游戏的牌处于牌堆中的什么位置。方伯伯首先决定好他要看的第一张牌应该是第 $l_i$ 张,其中 $l_i=(2\mathrm{ans}_{i-1}+l_{i-1}+i-1)\bmod 2^{n_i} \mathrel{+} 1$。 3. 方伯伯接着决定他要看的最后一张牌应该是第 $r_i$ 张,其中 $r_i=(\mathrm{ans}_{i-1}+1+l_1\bmod 2^{\lfloor n_i/2 \rfloor} \cdot 2^{\lfloor n_i/2 \rfloor})\bmod 2^{n_i} \mathrel{+}1$。 4. 因为上面两个式子并不简单,有可能会产生 $l_i>r_i$ 的结果,此时将它们的值互换。 5. 想好自己要看什么牌后,方伯伯就会以此决定自己要洗 $x_i$ 次牌,其中 $x_i=(r_i-l_i+t_{i-1}+i-1)\bmod 2^{n_i}$。 6. 方伯伯同时还会想好他要给每张牌要加上数字的是 $t_i$,其中 $t_i=(l_i+r_i)\bmod 2^{n_i}$。 7. 方伯伯洗完牌后,把其中从上往下数第 $l_i$ 到第 $r_i$ 张牌上的数字均加上数字 $t_i$,并依次(转换成二进制)异或之后得到一个异或值;方伯伯把第 $i$ 堆牌的这个异或值取模 $\bmod 2^{n_i-1}$ 的值记作 $\mathrm{ans}_i$,接着回到第一步玩下一个牌堆。 方伯伯听说你有高超的信息学能力,他想知道你能否在他完成游戏前就算出最后一个牌堆,即第 $m-1$ 个牌堆,得到的游戏结果 $\mathrm{ans}_{m-1}$。你能做到吗? 输入描述: 第一行包含一个整数 $m$,表示牌组的个数。 接下来一行包含六个整数,分别为 $n_0, x_0 ,l_0 ,r_0, t_0 , \mathrm{Base}$。 输出描述: 输出为一个数,表示最后的答案。 数据范围: 对于 $10\%$ 的数据,$m\le 100$。 对于 $20\%$ 的数据,$m\le 5\times 10^5$,$n_i\le 20$,$ \mathrm{Base}\le 16$。 对于 $60\%$ 的数据,$m\le 5\times 10^5$,$n_i\le 60$,$\mathrm{Base}\le 55$。 对于所有数据,$m \leq 5\times 10^6,\ n_i \leq 60,\ 0<l_i \leq r_i \leq 2^{n_i},\ 0<x_i,t_i<10^9,\ \mathrm{Base} \leq 55$。 样例解释:$ans_0=1$,$n_1=16$,$l_1=7$,$r_1=1795$,$x_1=1791$,$t_1=1802$。

输入输出格式

输入格式


第1行包含1个整数m,表示数据个数接下来1行包含6个整数,分别为n,x,L,r,t,Base

输出格式


输出包含m行,每行1个数,表示最后的答案

输入输出样例

输入样例 #1

2
5 1 4 27 3 15

输出样例 #1

2700

说明

m<=5000000,N<=60 0<L<=R<=2^N 0<x,t<10^9 Base<=55