AT_fps_24_x 関数的平方根

You are given a formal power series $ F(x) = \sum_{i=0}^{N-1} f_i x^i $ over $ \mathbb{F} _ {998244353} $ , where $ N \geq 2 $ and $ F(x) \bmod{x^2} = x $ . It can be proven that there exists a unique formal power series $ G(x) = \sum_{i=0}^{N-1} g_i x^i $ over $ \mathbb{F} _ {998244353} $ such that: - $ G(G(x)) \equiv F(x) \pmod{x^N} $ , and - $ G(x) \bmod{x^2} = x $ . Your task is to find this $ G(x) $ .

The input is given from standard input in the following format: > $ N $ $ f_0 $ $ f_1 $ $ \dots $ $ f_{N-1} $

Print the answer in the following format: > $ g_0 $ $ g_1 $ $ \dots $ $ g_{N-1} $

### Note This problem is a **hard challenge intended for those who have finished all other problems and still have time left**. The score is set relatively low compared to its difficulty. If you have not solved the other problems yet, it is recommended to do those first. ### Sample Explanation 1 $ G(x) = x + 2x^2 $ satisfies the conditions. ### Constraints - $ 2 \leq N \leq 8000 $ - $ f_0 = 0 $ - $ f_1 = 1 $ - $ 0 \leq f_i < 998244353 $ for $ 2 \leq i \leq N-1 $ - All input values are integers