在幻象之夜的第十六个夜晚，骑士们聚集在一起，准备进行一场战斗。

两组骑士准备进行对决，每组包含 $n$ 名骑士。第一组中第 $i$ 名骑士的力量值为 $a_i$，第二组中第 $j$ 名骑士的力量值为 $b_j$。

你的任务是为今晚组织骑士之间的对决。每场对决涉及每组中的一名骑士，且每名骑士最多只能参加一场对决。对决的结果并不重要——真正重要的是对决变得多么狂野或疯狂。

一场对决的“疯狂度”（lunaticus）定义为参与对决的两名骑士的力量值之和。然而，有一个特殊条件：如果一场对决的疯狂度达到 $998244353$，它会溢出并重置为零。具体来说，第一组的第 $i$ 名骑士与第二组的第 $j$ 名骑士之间的对决，其疯狂度为 $(a_i + b_j) \pmod{998244353}$。

该特殊条件仅适用于单场对决的疯狂度。在计算多场对决的疯狂度总和时，总和可以超过 $998244353$。

由于对决的场数尚未确定，你希望计算出对于每个从 $1$ 到 $k$ 的整数 $x$，今晚进行恰好 $x$ 场对决时，疯狂度总和的最大可能值。此外，有 $m$ 对特定的对决组合是不能组织的。请在避免这 $m$ 个限制的情况下，使疯狂度总和最大化。

输入格式

第一行包含三个整数 $n, m, k$ ($1 \le n \le 10^5, 0 \le m \le 3 \times 10^5, 1 \le k \le \min(n, 200)$)，分别表示每组骑士的人数、不能组织的额外对决组合数量，以及你需要回答的问题数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 998244353$)，表示第一组骑士的力量值。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($0 \le b_i < 998244353$)，表示第二组骑士的力量值。

接下来的 $m$ 行，第 $i$ 行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$)，表示你不能组织第一组的第 $u_i$ 名骑士与第二组的第 $v_i$ 名骑士之间的对决。保证所有给定的对决组合均不相同。

输出格式

在一行中输出 $k$ 个数字，第 $i$ 个数字表示今晚进行恰好 $i$ 场对决时，疯狂度总和的最大可能值。对于第 $i$ 个数字，如果无法组织 $i$ 场对决，则输出 $-1$。

样例

样例输入 1

3 4 3
10 998244352 5
998244352 8 6
1 2
1 3
2 2
3 3

样例输出 1

998244351 998244364 27

样例输入 2

6 10 5
749208241 448597025 773867529 808779198 554621438 19807774
281439035 850615248 796547348 327547103 765641981 702406342
1 4
5 3
3 4
2 1
5 6
4 3
6 2
6 3
2 6
2 4

样例输出 2

882168541 1667618296 2328768389 2900938913 3354309143

样例输入 3

1 1 1
0
0
1 1

样例输出 3

-1