P5107 Energy Harvesting

**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$.

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.

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$.

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