考虑一个关于数组的游戏：
你扮演一个指针。初始时，你等概率地指向数组中的任意一个元素。 在游戏的每一时刻，你可以执行以下操作之一：
- 结束游戏。游戏结束，你的得分等于你当前指向的元素的值。
- 移动。你等概率地向左或向右移动一个元素。如果你移动后可能指向数组边界之外，则不允许选择此选项。（你可能会被解引用，然后变成一只山羊，或者整个游戏被优化掉等等——这是未定义的行为，谁知道呢。总之你不想遇到这些情况。）
你重复进行此选择直到游戏结束。可以证明 $\lim_{m \to \infty} f(m) = 0$，其中 $f(m)$ 是你可以选择移动 $m$ 次的概率。 数组的得分是你采取最优策略时能获得的最高期望得分。（你是一个聪明的指针。）
给定一个数组 $a$。对于它的每一个前缀，计算其得分对 $998\,244\,353$ 取模的结果。 对一个可能的非整数 $X$ 对 $M$ 取模的定义如下： 题目保证 $X$ 等于某个不可约分数 $\frac{P}{Q}$，其中 $Q$ 在模 $M$ 下存在逆元。在这种情况下，$X \pmod M = A$，其中 $A$ 是 $0$ 到 $M-1$ 之间的整数，且 $P - QA$ 能被 $M$ 整除。可以证明，$A$ 是唯一的。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$) —— 数组 $a$ 的长度。 第二行包含 $n$ 个空格分隔的整数 $a_i$ ($1 \le a_i \le 10^6$) —— 数组 $a$ 的元素。
输出格式
输出 $n$ 个整数。第 $i$ 个整数应为数组 $a$ 长度为 $i$ 的前缀的得分，对 $998\,244\,353$ 取模。
样例
输入 1
3 3 1 2
输出 1
3 2 499122179
输入 2
6 6 1 2 5 3 4
输出 2
6 499122180 4 499122182 5 582309211
说明
考虑第一个样例中长度为 3 的前缀（即整个数组），它等于 $[3, 1, 2]$。最优策略是如果你从第二个元素开始，就从第二个元素移动。之后你将无法移动，或者如果你从第二个元素以外的某个元素开始，你也无法移动。 得分是 $\frac{5}{2}$，在模 $998\,244\,353$ 下等于 $499\,122\,179$。