AT_agc076_d [AGC076D] Stochastic Dominance

Let $ L=10^8 $ . You are given an integer $ N $ and a non-negative integer sequence $ A=(A_1,A_2,\cdots,A_M) $ of length $ M $ ( $ 0 \leq A_i < L $ ). For each $ k=1,2,\cdots,N $ , solve the following problem: There are $ k $ red balls numbered from $ 1 $ to $ k $ and $ k $ blue balls numbered from $ 1 $ to $ k $ . Now, you will write a real number on each ball in the following way. Here, all random choices are independent. - For each $ 1 \leq i \leq k $ , the number written on red ball $ i $ is $ L \times (i-1)+A_{j_i} $ . Here, $ j_i $ is an integer chosen uniformly at random from the range between $ 1 $ and $ M $ (inclusive). - For each $ 1 \leq i \leq k $ , the number written on blue ball $ i $ is a **real number** chosen uniformly at random from the range $ [0,k \times L) $ . Find the probability, modulo $ 998244353 $ , that the following condition is satisfied after writing numbers on all balls. - For any real number $ x $ ( $ 0 \leq x \leq k \times L $ ), "the number of red balls with a number written that is at most $ x $ " $ \geq $ "the number of blue balls with a number written that is at most $ x $ ". Definition of probability modulo $ 998244353 $ It can be proved that the desired probability is always a rational number. Also, under the constraints of this problem, it can be proved that if the desired rational number is represented as an irreducible fraction $ \frac{P}{Q} $ , then $ Q \neq 0 \pmod{998244353} $ . Therefore, there uniquely exists an integer $ R $ satisfying $ R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 $ . Output this $ R $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_M $

Output $ N $ lines. The $ i $ -th line should contain the answer for $ k=i $ .

### Sample Explanation 1 - $ k=1 $ : The probability of satisfying the condition is $ 1/2 $ . - $ k=2 $ : The probability of satisfying the condition is $ 5/16 $ . ### Constraints - $ 1 \leq N \leq 250000 $ - $ 1 \leq M \leq 250000 $ - $ 0 \leq A_i < L=10^8 $ - All input values are integers.