题目描述

题面已修改，请大家注意。

请你求下列式子：$\sum_{i=1}^N\sum_{j=1}^Ngcd(i,j)$ ，答案对大质数取模。

不好意思读错剧本了。

给定一个 $n$ 个点 $m$ 条边的有向图，每个点有初始能量 $a_i$ 。

每过一秒，每个点的能量便会等量地流向所有出边，另外，会有一份流向自己（你可以当做有一个自环）。

现在 $dkw$ 有 $q$ 次询问，每次询问会给你一个时间 $t$ ，$dkw$想知道 $t$ 秒时每个点的能量。

不保证图中没有重边和自环，答案对$998244353$取模。

输入格式

第一行包含三个整数，$n,m,q$ 。

第二行包含$n$个整数，从$a_1$到$a_n$ ，代表初始能量。

接下来 $m$ 行，每行包含两个正整数 $x_i,y_i$ ，代表一条有向边，从 $x_i$ 指向 $y_i$ ，我们约定点编号从 $1$ 到 $n$ 。

接下来 $q$ 行，每行包含一个正整数 $t$ ，代表一次询问。

输出格式

为了防止输出过大，对于每个询问你只需要输出一行一个非负整数，代表 $n$ 个点的能量（取模）的异或和对$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

提示

对于 30% 的数据，$1\le t \le 50$

对于 60% 的数据，$1\le q\le 50$

对于 80% 的数据，$1\le q\le 1000$

对于 100% 的数据，$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$