Description

For a sequence $a$ of distinct positive integers with length $|a| \geq 3$, the "nediam" $f(a)$ is defined as follows:

• When $|a| = 3$, $f(a)$ is the median of $a$;
• When $|a| > 3$, for any contiguous subsequence of length $3$ denoted as $[a_i, a_{i + 1}, a_{i + 2}]$, let the median of this subsequence be $x$. The sequence obtained by removing $x$ from $a$ is denoted as $b$, and $f(a)$ is the maximum value of $f(b)$ over all such subsequences.

Turtle gives you a permutation $p_1, p_2, \ldots, p_n$ of the integers from $1$ to $n$ and $m$ queries. For each query, given $l$ and $r$, you need to calculate the "nediam" $f([p_l, p_{l + 1}, \ldots, p_r])$.

Input Format

To speed up the input process, we will use the following method.

The first line contains six positive integers $n, m, seed, A, B, C$.

The second line contains a permutation $p_1, p_2, \ldots, p_n$.

For the next $m$ queries, you will generate the pair $(l, r)$ as follows:

unsigned seed, A, B, C;

inline unsigned rnd() {
	seed = A * seed * seed + B * seed + C;
	seed = seed ^ (seed << 27);
	seed = seed ^ (seed >> 19);
	return seed;
}

inline std::pair<int, int> gen() {
	int l, r;
	do {
		l = rnd() % n + 1;
		r = rnd() % n + 1;
	} while (abs(l - r) < 2);
	if (l > r) {
		std::swap(l, r);
	}
	return std::make_pair(l, r);
}

For each query, call gen() once to generate the pair $(l, r)$ for that query.

Output Format

To speed up the output process, we will use the following method.

Let the answer for the $i$-th query be $ans_i$. You need to output $(1 \times ans_1) \oplus (2 \times ans_2) \oplus \cdots \oplus (m \times ans_m)$, where $\oplus$ denotes the bitwise XOR operation.

4 4 114 514 1919 810
1 3 4 2

1

10 100 123456 789123 456789 123456789
3 9 5 7 6 4 10 8 2 1

142

Hint

Sample $1$ Explanation

The generated four queries are $(1, 4), (1, 3), (1, 3), (2, 4)$, with answers $2, 3, 3, 3$ respectively. Therefore, you need to output $(1 \times 2) \oplus (2 \times 3) \oplus (3 \times 3) \oplus (4 \times 3) = 2 \oplus 6 \oplus 9 \oplus 12 = 1$.

For the first query, choosing the contiguous subsequence $[1, 3, 4]$ or $[3, 4, 2]$ will result in the deletion of $3$. After removing $3$, the remaining sequence is $[1, 4, 2]$, and the median is $2$.

Subtasks and Constraints

• Special Property A: $p_i = i$.
• Special Property B: $p$ is randomly generated with equal probability from all permutations of $1 \sim n$.

For all tests, it is guaranteed that:

• $3 \le n \le 10^6$;
• $1 \le m \le 5 \times 10^6$;
• $0 \le seed, A, B, C < 2^{32}$;
• $p$ is a permutation of $1 \sim n$.