黒板に $N$ 個の正整数 $A_1, A_2, \ldots, A_N$ が書かれています。

あなたは以下の操作を行えなくなるまで繰り返します。

• 黒板に書かれている数を $2$ つ選んで消す。消した数を $x, y$ として、
  「$x$と$y$の最大公約数」 と 「$x$と$y$の最小公倍数」を黒板に書き加える。
  • ただし、黒板に書かれている数の組み合わせが操作の前後で変化しないような操作は行うことができない。

操作を行えなくなるまで繰り返したのち、
黒板に書かれているすべての数字を昇順に並び替え、この数列を $B$ とします。(操作が有限回で終了することは証明できる。)

数列 $B$ の各要素の値は非常に大きくなることがあるので、各要素を $998244353$ で割ったあまりを求めてください。

• $2 \leq N \leq 10^5$
• $1 \leq A_i \leq 2 \times 10^5~~(1 \leq i \leq N)$
• 入力はすべて整数

部分点

以下の条件を満たすテストケースにすべて正解したとき、記載された点数が与えられる。

1. (10点) $N = 2$
2. (40点) $N \leq 1000,~ (A_1, A_2, \ldots, A_N)$ の最小公倍数 $\leq 10^{18}$
3. (50点) 追加の制約なし

入力は、以下の形式で標準入力から与えられる。

数列 $B$ の各要素を $998244353$ で割ったあまりを空白区切りで出力せよ。