問題文

$N$頂点$M$辺の単純有向グラフが与えられます．（グラフは連結ではないこともあります．）$i$（$1 \leq i \leq M$）本目の辺は頂点$u_i$から頂点$v_i$へ張られています．
また，各頂点には，値$A_i$（$1 \leq i \leq N$）が書かれています．
全頂点について以下を求めてください．

その頂点から到達可能な頂点の集合$S$について，$S$に含まれる頂点に書いてある数の最大公約数

ただし，頂点$u$から頂点$v$に"到達可能"とは，頂点$u$から，有向辺に沿って頂点を $0$回以上 移動することで頂点$v$に到達可能であるということをいいます．

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq \min(N (N-1), 2 \times 10^5)$
• $1 \leq u_i, v_i \leq N \quad (1 \leq i \leq M)$
• $u_i \neq v_i \quad (1 \leq i \leq M)$
• $i \neq j \ ならば\ (u_i, v_i) \neq (u_j, v_j) \quad (1 \leq i, j \leq M)$
• $1 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)$
• 入力はすべて整数

入力

出力

$i$行目（$1 \leq i \leq N$）に以下を出力．

頂点$i$から到達可能な頂点の集合$S_i$について，$S_i$に含まれる頂点に書いてある数の最大公約数

サンプル

10 11
20 66 390 28 15 140 84 36 210 252
1 2
1 3
1 4
2 3
3 9
4 6
5 1
6 8
7 10
8 4
8 7

2
6
30
4
1
4
84
4
210
252