Problem Description

The statement has been modified. Please pay attention.

Please compute the following expression: $\sum_{i=1}^N\sum_{j=1}^Ngcd(i,j)$, and take the answer modulo a large prime number.

Sorry, I read the wrong script.

You are given a directed graph with $n$ nodes and $m$ edges. Each node has an initial energy value $a_i$.

Every second, the energy at each node flows equally to all of its outgoing edges. In addition, one share flows to itself (you may treat this as having a self-loop).

Now $dkw$ has $q$ queries. Each query gives a time $t$, and $dkw$ wants to know the energy at each node after $t$ seconds.

The graph is not guaranteed to be free of multiple edges or self-loops. All answers are taken modulo $998244353$.

Input Format

The first line contains three integers, $n,m,q$.

The second line contains $n$ integers, from $a_1$ to $a_n$, representing the initial energy.

The next $m$ lines each contain two positive integers $x_i,y_i$, representing a directed edge from $x_i$ to $y_i$. We assume the nodes are numbered from $1$ to $n$.

The next $q$ lines each contain one positive integer $t$, representing a query.

Output Format

To avoid overly large output, for each query you only need to output one line with one non-negative integer, which is the XOR sum of the energies (modulo) of the $n$ nodes, and then taken modulo $998244353$.

5 10 3
4 5 3 2 7 
4 1
1 4
2 1
3 2
1 2
5 1
2 4
2 1
2 4
1 4
1
2
3

15
548614965
80769513

Hint

For $30\%$ of the testdata, $1\le t \le 50$.

For $60\%$ of the testdata, $1\le q\le 50$.

For $80\%$ of the testdata, $1\le q\le 1000$.

For $100\%$ of the testdata, $1\le n\le 50,1\le m\le n\times (n-1),1\le q\le 5\times 10^4,0< a_i< 998244353,1\le t\le 10^9$.

Translated by ChatGPT 5