Steve 拥有一个长度为 $n$ 的整数数组 $a$（下标从 1 开始）。起初，他将所有元素都赋值为 0。之后，他进行了 $m$ 次操作，每次操作都是用某个值更新数组 $a$ 的一个区间。在所有操作完成后，你需要计算 $\bigoplus_{i=1}^{n} (i \cdot a_i)$ 的值，其中 $\bigoplus$ 表示按位异或运算符。

为了避免输入数据过大，这些操作通过一种特殊的方法进行了加密。输入给出了三个无符号 32 位整数 $X, Y$ 和 $Z$ 作为初始值。随机数生成函数描述如下，其中 $\wedge$ 表示按位异或运算符，<< 表示按位左移运算符，>> 表示按位右移运算符。注意，该函数在调用后会改变 $X, Y$ 和 $Z$ 的值。

1: function RNG61()
2:     X ← X ∧ (X << 11) ▷ 32-bit unsigned integer overflow might occur
3:     X ← X ∧ (X >> 4)
4:     X ← X ∧ (X << 5) ▷ 32-bit unsigned integer overflow might occur
5:     X ← X ∧ (X >> 14)
6:     W ← X ∧ (Y ∧ Z)    ▷ as a partial 32-bit unsigned integer
7:     X ← Y
8:     Y ← Z
9:     Z ← W
10:    return Z
11: end function

令调用上述函数产生的第 $i$ 个结果值为 $f_i$ ($i = 1, 2, \dots, 3m$)。Steve 的第 $i$ 次操作是将区间 $a_j$ ($j = l_i, l_i + 1, \dots, r_i$) 中所有小于 $v_i$ 的元素更新为 $v_i$，其中：

$$ \begin{cases} l_i = \min ((f_{3i-2} \bmod n) + 1, (f_{3i-1} \bmod n) + 1) \\ r_i = \max ((f_{3i-2} \bmod n) + 1, (f_{3i-1} \bmod n) + 1) \\ v_i = f_{3i} \bmod 2^{30} \end{cases} (i = 1, 2, \dots, m) $$

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 接下来的 $T$ 行，每行描述一个测试用例，包含五个空格分隔的整数 $n, m, X, Y$ 和 $Z$。

$1 \le T \le 100, 1 \le n \le 10^5, 1 \le m \le 5 \cdot 10^6, 0 \le X, Y, Z < 2^{30}$。 保证所有测试用例中 $n$ 的总和不超过 $10^6$，且 $m$ 的总和不超过 $5 \cdot 10^7$。

输出格式

对于每个测试用例，输出一行答案。

样例

输入 1

4
1 10 100 1000 10000
10 100 1000 10000 100000
100 1000 10000 100000 1000000
1000 10000 100000 1000000 10000000

输出 1

1031463378
1446334207
351511856
47320301347

说明

在第一个样例中，所有操作完成后，$a = [1031463378]$。 在第二个样例中，所有操作完成后，$a = [1036205629, 1064909195, 1044643689, 1062944339, 1062944339, 1062944339, 1062944339, 1057472915, 1057472915, 1030626924]$。

RNG61 function