You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

碳钾钨最近学习了变成食物的魔法，他想捉弄一下他的好朋友kuro。

kuro发现自己的家里突然出现了$n$块巧克力，每一块的美味值为$a_i$,她的巧克力太多了，所以kuro决定玩一些神秘的游戏。

她先从巧克力堆里随机抽取一块巧克力，记下美味值为$x$，放回后再抽取一块，记下美味值为$y$，随后，她吃下美味值更大的那一块。

kuro想知道自己这么做所吃下的巧克力的期望值是多少，但她嫌弃这个问题太过简单，所以她想问你，对于所有的$i(1 \leq i \leq n)$,对前$i$块巧克力这么做的期望值为多少？

期望可以表示为一个分数$\frac{p}{q}$(pq是互质的)，你需要先找到一个整数$y$,使得$q*y \equiv 1(mod \space998 \space244\space353)$然后输出整数$x(0 \leq x<998 \space244\space353)$,使得$p*y \equiv x(mod \space998 \space244\space353)$,容易证明这样的整数$x$是唯一的.

Input Format

第一行为一个整数$n(1 \leq n \leq 2*10^5)$,代表kuro的巧克力块数

第二行为$n$个整数$a_i(1 \leq a_i \leq 2*10^5)$,代表每块巧克力的美味度

Output Format

输出$n$行,每行是一个整数$x(0 \leq x<998 \space244\space353)$,代表期望。

Sample

输入 #1

3
1 2 3

输出 #1

1
249561090
776412277

当$i=1$时，答案显然是1

当$i=2$时，答案为7/4

当$i=3$时，答案为22/9

Hint

在kuro即将吃下碳钾钨身体的一部分前，碳钾钨变了回来，阻止了这场惨剧。