There are $2^n$ cards, each numbered from $1$ to $2^n$. To ensure fairness, we perform a shuffle operation as follows:

1. Take all cards at odd positions in order to form a new pile of cards.
2. Place the new pile of cards in front of the old pile.

For example, $12345678$ becomes $13572468$ after one shuffle, and $15263748$ after another.

There are 6 groups of length $m$: $n, x, l, r, t, ans$. $ans_i$ is equal to the XOR sum of the numbers on the cards from position $l_i$ to $r_i$ after shuffling the $2^{n_i}$ cards $x_i$ times, with each number increased by $t_i$, modulo $2^{n_i}-1$. Given that for $i \ge 1$, the arrays $n, x, l, r, t$ satisfy the following formulas:

1. $n_i = (ans_{i-1} + i - 1) \pmod 5 + base$
2. $l_i = (ans_{i-1} \times 2 + l_{i-1} + i - 1) \pmod {2^{n_i}} + 1$
3. $r_i = (ans_{i-1} + 1 + l_i \pmod {2^{n_i}} \times 2^{\lfloor \frac{n_i}{2} \rfloor}) \pmod {2^{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) \pmod {2^{n_i}}$
6. $t_i = (l_i + r_i) \pmod {2^{n_i}}$

Given $n_0, x_0, l_0, r_0, t_0$, calculate $ans_{m-1}$.

Input

The first line contains one integer $m$, representing the number of data points. The next line contains 6 integers: $n, x, l, r, t, base$.

Output

Output $m$ lines, each containing one number representing the final answer.

Examples

Input 1

2
5 1 4 27 3 15

Output 1

2700

Constraints

• For 10% of the data: $m \le 100$
• For 20% of the data: $m \le 500000, n \le 20, base \le 16$
• For 60% of the data: $m \le 500000, n \le 60, base \le 55$
• For 100% of the data: $m \le 5000000, n \le 60, 0 < l \le r \le 2^n, 0 < x, t < 10^9, base \le 55$