Description：

求： $$ ans[k]=\sum_{i=1}^n\sum_{j=1}^m(a_i+b_j)^k,k\in[1,t] $$ $1\leqslant n,m,t\leqslant 10^5$

Solution：

先用二项式定理展开一下，然后交换求和号： $$ ans[k]=\sum_{v=0}^k\binom kv\Bigl(\sum_{i=1}^na_i^v\Bigr)\Bigl(\sum_{j=1}^mb_j^{k-v}\Bigr) $$ 构造生成函数： $$ A(x)=\sum_{i\geqslant 0}\Bigl(\sum_{k=1}^na_k^i\Bigr)x^i\\ B(x)=\sum_{i\geqslant 0}\Bigl(\sum_{k=1}^mb_k^i\Bigr)x^i $$ 那么： $$ ans[k]=k!\sum_{v=0}^k\frac{[x^v]A(x)}{v!}\frac{[x^{k-v}]B(x)}{(k-v)!} $$ 如果我们能求出 $A(x)$ 和 $B(x)$ ，那么后面就是个卷积， $NTT$ 就可以了。

以 $A(x)$ 为例： $$ \begin{align} F(x)&=\sum_{i\geqslant 0}\Bigl(\sum_{k=1}^na^i_k\Bigr)x^i\\ &=\sum_{k=1}^n\Bigl(\sum_{i\geqslant 0}a_k^ix^i\Bigr) \end{align} $$

也就是设： $$ F_k(x)=\sum_{i\geqslant 0}a_k^ix^i=\frac1{1-a_kx} $$ 我们发现： $$ \ln'(x)=\frac 1 x $$ 因此，根据链式法则，有： $$ (\ln(1-a_kx))'=\ln'(1-a_kx)(1-a_kx)'=\frac{-a_k}{1-a_kx}=\sum_{i\geqslant 0}-a_k^{i+1}x^i=-\frac{F_k(x)-1}x $$ 设 $G_k(x)=(\ln(1-a_kx))'$ ，也就是说 $G_k(x)=-\frac{F_k(x)-1}x\Longleftrightarrow F_k(x)=-xG(x)+1$ 。

设： $$ G(x)=\sum_{k=1}^nG_k(x) $$ 那么： $$ F(x)=-xG(x)+n $$ 考虑怎么算 $G$ ： $$ G(x)=\sum_{k=1}^nG_k(x)=\sum_{k=1}^n(\ln(1-a_kx))'=\biggl(\ln\Bigl(\prod_{k=1}^n(1-a_kx)\Bigr)\biggr)' $$ 后面那个东西就可以分治 $NTT$ 计算了，然后再搬一个多项式 $\ln$ 的板子就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

int t;

#define MAXN 270000

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

#define R register

#define I inline

int a[MAXN],b[MAXN];

int fac[MAXN],ifac[MAXN];

#define P 998244353

namespace polynomial

{

	I int power(int a,int b)

	{

		R int res = 1;

		for(;b > 0;b = b >> 1,a = 1ll * a * a % P)if(b & 1)res = 1ll * res * a % P;

		return res;

	}

	I int inver(int a){return power(a,P - 2);}

	int cnt = 0;

	struct poly

	{

		int a[MAXN];

		int d;

		I int& operator [](int x){return a[x];}

		I int operator [](int x)const{return a[x];}

		poly(){d = 0;memset(a,0,sizeof(a));}

		I poly& operator =(const poly& b)

		{

			for(R int i = b.d + 1;i <= d;++i)a[i] = 0;

			d = b.d;

			for(R int i = 0;i <= b.d;++i)a[i] = b[i];

			return *this;

		}

		I void clear()

		{

			for(R int i = 0;i <= d;++i)a[i] = 0;

			d = 0;

			return;

		}

	};

	int rev[MAXN];

	int ww[MAXN << 1],*g = ww + MAXN;

	I int init(int n)

	{

		R int l = 0,len = 1;

		for(;len <= n;len = len << 1)++l;

		for(R int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

		g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

		for(R int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

		return len;

	}

	I void NTT(poly &f,int l,int type)

	{

		for(R int i = 0;i < l;++i)

		{

			if(i < rev[i])swap(f[i],f[rev[i]]);

		}

		for(R int i = 2;i <= l;i = i << 1)

		{

			R int wn = g[type * l / i];

			for(R int j = 0;j < l;j += i)

			{

				R int w = 1;

				for(R int k = j;k < j + i / 2;++k)

				{++cnt;

					R int u = f[k],t = 1ll * f[k + i / 2] * w % P;

					f[k] = (u + t >= P ? u + t - P : u + t);

					f[k + i / 2] = (u - t < 0 ? u - t + P : u - t);

					w = 1ll * w * wn % P;

				}

			}

		}

		if(type == -1)

		{

			R int ni = power(l,P - 2);

			for(R int i = 0;i < l;++i)f[i] = 1ll * f[i] * ni % P;

		}

		return;

	}

	I poly operator * (poly &a,poly &b)

	{

		poly x = a,y = b;

		x.d = a.d + b.d;

		R int len = init(x.d);

		NTT(x,len,1);NTT(y,len,1);

		for(R int i = 0;i < len;++i)x[i] = 1ll * x[i] * y[i] % P;

		NTT(x,len,-1);

		return x;

	}

	poly invtmp;

	void calc_inv(poly &a,poly &b,int deg)

	{

		if(deg == 1)

		{

			b[0] = power(a[0],P - 2);

			return;

		}

		calc_inv(a,b,((deg + 1) >> 1));

		R int len = init(deg << 1);

		for(R int i = 0;i < deg;++i)invtmp[i] = a[i];

		for(R int i = deg;i < len;++i)invtmp[i] = 0;

		NTT(invtmp,len,1);NTT(b,len,1);

		for(R int i = 0;i < len;++i)b[i] = (2ll * b[i] - 1ll * b[i] * b[i] % P * invtmp[i] % P + P) % P;

		NTT(b,len,-1);

		for(R int i = deg;i < len;++i)b[i] = 0;

		return;

	}

	I poly inv(poly k,poly &res,int deg)

	{

		calc_inv(k,res,deg + 1);

		res.d = deg;

		while(res.d > 0 && res[res.d] == 0)--res.d;

		return res;

	}

}

using namespace polynomial;

poly s[19];

int val[MAXN];

void solve(int d,int l,int r)

{

	if(l == r){s[d].clear();s[d][0] = 1;s[d][1] = (P - val[l]) % P;s[d].d = 1;return;}

	R int mid = ((l + r) >> 1);

	solve(d + 1,l,mid);s[d] = s[d + 1];

	solve(d + 1,mid + 1,r);

	s[d].d = s[d].d + s[d + 1].d;

	R int len = init(s[d].d);

	NTT(s[d],len,1);NTT(s[d + 1],len,1);

	for(R int i = 0;i < len;++i)s[d][i] = 1ll * s[d][i] * s[d + 1][i] % P;

	NTT(s[d],len,-1);

	for(int i = 0;i < len;++i)s[d + 1][i] = 0;

	return;

}

poly calc(int a[],int n,int deg)

{

	for(R int i = 1;i <= n;++i)val[i] = a[i];

	solve(1,1,n);

	R poly k;

	R poly x;x.d = s[1].d - 1;for(R int i = 0;i <= x.d;++i)x[i] = 1ll * (i + 1) * s[1][i + 1] % P;

	R poly y;calc_inv(s[1],y,deg + 1);y.d = deg;while(y.d > 0 && y[y.d] == 0)--y.d;

	x.d = x.d + y.d;

	R int len = init(x.d);

	NTT(x,len,1);NTT(y,len,1);

	for(R int i = 0;i < len;++i)x[i] = 1ll * x[i] * y[i] % P;

	NTT(x,len,-1);

	s[1].clear();

	for(R int i = deg + 1;i <= x.d;++i)x[i] = 0;x.d = deg;

	for(R int i = deg;i >= 0;--i)x[i] = 1ll * x[i - 1] * (P - 1) % P;

	x[0] = n % P;

	return x;

}

int main()

{freopen("in.in","r",stdin);freopen("out.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(R int i = 1;i <= n;++i)a[i] = rd();

	for(R int i = 1;i <= m;++i)b[i] = rd();

	scanf("%d",&t);

	R poly A = calc(a,n,t),B = calc(b,m,t);

	fac[0] = 1;for(R int i = 1;i <= t;++i)fac[i] = 1ll * fac[i - 1] * i % P;

	ifac[t] = power(fac[t],P - 2);for(R int i = t - 1;i >= 0;--i)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;

	for(R int i = 0;i <= A.d;++i)A[i] = 1ll * A[i] * ifac[i] % P;

	for(R int i = 0;i <= B.d;++i)B[i] = 1ll * B[i] * ifac[i] % P;

	R poly res = A * B;

	for(R int i = 1;i <= t;++i)printf("%lld\n",1ll * res[i] * fac[i] % P * inver(1ll * n * m % P) % P);

	return 0;

}