H-Convolution_2021牛客暑期多校训练营4

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Bob invented a new operation $\otimes$

Let $p_i$ denote the i-th prime number. If $x=\prod_{i}p_i^{a_i}$ and $y=\prod_{i}p_i^{b_i}$ , then

$x\otimes y=\prod_{i}p_i^{|a_i-b_i|}$

Now Bob have a sequence $a_{1...n}$ , he wants to calculate sequence $b_{1...n}$ satisfies:

$b_i=\sum_{1\leq j,k\leq n,j\otimes k=i}a_jk^c$

The answer may be very large, you only need to output:

$(b_1\mod 998244353)~xor~(b_2\mod 998244353)~...~xor~(b_n\mod 998244353)$

XOR means bitwise exclusive OR

输入描述:

The first line has two integers .

The second line has  integers .

输出描述:

Output the answer.

示例1

输入

复制

6 1
1 2 3 4 5 6

输出

复制