Description

There are $n$ candidate contestants in IOI 2077, numbered $1 \sim n$. Each candidate contestant has an ability value, and all ability values are distinct. The ability value of the $i$-th candidate is $a_i$. Little A prefers ordered numbers, so he sorts these $n$ candidates by ability value in increasing order, i.e. $a_i < a_{i+1}\ (1 \leq i < n)$.

The official contestants will be chosen from these $n$ candidates. Specifically, all contestants will be a substring $[l, r]$ of the candidates, i.e. candidates with indices $l, l+1, \cdots, r$ will participate in IOI 2077. Little A’s index is $k$. Since he knows he has been appointed to participate, we must have $l \leq k \leq r$. There are $q$ possible cases of contestants. Each case is described by three numbers $l_i, r_i, k_i\ (l_i \leq k_i \leq r_i)$, meaning the contestants are the candidates with indices in $[l_i, r_i]$, and Little A’s index is $k_i$.

Because he is not strong enough, Little A feels overwhelmed by the coming IOI. He decides to choose some contestants as teammates and help (zuo) each other (bi) during the contest. Specifically, let the number of official contestants be $s$. Then Little A will choose an integer $m$ uniformly at random from $[0, \lfloor \frac{s-1}{2} \rfloor]$, and then randomly select $2m$ people from the $s$ contestants as his teammates. However, Little A does not want to look too weak, so his ability value $a_k$ must be the median of the ability values of these $2m+1$ people.

As the saying goes, there is strength in numbers. Little A hopes the sum of the ability values of himself and all selected teammates is as large as possible. But before that, he wants to know the expected value of this sum. Output the result modulo $998244353$, and it is guaranteed that the answer is well-defined under this modulus. For each possible contestants case, you need to compute the answer for that case. To avoid too much output, you only need to compute the XOR of all answers.

Input Format

The first line contains an integer $t$, the Subtask id of this test point.
The second line contains two integers $n, q$, representing the number of candidate contestants and the total number of cases.
The third line contains $n$ integers $a_1, a_2, \cdots, a_n$, representing the ability values of each candidate contestant. It is guaranteed that $a_i$ is increasing.
The next $q$ lines each contain three integers $l_i, r_i, k_i$ describing one possible contestants case.

Output Format

Output one line with one integer, the XOR of all answers.

0
5 2
2 3 5 7 8
1 5 3
2 4 2

499122189

Hint

"Sample 1 Explanation"

• Query 1:
  Since $s_1 = r_1 - l_1 + 1 = 5$, $m$ can be $0, 1$, or $2$.
  When $m = 0$: Little A has no teammates, so the expected value is his own ability value $a_{k_1} = a_3 = 5$.
  When $m = 1$: Little A can choose contestants with indices $(1, 4)$ or $(1, 5)$ or $(2, 4)$ or $(2, 5)$ as his teammates. The sums of abilities are $14, 15, 15, 16$ respectively, so the expected value is $\frac{14+15+15+16}{4} = 15$.
  When $m = 2$: Little A can only choose everyone, so the expected value is $2+3+5+7+8 = 25$.
  Therefore, the expected value is $\frac{5+15+25}{3} = 15$.

• Query 2:
  Since $s_2 = r_2 - l_2 + 1 = 3$, $m$ can be $0$ or $1$.
  When $m = 0$: Little A has no teammates, and the expected value is $3$.
  When $m = 1$: Little A cannot make any choice, so the expected value is $0$.
  Therefore, the expected value is $\frac{3+0}{2} = \frac{3}{2}$, which becomes $499122178$ after taking modulo $998244353$.

$15 \oplus 499122178 = 499122189$.

"Constraints and Conventions"

This problem uses bundled tests.

Let $s_i = r_i - l_i + 1$.

• Subtask #0 (1 point): the samples.
• Subtask #1 (10 points): $s_i \leq 2$.
• Subtask #2 (20 points): $s_i \leq 16$, $q \leq 40$, $n \leq 640$.
• Subtask #3 (15 points): $s_i, q \leq 500$, $n \leq 10^5$.
• Subtask #4 (15 points): $s_i, q \leq 3 \times 10^3$, $n \leq 10^5$.
• Subtask #5 (15 points): $s_i, q \leq 2 \times 10^5$, $n \leq 5 \times 10^5$.
• Subtask #6 (24 points): no special constraints.

For $100\%$ of the testdata, $1 \leq n, q \leq 2 \times 10^6$, $1 \leq l_i \leq k_i \leq r_i \leq n$, $1 \le a_i \le 998244352$, $a_i < a_{i+1}\ (1 \leq i < n)$.

For all test points, the time limit is 1s and the memory limit is 512MB.

"Help / Tips"

About modulo of rational numbers, median.

The input and output size of this problem is extremely large, please pay attention to I/O optimization.
This problem provides a fast input template for signed 32-bit integers, guaranteeing the total reading time does not exceed 250ms:

#define gc getchar()
inline int read(){
	int x=0; bool sgn=0; char s=gc;
	while(!isdigit(s))sgn|=s=='-',s=gc;
	while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=gc;
	return sgn?-x:x;
}

// 如果需要读入直接调用 read() 即可。
// 一个例子（与正解无关，仅供参考）：

int t=read(),n=read(),q=read();
int a[2000005],l[2000005],r[2000005],k[2000005];
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=q;i++)l[i]=read(),r[i]=read(),k[i]=read();

// 这样你就可以在 250ms 内读入全部数据了。

"Source"

Sweet Round 07 C.
idea & solution: SSerWarriors_Cat; data: Alex_Wei; validation: chenxia25。

After IOI 2077 ended, Little A successfully AK-ed IOI thanks to his outstanding (dui) performance (you) and great (bang) teamwork (zhu). This made him recall his once-passionate self and the comrades who fought alongside him on the OI path. Now they are far apart, and it has been more than ten years since they last met, but their sincere friendship has not faded, and it will never fade.

"Grandpa, there is a recording in your phone, and it also says 'ycx txdy!'."
"Oh, really? Play it for me."

"I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you are vegetable chickens."
"I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you are vegetable chickens."
"I AK IOI. I AK ACM World Final. I AK Universe OI. I think all of you ............"

2077.7.7

Translated by ChatGPT 5