問題文

$N$ 頂点 $M$ 辺の連結単純無向グラフ $G$ があり，$i\ (1\leq i\leq M)$ 番目の辺は頂点 $U_i,V_i$ 間を結ぶ辺です． また各頂点には整数が書き込まれており，頂点 $i\ (1\leq i\leq N)$ に書き込まれている数字は $A_i$ です． $x=1,2,\dots,N$ それぞれに対し次の問題を解いてください．

• 問題：頂点 $1$ から頂点 $x$ への単純パス（同じ頂点を複数回通らないパス）に対し，そのスコアをその単純パスに含まれる頂点に書かれた整数すべての最小公倍数と定めます． 頂点 $1$ から頂点 $x$ への単純パスすべてに対するスコアの最大公約数を $998244353$ で割ったあまりを求めてください．

入力

$N\ M$
$A_1\ A_2\ \dots\ A_N$
$U_1\ V_1$
$U_2\ V_2$
$\vdots$
$U_M\ V_M$

• $1\leq N\leq 250$
• $N-1\leq M\leq\min\left(8000,\frac{N(N-1)}{2}\right)$
• $1\leq A_i\lt 998244353$
• $1\leq U_i\lt V_i\leq N$
• $i\neq j$ ならば $(U_i,V_i)\neq(U_j,V_j)$．
• 与えられるグラフは連結
• 入力はすべて整数

出力

$N$ 行出力してください． $i$ 行目には $x=i$ としたときの答えを出力してください． 最後に改行してください．

サンプル

4 4
3 4 6 9
1 2
1 3
2 4
3 4

3
12
6
18

5 4
164493406 49276361 366324377 764544595 615989488
1 2
2 3
3 4
4 5

164493406
120205690
108232323
103692775
101734306

8 20
785470077 742424363 266929410 601820340 936427390 852239977 812821450 40172340
5 8
5 6
2 7
2 8
1 6
4 5
3 8
1 8
1 3
3 6
2 6
1 7
4 7
1 4
5 7
1 5
4 6
1 2
3 7
2 3

785470077
453182908
816474233
856799369
288800012
205327740
241617414
468866145