你有 nn 个数组成的序列 [a_1\sim a_n][a
1
∼a
n
]，初始时 a_i=0a
i
=0。
有 qq 次操作组成的操作序列 AA，第 ii 次操作在所有可能的 nN(n+1)nN(n+1) 种操作之内均匀随机：
在以下两种操作之中以一半的概率随机选择一种操作，作为这次操作。
随机选取满足条件的正整数 l,r,x\ (1\le l\le r\le n,1\le x\le N)l,r,x (1≤l≤r≤n,1≤x≤N)，把 [l,r][l,r] 区间内的数加上 xx。
随机选取满足条件的正整数 l,r,x\ (1\le l\le r\le n,1\le x\le N)l,r,x (1≤l≤r≤n,1≤x≤N)，把 [l,r][l,r] 区间内的数改为 xx。
容易发现每次操作共有 nN(n+1)nN(n+1) 种可能。
由于这棵树是 ToothPaste Tree，只有在你询问的时候，它才会执行与你这次询问有关且还没执行的操作。具体地，假设你依次询问了 a_{p_1\sim p_m}a
p
1
∼p
m
的值，则
询问 a_{p_i}a
p
i
时，把所有 AA 中与这个数有关的操作（即这次操作的 [l,r][l,r] 包含 p_ip
i
）按时间顺序（即按 AA 中的顺序）执行了，并从 AA 中删除它们。然后输出 a_{p_i}a
p
i
当前的值。
比如 AA 中目前按顺序有以下四个操作，且 aa 中所有元素目前都是 00：
给区间 [2,3][2,3] 加一。
给区间 [3,4][3,4] 加一。
把区间 [2,4][2,4] 赋值为一。
给区间 [2,3][2,3] 加一。
现在询问了 a_2a
2
的值，那么操作 1,3,41,3,4 会被顺序执行，导致 a_1\sim a_4a
1
∼a
4
分别变为 [0,2,2,1][0,2,2,1]。因此 ToPTree 输出 22。操作序列变为：
给区间 [3,4][3,4] 加一。
再询问 a_3a
3
的值，操作 11 会被执行，导致操作序列变为空，并且 a_1\sim a_4a
1
∼a
4
变为 [0,2,3,2][0,2,3,2]，故输出 33。注意这个输出结果与按照顺序执行所有操作 1\sim 41∼4 得到的结果并不一致。
给定 n,m,q,Nn,m,q,N 以及序列 pp，ToPTree 一共会按询问顺序输出 mm 个值，求这 mm 次输出分别的期望，对 998244353998244353 取模。
（第一次询问之前，没有任何操作被执行了。）
输入格式
第一行四个正整数 n,m,q,Nn,m,q,N。
接下来一行 mm 个正整数 p_1\sim p_mp
1
∼p
m
。
输出格式
输出一行 mm 个非负整数，用空格隔开，为答案，对 998244353998244353 取模。
```c++
#include <bits/stdc++.h>
using namespace std;
long long ll;
template<typename T>inline void read(T &FF){
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}
int a[100010],s[100010],n,T;
int main(){
read(n);read(T);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=1;i<=n;i++)s[i]=s[i-2]+a[i];
while(T--){
int l,r;
read(l);read(r);
if((r-l+1)%2==0)puts("0");
else{
int ans=(s[r]-s[l-2])%2;
printf("%d\n",ans);
}
}
return 0;
}
```