给定 $n$ 次多项式

$$f(x)=\sum _{i=0}^n{a}_i{x}^i$$

$Q$ 次询问，第 $i$ 次询问 $f(q_i)$ 对 $998244353$ 取模的值。

输入格式

由于本题的数据范围较大，所有测试点的 $q_i$ 将在程序内生成。

第一行两个整数 $n,Q$。$n,Q$ 的意义见题目描述。

第二行 $n+1$ 个整数，第 $i$ 个整数表示 $a_{i-1}$

第三行三个整数 $q_0,q_{\mathrm{x}},q_{\mathrm{y}}$，表示 $q_i$ 的生成方式。

$q_i$ 按照如下规则生成:

$\mathrm{\forall }1\le i\le Q,q_i=(q_{i-1}\times q_{\mathrm{x}}+q_{\mathrm{y}})mod998244353$

输出格式

由于输出规模过大，你只需要输出所有询问答案取完模之后的 $\mathrm{xor}$ 和即可。

样例一

input

2 2
1 2 3
1 2 1

output

128

explanation

$q_1=2\times q_0+1=3$

$q_2=2\times q_1+1=7$

答案 $=(1+2\times 3+3\times 3^2)\mathrm{xor}(1+2\times 7+3\times 7^2)=34\mathrm{xor}162=128$

样例二

见样例数据下载

数据范围

对于所有测试数据，满足 $1\le n\le 2.5\times {10}^5,1\le Q\le {10}^6,2\le q_{\mathrm{x}}<998244353,0\le q_0,q_{\mathrm{y}}<998244353$。

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$

下载

样例数据下载