AT_abc393_e [ABC393E] GCD of Subset

長さ $ N $ の数列 $ A=(A_1,A_2,\dots,A_N) $ と $ N $ 以下の正整数 $ K $ が与えられます。 $ i=1,2,\dots,N $ について次の問題を解いてください。 - $ A_i $ を含むように $ K $ 個の要素を $ A $ から選ぶ時、それらの最大公約数 (GCD) としてあり得る最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

$ N $ 行出力せよ。 $ j $ 行目には $ i=j $ の時の答えを出力せよ。

### Sample Explanation 1 $ i=1 $ の時は $ A_1 $ と $ A_3 $ を選ぶと最大公約数が $ \gcd(\lbrace 3, 6 \rbrace) = 3 $ となり、これが最大です。 $ i=2 $ の時は $ A_2 $ と $ A_5 $ を選ぶと最大公約数が $ \gcd(\lbrace 4, 12 \rbrace) = 4 $ となり、これが最大です。 $ i=3 $ の時は $ A_3 $ と $ A_5 $ を選ぶと最大公約数が $ \gcd(\lbrace 6, 12 \rbrace) = 6 $ となり、これが最大です。 $ i=4 $ の時は $ A_4 $ と $ A_2 $ を選ぶと最大公約数が $ \gcd(\lbrace 7, 4 \rbrace) = 1 $ となり、これが最大です。 $ i=5 $ の時は $ A_5 $ と $ A_3 $ を選ぶと最大公約数が $ \gcd(\lbrace 12, 6 \rbrace) = 6 $ となり、これが最大です。 ### Constraints - $ 1 \leq K \leq N \leq 1.2 \times 10^6 $ - $ 1 \leq A_i \leq 10^6 $ - 入力される値は全て整数