猫猫与宝石
题号：NC249993
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一天，猫猫路过了宝石店。
店中有 n 块宝石，美丽度为整数 a_1,...,a_n。
神奇的是，如果把 c 个美丽度之和为 w 的宝石合并，可以合成一个美丽度为 c\cdot w 的新宝石。
猫猫想知道，如果她随机选一些宝石 (共 2^n 种选法)，每个宝石以 0.5 的概率被选中，然后把所有选中的宝石合并，获得的新宝石美丽度的期望值是多少。如果没有任何宝石被选中，我们认为新宝石的美丽度为 0。
猫猫非常贪心，她想对于每个 i=1,2,...,n，都询问一下假设只有前 i 块宝石，随机选一些宝石合并，新宝石美丽度的期望是多少。
离散型随机变量 X 的期望定义如下：设 X 所有可能的取值是 v_1,v_2,...,v_m，概率对应为 p_1,p_2,...,p_m (满足 \sum p_i = 1)，则期望 E(X) = \sum_{i = 1}^m p_i v_i。
记 M = 998244353。可以证明答案可以表示成 \frac pq 其中 p \geq 0,q\geq 1,\gcd(p,q) = 1,q\bmod M\not=0，故你只要输出 p\cdot q^{-1}\bmod M 即可。此处 q^{-1} 表示 q 在模 M 意义下的逆元，即 q q^{-1}\equiv 1\pmod {M}，例如本题数字 2 在模 M 意义下的逆元是 \frac{M+1}2。

输入描述:

输入共两行。
第一行一个正整数 n，表示宝石的个数。
第二行 n 个正整数 a_1,a_2,...,a_n，表示每个宝石的美丽度。

1\leq n\leq 2\cdot 10^5,0\le a_i < M。

输出描述:

一行 n 个数，第 i 个数表示 a_1,...,a_i 的答案。
示例1

输入

复制 
2
1 2

输出

复制 
499122177 748683267

说明

对于 i=1，第一个宝石有 0.5 的概率被选中，期望是 0.5 \times 0\times 0 + 0.5\times 1 \times 1 = 0.5。0.5 \bmod M= \dfrac{1}{2} \bmod M = 1\cdot 2^{-1}\bmod M = 499122177。

对于 i=2，有四个局面，分别是：1,2 均没被选中；1,2 均选中；1 选中 2 未选中；1 未选中 2 选中。四个局面的概率都是 0.25，故期望是 0.25 \times (0+2\times(1+2)+1\times1+1\times 2) = 2.25。2.25 \bmod M= \dfrac{9}{4} \bmod M = 9\cdot 4^{-1}\bmod M = 748683267。
示例2

输入

复制 
5
2023 3 15 1678 8725

输出

复制 
499123188 499123696 2041 249565737 18666