这是个结论题……而且结论还很好猜……
可以观察，n那么大，而刚开始只有f(i)=i和f(i)=i^2，可以猜一个结论：
一次函数洗牌之后的期望还是一次函数，二次函数洗牌之后的期望还是二次函数。
而洗牌两次后的期望，和用洗牌一次后的期望作为权值，再洗第二次牌得到的期望，结果应该是一样的。这个很好证，因为期望是线性可加的，而每次洗牌后，一个特定位置上的值，是每个位置原来的权值乘以特定的常数（这个常数在下面的证明过程中有推导）相加，只涉及到一些变量期望的线性相加，所以是可以的。注意，这点虽然比较显然，但有些时候不一定是对的，所以这种东西还要先思考一下。
那前面这个结论是不是对的呢？可以写个这样的程序试试，测一下样例，对拍一下，好像还真是这样。那不是就做完了吗？具体做法：每一次选三个好算的算出来，然后把二次函数给算出来（可以待定系数解方程，也可以直接拉格朗日插值），不就可以了吗？选的时候可以选最开始的三个（这样可以二阶差分），也可以选前两个加最后一个，因为这个洗牌的过程可以想成在第一堆和第二堆中任选一个放到牌堆顶，也就是随机打乱（这个在证明2中有说明），然后，把第一堆的拿出来安原来的顺序排好，把第二堆按原来的顺序排好。这样就会发现算最后一个和算第一个是一样好算的。
记第i个数是x_i，洗牌后第一个数的期望x_i'=\frac Anx_1+\frac{n-A}nx_{A+1}，最后一个数的期望x_n'=\frac Anx_A+\frac{n-A}nx_n（有\frac An的概率是抽到第一堆，\frac{n-A}n的概率是抽到第二堆，而且肯定是最后一个），第二个数的期望x_2'=\frac An(\frac{A-1}{n-1}x_2+\frac{n-A}{n-1}x_{A+1})+\frac{n-A}n(\frac A{n-1}x_1+\frac{n-A-1}{n-1}x_{A+2})，前者是对应第一个抽到的是第一堆，后者是对应第一个抽到的是第二堆。
这就可以愉快地把这题A了。代码在最后（代码1）。
当然有个非常关键的问题，这个结论为什么是对的？
证明1
我们证明这样一个东西：一个序列\{a_i\}（等一下，上面是x怎么就变a了……懒得改了）满足a_i=f(i)，其中f(i)为多项式，则对于洗牌后的序列\{a_i'\}，存在一个多项式f'(i)使得a_i'=f'(i)且\deg f\geqslant\deg g，这样就能保证选\deg f+1个数插值后的结果就是f'。为了方便，记\deg f=m。
大量公式警告
我们先要知道转移式。考虑a_j\ (j\leqslant A)对a_i'的贡献，即a_j乘以洗牌后第i张是原先的第j张得概率。考虑某一种情况的概率大概长这样（某一特殊但平凡的情况）：\frac An\cdot\frac {A-1}{n-1}\cdot\frac {n-A}{n-2}\cdot\cdots\cdot\frac{A-j+1}{n-i+2}\cdot\frac{n-A-i+j+1}{n-i+1}。观察发现虽然每个分数都没什么规律，每次乘的分数也不是固定的，但是容易发现分子是A^\frac{j}{}(n-A)^\frac{i-j}{}，分母是n^\frac{i}{}。而a_i'前面有i-1个数，当中有j-1的数是第一堆的，所以要再乘一个\binom{i-1}{j-1}。j>A时同理。
那么就有
a_i'=\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}A^\frac{j}{}(n-A)^\frac{i-j}{}\frac1{n^\frac i{}}+\sum_{j=1}^{n-A}a_{A+j}\dbinom{i-1}{j-1}A^\frac{i-j}{}(n-A)^\frac j{}\frac1{n^\frac{i}{}}
其实前后两个式子形式上还是没什么区别，我们就先看前一部分。化简它。
\begin{aligned}&\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}A^\frac{j}{}(n-A)^\frac{i-j}{}\frac1{n^\frac i{}}\\=&\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}\frac{A!}{(A-j)!}\cdot\frac{(n-A)!}{(n-A-i+j)!}\cdot\frac{(n-i)!}{n!}\\=&\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}\frac{(n-i)!}{(A-j)!(n-A-i+j)!}\cdot\frac{A!(n-A)!}{n!}\\=&\frac{A!(n-A)!}{n!}\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}\frac{(n-i)!}{(A-j)!(n-A-i+j)!}\\=&\frac1{\dbinom nA}\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\end{aligned}
好像化简不了了……但我们好像忘了一个条件？a_i可以表示成至多m次（本题m\leqslant2）的多项式！这又有什么用呢？
注意到，这里的转移，都是某个位置的数。乘上一个和这个数无关的常数，也就是说，它是线性的，就是将输入的一些数据线性相加（即乘一个常数后相加）的结果，和原先这些输入后分别得到的结果，进行相同的线性相加，得到的结果是一样的（这也不难验证）。若对于所有小于m次的多项式f(x)都可以表示成\sum_{k=0}^mc_kf_k(x)，其中c_k为常数，f_k是次数为k的多项式，我们就只需要证明当a_i=f_k(i)时，a_i'可以被表示成至多k次的多项式即可。
现在，只需要找到一个便于我们证明的f_k即可。首先想到的可能是f_i(x)=x^i，但这里的系数都是阶乘和二项式，所以更应该尝试下降幂（我们知道m次下降幂多项式可以和m次多项式一一对应），尝试后发现好像f_k(x)=(x-1)^\frac k{}最方便（可能一个理由是下标从0开始更自然？我随便说的。），而且我们知道，一个任意的m次多项式，总是可以被表示成m次的下降幂多项式。那么将a_j=(j-1)^\frac k{}带入并来一些操作得：
\begin{aligned}&\frac1{\dbinom nA}\sum_{j=1}^Aa_j\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\\=&\frac1{\dbinom nA}\sum_{j=1}^A(j-1)^\frac k{}\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\\=&\frac1{\dbinom nA}\sum_{j=1}^A\frac{(j-1)!}{(j-1-k)!}\cdot\frac{k!}{k!}\cdot\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\\=&\frac1{\dbinom nA}\sum_{j=1}^Ak!\dbinom{j-1}{k}\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\\=&\frac{k!}{\dbinom nA}\sum_{j=1}^A\dbinom{j-1}{k}\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\end{aligned}
而二项式当中有个东西：
\begin{aligned}\dbinom ab\dbinom ca&=\frac{a!}{b!(a-b)!}\cdot\frac{c!}{a!(c-a)!}\\&=\frac{c!}{b!(c-b)!}\cdot\frac{(c-b)!}{(a-b)!(c-a)!}\\&=\dbinom cb\dbinom{c-b}{a-b}\end{aligned}
所以令j-1=a,\ k=b,\ i-1=c，则有
\begin{aligned}&\frac{k!}{\dbinom nA}\sum_{j=1}^A\dbinom{j-1}k\dbinom{i-1}{j-1}\dbinom{n-i}{A-j}\\=&\frac{k!}{\dbinom nA}\sum_{j=1}^A\dbinom{i-1}k\dbinom{i-1-k}{j-1-k}\dbinom{n-i}{A-j}\\=&\frac{k!}{\dbinom nA}\dbinom{i-1}k\sum_{j=1}^A\dbinom{i-1-k}{j-1-k}\dbinom{n-i}{A-j}\\=&\frac{k!}{\dbinom nA}\dbinom{i-1}k\sum_j\dbinom{i-1-k}{j-1-k}\dbinom{n-i}{A-j}\\=&\frac{k!}{\dbinom nA}\dbinom{i-1}k\sum_j\dbinom{i-1-k}j\dbinom{n-i}{A-j-1-k}\end{aligned}
（倒数第二行可以把限制去掉因为显然j-1-k\geqslant0,\ j\leqslant A，即A\geqslant j\geqslant1+k\geqslant1时后一串不为0。最后一行是把j用j+1+k代替。）我们又提出了一项！继续。二项式当中还有一个东西：
\sum_j\dbinom nj\dbinom m{k-j}=\dbinom{n+m}k
这个式子为什么是对的呢？考虑组合意义。设有n个红球，m个蓝球，左式为对于每个j，当红球取j个，蓝球取k-j个的方案数之和，相当于总共n+m个球中取k个球的方案数，即为右式。
令i-1-k=n,\ n-i=m,\ A-1-k=k（这里右式的n,m,k为上式中的），继续：
\begin{aligned}&\frac{k!}{\dbinom nA}\dbinom{i-1}k\sum_j\dbinom{i-1-k}j\dbinom{n-i}{A-j-1-k}\\=&\frac{k!}{\dbinom nA}\dbinom{i-1}k\dbinom{i-1-k+n-i}{A-1-k}\\=&\frac{k!}{\dbinom nA}\dbinom{i-1}k\dbinom{n-k-1}{A-k-1}\end{aligned}
我们把和式打开了！继续稍微化简一下：
\begin{aligned}&\frac{k!}{\dbinom nA}\dbinom{i-1}k\dbinom{n-k-1}{A-k-1}\\=&k!\frac{(i-1)!}{k!(i-1-k)!}\cdot\frac{\dbinom{n-k-1}{A-k-1}}{\dbinom nA}\\=&\frac{(i-1)!}{(i-1-k)!}\cdot\frac{\dbinom{n-k-1}{A-k-1}}{\dbinom nA}\\=&(i-1)^\frac k{}\cdot\frac{\dbinom{n-k-1}{A-k-1}}{\dbinom nA}\end{aligned}
搞出来了！？也就是说当a_i=(i-1)^\frac k{}时，a_i'的一部分是\begin{aligned}(i-1)^\frac k{}\cdot\frac{\binom{n-k-1}{A-k-1}}{\binom nA}\end{aligned} ，也是k次的下降幂。结合前面的说明，可得当a_i是m次多项式时，a_i'的这一部分也是不多于m次的多项式。
而另一部分呢？（虽然同理但还有一些差别。）设b_i=a_{A+i}，比较一下式子，当b_i=(i-1)^\frac k{}时，还是有a_i'的另一部分是\begin{aligned}(i-1)^\frac k{}\cdot\frac{\binom{n-k-1}{n-A-k-1}}{\binom n{n-A}}\end{aligned}（其实下面分母也是\begin{aligned}\binom nA\end{aligned}），所以a_i'就是至多m次的多项式。 证毕。
当然，有了这个式子也可以写一份代码，就是每次记录下降幂多项式的系数（初始条件可能要手算一下），然后可以直接转移，每一项按照这个式子给出的，乘上一个系数，就不用插值了。当然要注意，要将a_i的多项式平移后才是b_i（设a_i=f(i)，则b_i=a_{A+i}=f(A+i)。这个平移可能又要手算一下）。可以参考代码2（如果懒得手算就参考一下代码里的那些系数）。
这个证明算是比较完整了，但好像还有点问题，最后这个式子好像有点过于简单？有没有更好的证明方法？
证明2
为了方便起见，根据我们上面的讨论，我们只要证明：一堆牌有A张，其中a_i=(i-1)^\frac k{}\ (1\leqslant i\leqslant A)；另一堆牌有n-A张，其中所有牌的数都为0，则洗完牌后每张的期望为\begin{aligned}a_i'=(i-1)^\frac k{}\cdot\frac{\binom{n-k-1}{A-k-1}}{\binom nA}\end{aligned}\ (1\leqslant i\leqslant n)。（因为前面说的“一部分”其实就是第一堆对答案的贡献，而我们这里直接把第二堆的贡献省略，下面也不讨论第二堆的贡献，因为就是0）。
那么，因为这个洗牌的过程是线性的，我们可以所有的权值都缩小到原来的\frac1{k!}，我们知道\begin{aligned}\frac{(i-1)^\frac k{}}{k!}=\frac{(i-1)!}{k!(i-1-k)!}=\binom{i-1}{k}\end{aligned}，则我们只需要证明当\begin{aligned}a_i=\binom{i-1}k\end{aligned}时，\begin{aligned}a_i'=\frac{\binom{i-1}k\binom{n-k-1}{A-k-1}}{\binom nA}\end{aligned}即可。
我们先证明一个前面提到过的结论（这里写得清晰一些）：这样的洗牌相当于，把所有的混在一起，然后把每一堆中的元素，按在原来堆中的顺序，在新堆中排好。可能有点抽象，举个例子：
为了方便讨论，这里和下面都用颜色代表所属的堆。假设两堆牌是\color{red}1,\color{red}2,\color{red}3和\color{blue}4,\color{blue}5,\color{blue}6，那么随机打乱后有可能是这样的：\color{red}2,\color{red}1,\color{blue}5,\color{blue}4,\color{red}3,\color{blue}6，然后\color{red}2,\color{red}1,\color{red}3排成\color{red}1,\color{red}2,\color{red}3，\color{blue}5,\color{blue}4,\color{blue}6排成\color{blue}4,\color{blue}5,\color{blue}6，然后按\color{red}2,\color{red}1,\color{blue}5,\color{blue}4,\color{red}3,\color{blue}6的颜色插回去变成\color{red}1,\color{red}2,\color{blue}4,\color{blue}5,\color{red}3,\color{blue}6。差不多就是这个意思。
证明的话考虑洗牌的过程，我们不考虑每一张牌具体是哪一张，而只考虑颜色，有\frac X{X+Y}的概率抽到红色，而红色有X张，所以抽到红色的特定一张的概率是\frac X{X+Y}\cdot\frac1X=\frac1{X+Y}，蓝色同理，而剩下牌的数量刚好是X+Y，就相当于，每一次都随机摸一张牌。这不就和随机打乱一样了吗。而洗牌前后相对位置不变，所以我们确定了颜色之后，就可以确定每一张牌的数。这个性质可以当结论记一下。
有了这个很好的性质，该怎么用呢？
先考虑有多少种情况，显然，根据颜色打乱后有\begin{aligned}\binom nA\end{aligned}中等概率的情况，我们只要算出所有情况下a_j'的和，先看一下a_i对a_j'的贡献。
因为\begin{aligned}a_i=\binom{i-1}k\end{aligned}，我们把它看成，在1到i-1中，把其中k个做上标记的方案数。考虑对a_j'的贡献时，要把a_i强行放到a_j'上，此时（洗牌后的排队中）1到j-1还要再选i-1个红的，后面j+1到n中还要选A-i个红的，然后统计方案数，而\begin{aligned}a_i=\binom{i-1}k\end{aligned}，所以它的贡献还要再乘上a_i，也就是相当于再在1到j-1中的i-1个红的，还要再选k个做标记，贡献其实是这样一个方案数。理一下，其实就是相当于在1到j-1中，有k个做了标记，还有i-k-1个红的，而在j+1到n中，有A-i个红的。
当我们考虑整个的贡献时，因为1\leqslant i\leqslant A，所以在j前后可以有所有情况的红色的个数，所以相当于在1到j-1中标记k个，在剩下没有标记且不是j的位子上（一共有n-k-1个位置），选A-k-1个红的，所以总的和是\begin{aligned}\binom{j-1}k\binom{n-k-1}{A-k-1}\end{aligned}。
而我们知道总的情况数是\begin{aligned}\binom nA\end{aligned}，所以\begin{aligned}a_j'=\frac{\binom{j-1}k\binom{n-k-1}{A-k-1}}{\binom nA}\end{aligned}，和前面我们要证明的式子一模一样！
所以我们用了一个非常巧妙的方法证出来了，我觉得这个证明方法还是非常神奇的（我想了好久）。
好了，说了这么多，可以上代码了。
代码1：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kcz=998244353;
const int maxn=10000005;
ll a,b,c,f[maxn];
int n;
inline ll qpow(ll a,ll k)
{
ll res=1;
while(k)
{
if(k&1) res=res*a%kcz;
if(k>>=1) a=a*a%kcz;
}
return res;
}
inline ll calc(ll x) { return ((a*x+b)%kcz*x+c)%kcz; } // 算第x个数的期望
int main()
{
int m,tp,i;
ll _,__,t1,t2,t3,t,___,sqn;
freopen("landlords.in","r",stdin),freopen("landlords.out","w",stdout);
scanf("%d%d%d",&n,&m,&tp),sqn=n*(ll)n%kcz;
_=qpow(n-1,kcz-2),__=qpow(n,kcz-2),___=qpow((-sqn+3*n-2)%kcz,kcz-2);
if(tp==1) a=c=0,b=1;
else a=1,b=c=0; // x_i=ai^2+bi+c
while(m--)
{
scanf("%lld",&t);
if(t==0 || t==n) continue;
t1=(calc(1)*t+calc(t+1)*(n-t))%kcz*__%kcz; // 第一个
t2=((calc(2)*(t-1)+calc(t+1)*(n-t))%kcz*t+(calc(1)*t+calc(t+2)*(n-t-1))%kcz*(n-t))%kcz*__%kcz*_%kcz; // 第二个
t3=(calc(t)*t+calc(n)*(n-t))%kcz*__%kcz; // 第n个
a=((2-n)*t1+(n-1)*t2-t3)%kcz*___%kcz;
b=((sqn-4)*t1+(1-sqn)*t2+3*t3)%kcz*___%kcz;
c=((4*n-2*sqn)*t1+(sqn-n)*t2-2*t3)%kcz*___%kcz; // 极其丑的差值
}
for(i=1;i<=n;i++)
f[i]=(calc(i)+kcz)%kcz;
scanf("%d",&m);
while(m--)
scanf("%lld",&t),printf("%lld\n",f[t]);
fclose(stdin),fclose(stdout);
return 0;
}
代码2：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kcz=998244353;
const int maxn=10000005;
ll a,b,c,a_,b_,c_,fac[maxn],inv[maxn],inv_fac[maxn];
int n;
inline ll f(ll x) { return (a+b*(x-1)+c*(x-1)%kcz*(x-2))%kcz; } // 算第x个数的期望
inline ll C(int n,int m) { return (m>=0 && m<=n)?fac[n]*inv_fac[m]%kcz*inv_fac[n-m]%kcz:0; } // 判一下0的情况
inline ll invC(int n,int m) { return inv_fac[n]*fac[m]%kcz*fac[n-m]%kcz; }
int main()
{
int i,q,op,A;
ll t;
freopen("landlords.in","r",stdin),freopen("landlords.out","w",stdout);
scanf("%d%d%d",&n,&q,&op);
if(op==1) a=b=1,c=0; // a_i=a+b*(i-1)+c*(i-1)*(i-2)
else a=1,b=3,c=1;
fac[0]=inv_fac[0]=inv[1]=fac[1]=inv_fac[1]=1;
for(i=2;i<=n;i++)
{
fac[i]=fac[i-1]*i%kcz;
inv[i]=-(kcz/i)*inv[kcz%i]%kcz;
inv_fac[i]=inv_fac[i-1]*inv[i]%kcz;
}
while(q--)
{
scanf("%d",&A);
a_=(a+b*A+c*A%kcz*(A-1ll))%kcz; // 平移x->x+A
b_=(b+c*2*A)%kcz;
c_=c;
t=invC(n,A);
a=(a*C(n-1,A-1)+a_*C(n-1,n-A-1))%kcz*t%kcz; // 更新系数
b=(b*C(n-2,A-2)+b_*C(n-2,n-A-2))%kcz*t%kcz;
c=(c*C(n-3,A-3)+c_*C(n-3,n-A-3))%kcz*t%kcz;
}
scanf("%d",&q);
while(q--)
scanf("%d",&i),printf("%lld\n",(f(i)+kcz)%kcz);
fclose(stdin),fclose(stdout);
return 0;
}