题目描述

对一个元素互不相同的长度 $\ge 3$ 的正整数序列 $a$，定义 $a$ 的“肿胃数（nediam）”$f(a)$ 为：

• 当 $|a| = 3$ 时，$f(a)$ 为 $a$ 的中位数；
• 当 $|a| > 3$ 时，取 $a$ 的任意一个长度为 $3$ 的子段 $[a_i, a_{i + 1}, a_{i + 2}]$，记这个子段的中位数为 $x$，$a$ 删掉 $x$ 后的序列为 $b$，$f(a)$ 为所有 $b$ 中 $f(b)$ 的最大值。

乌龟给你一个 $1 \sim n$ 的排列 $p_1, p_2, \ldots, p_n$ 和 $m$ 次询问，每次询问给定 $l, r$，你需要求出 $[p_l, p_{l + 1}, \ldots, p_r]$ 的“肿胃数（nediam）”，即 $f([p_l, p_{l + 1}, \ldots, p_r])$。

输入格式

为了加快读入速度，我们采用以下读入方法。

第一行包含六个正整数 $n, m, seed, A, B, C$。

第二行包含一个排列 $p_1, p_2, \ldots, p_n$。

接下来的 $m$ 组询问，每组询问你要按照如下的方式生成 $(l, r)$：

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);
}

每组询问调用一次 gen() 生成这组询问的 $(l, r)$。

输出格式

为了加快输出速度，我们采用以下输出方法。

设第 $i$ 组询问的答案为 $ans_i$，你需要输出 $(1 \times ans_1) \oplus (2 \times ans_2) \oplus \cdots \oplus (m \times ans_m)$，其中 $\oplus$ 为按位异或。

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

提示

【样例解释 #1】

生成的四组询问分别为 $(1, 4), (1, 3), (1, 3), (2, 4)$，答案分别为 $2, 3, 3, 3$，所以你需要输出 $(1 \times 2) \oplus (2 \times 3) \oplus (3 \times 3) \oplus (4 \times 3) = 2 \oplus 6 \oplus 9 \oplus 12 = 1$。

对于第一组询问，选择子段 $[1, 3, 4]$ 或 $[3, 4, 2]$ 都会使得 $3$ 被删除。删除 $3$ 后的序列为 $[1, 4, 2]$，中位数为 $2$。

【数据范围】

本题使用捆绑测试。

• 特殊性质 A：$p_i = i$；
• 特殊性质 B：$p$ 从所有 $1 \sim n$ 的排列中等概率随机生成。

对于所有数据，满足：

• $3 \le n \le 10^6$；
• $1 \le m \le 5 \times 10^6$；
• $0 \le seed, A, B, C < 2^{32}$；
• $p$ 是一个 $1 \sim n$ 的排列。