Background

Fireflies pass through the wind, melt into flying light, and bloom in your eyes.

Problem Description

Xiao D found a group of fireflies. There are $n$ fireflies in the group, arranged in a line in order and numbered from $1$ to $n$. Xiao D is very capable: at a glance he knows the brightness of these $n$ fireflies, and the brightness values form a permutation of $1\sim n$. Xiao D wants to pick some fireflies so that they can weave a dreamy, dazzling curtain of light. Specifically, he needs a firefly interval.

Xiao D has strict requirements for a firefly interval: it must contain at least $k$ fireflies, and their indices must be consecutive.

Xiao D greatly admires the light of the fireflies. He defines the overall brightness value of the firefly interval from index $L$ to $R$ as the $m$-th largest number among the brightness values of those fireflies. Xiao D is given $Q$ thresholds. Each threshold gives a number $x$. You need to find how many firefly intervals have an overall brightness value greater than or equal to $x$. Of course, there can be many such intervals, and you need to help Xiao D count them.

Input Format

The first line contains five integers $n,k,m,B,cas$, where $B$ is a given constant, and $cas$ is the Subtask ID of the current test point.

The second line contains $n$ integers $a_i$ separated by spaces, representing the brightness values of the $n$ fireflies. They are generated by the given code.

The third line contains an integer $Q$, denoting the number of thresholds.

The fourth line contains $Q$ integers separated by spaces, representing the threshold $x$ for each query, generated by the given code.

The input size of this problem is large. The input data can be generated by the following code: The full code can be viewed here.

// 请注意避免整形溢出 
#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());
}

You only need to generate the input according to the code above. For specific operation explanations, please refer to the sample explanation. The solution to this problem is unrelated to how the data is generated.

Output Format

For each query threshold, you need to compute the number of corresponding firefly intervals.

To avoid excessive output, please output the xor sum of the numbers of firefly intervals over the $Q$ queries. For specific operation explanations, please refer to the sample explanation.

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

Hint

[Sample Explanation $\mathbf 1$]

The brightness values of the fireflies from $1$ to $n$ are: $5,4,2,3,1$. There are $6$ firefly intervals in total. We take the $2$-nd largest value in each interval; they are:

• The fireflies with indices $1$ to $3$ are $[5,4,2]$, and the overall brightness value is $4$.
• The fireflies with indices $2$ to $4$ are $[4,2,3]$, and the overall brightness value is $3$.
• The fireflies with indices $3$ to $5$ are $[2,3,1]$, and the overall brightness value is $2$.
• The fireflies with indices $1$ to $4$ are $[5,4,2,3]$, and the overall brightness value is $4$.
• The fireflies with indices $2$ to $5$ are $[4,2,3,1]$, and the overall brightness value is $3$.
• The fireflies with indices $1$ to $5$ are $[5,4,2,3,1]$, and the overall brightness value is $4$.

There are $5$ queries. The thresholds are $2,2,2,0,2$, so the answers are $6,6,6,6,6$. The total xor value is $6$.

[Sample Explanation $\mathbf 2$]

The brightness values of the fireflies from $1$ to $n$ are: $3,1,4,2,5,6$.

There are $5$ queries. The thresholds are $1,5,1,4,6$, and the answers are $10,4,10,7,0$. The total xor value is $3$.

[Sample Explanation $\mathbf 3$] This testdata satisfies the constraints of Subtask 4. The detailed solution is not explained. Please pay attention to integer overflow issues.

[Sample Explanation $\mathbf 4$] This testdata satisfies the constraints of Subtask 5. The detailed solution is not explained.

[Sample Explanation $\mathbf 5$] This testdata satisfies the constraints of Subtask 8. The detailed solution is not explained.

[Constraints and Notes]

This problem uses bundled subtask testing. The input/output size is not very large, but please optimize constants. This problem automatically enables O2 optimization.

• 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$.

For all test points: $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$.

Translated by ChatGPT 5