题目背景

萤火穿过风 融化成飞光 就在你眼眸盛放

题目描述

小 D 发现了一群萤虫，萤群中有 $n$ 个萤虫且按照顺序排成一行并将其从 $1$ 从 $n$ 编号。小 D 非常厉害，他一眼就看出这 $n$ 个萤虫的光度，且这些萤虫的亮度值是 $1\sim n$ 的一个排列。小 D 想找一些萤虫，让它们共同编织出如梦似幻的璀璨光幕，具体的，他需要一个 萤虫区间。

小 D 对 萤虫区间 定义苛刻：至少得有 $k$ 个萤虫且这些萤虫编号连续。

小 D 十分欣赏萤虫的光芒，他定义编号从 $L$ 到 $R$ 的萤虫区间的总体光度值为这些萤虫的光度值中的第 $m$ 大数。小 D 给定了 $Q$ 个指标，每个指标给定一个数 $x$，寻找一个 萤虫区间 使得这个区间的总体光度值大于等于 $x$。当然，这种区间是很多的，你需要帮小 D 数有多少这样的区间。

输入格式

第一行五个整数 $n,k,m,B,cas$，其中 $B$ 是给定常数，$cas$ 是当前数据点所属的 Subtask 编号。

第二行空格隔开的 $n$ 个数字 $a_i$，表示 $n$ 个萤虫的光度值。用给定代码生成。

第三行一个整数 $Q$，表示给定指标个数。

第四行空格隔开的 $Q$ 个数字，表示每次询问的指标 $x$，用给定代码生成。

本题输入量较大，输入数据可以用以下代码生成：在此可查看完整代码。

// 请注意避免整形溢出 
#define int long long
const int N = 1e6 + 5, INF = 2147483647;
int n, k, m, B, Q, x, a[N], cas;
// myrand 为数据生成器 
struct myrand {
	int A, B, P, x;
	myrand(int A, int B, int P, int x) {
		this->A = A; this->B = B; this->P = P; this->x = x;
	} int next() { return x = (A * x + B) % P; }
};
int read_x(int x) { // 不同数据下的 x 不同
	if (cas == 7) x = x % 2;
	else x = x % (n + 1);
	return x;
}
signed main() {
	cin >> n >> k >> m >> B >> cas >> Q;	
	// B 是生成数据是给定常数。在此初始化数据生成器 myrand 参数 
	myrand rnd(16807, B, INF, 0);
	// 伪随机生成 a 序列 
	for (int i = 1; i <= n; i++) a[i] = i;
	for (int i = 1; i <= n; i++) {
		int l = rnd.next() % n + 1, r = rnd.next() % n + 1;
		swap(a[l], a[r]);
	}
	// 生成查询指标 
	for (int i = 1; i <= Q; i++) x = read_x(rnd.next());
}

你只需要以上述代码为准，进行输入即可。具体操作解释请参见样例解释。本题解法和数据的生成方式无关。

输出格式

对于每一个询问指标，都需要求出对应萤虫区间个数。

为了避免输出过多，请输出 $Q$ 次查询中萤虫区间个数的 异或和。具体操作解释请参见样例解释。

5 3 2 999 1
5

6

6 3 2 998 1
5

3

1000000 10000 1 998244353 4
1000000

306558155574

1000000 10000 2 998244353 5
1000000

39831215473

1000000 100000 100 1231 8
1000000

170979323511

提示

【样例解释 $\mathbf 1$】

萤虫从 $1$ 到 $n$ 的光度值为：$5,4,2,3,1$。总共有 $6$ 个萤虫区间，要求区间第 $2$ 大值，分别是：

• 编号 $1$ 至 $3$ 构成的萤虫为 $[5,4,2]$，总体光度值为 $4$。
• 编号 $2$ 至 $4$ 构成的萤虫为 $[4,2,3]$，总体光度值为 $3$。
• 编号 $3$ 至 $5$ 构成的萤虫为 $[2,3,1]$，总体光度值为 $2$。
• 编号 $1$ 至 $4$ 构成的萤虫为 $[5,4,2,3]$，总体光度值为 $4$。
• 编号 $2$ 至 $5$ 构成的萤虫为 $[4,2,3,1]$，总体光度值为 $3$。
• 编号 $1$ 至 $5$ 构成的萤虫为 $[5,4,2,3,1]$，总体光度值为 $4$。

共有 $5$ 次询问，询问指标分别是 $2,2,2,0,2$，则答案分别是：$6,6,6,6,6$。则总异或值为 $6$。

【样例解释 $\mathbf 2$】

萤虫从 $1$ 到 $n$ 的光度值为：$3,1,4,2,5,6$。

共有 $5$ 次询问，询问指标分别是 $1,5,1,4,6$，答案分别是：$10,4,10,7,0$。则总异或值为 $3$。

【样例解释 $\mathbf 3$】 该数据满足 Subtask 4 的限制。具体求解不做解释。请注意整形溢出相关问题。

【样例解释 $\mathbf 4$】 该数据满足 Subtask 5 的限制。具体求解不做解释。

【样例解释 $\mathbf 5$】 该数据满足 Subtask 8 的限制。具体求解不做解释。

【数据规模与约定】

本题开启子任务捆绑测试。本题输入输出量一点不大，但请注意优化常数。本题自动开启 O2 优化。

• Subtask 1（10 pts）：$m\leq n\leq 100$，$Q\leq 100$。
• Subtask 2（10 pts）：$m\leq n\leq 1000$，$Q\leq 100$。
• Subtask 3（18 pts）：$n\leq 10^5$，$m\leq 100$。
• Subtask 4（9 pts）：$n\leq 10^6$，$m=1$。
• Subtask 5（9 pts）：$n\leq 10^6$，$m=2$。
• Subtask 6（15 pts）：$n\leq 10^6$，$k=m\leq 100$。
• Subtask 7（7 pts）：$n\leq 10^6$，$m\leq 100$，$0\leq x\leq 1$。
• Subtask 8（22 pts）：$n\leq 10^6$，$m\leq 100$。

对于所有测试点满足 $1\leq m\leq k\leq n\leq 10^6$，$m\leq \min\{1000,n\}$，$1\leq a_i\leq n$，$1\leq Q\leq 10^6$，$1\leq B\leq 10^9$。