有 $n$ 个瓶子排成一排，编号为 $1, 2, \dots, n$，第 $i$ 个瓶子的容量为 $a_i$。初始时，第一个瓶子装满了水，其余瓶子均为空。

Haitang 按从左到右的顺序对每个瓶子执行以下操作：

• 从剩余的 $n-1$ 个瓶子中等概率随机选择一个瓶子。
• 将当前瓶子中的水倒入所选瓶子，直到当前瓶子变空或所选瓶子装满。

给定序列 $a$，dXqwq 想知道所有操作完成后每个瓶子中水的期望体积。

由于 dXqwq 不喜欢浮点数，你只需要输出结果对 $998244353$ 取模后的值。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示瓶子的数量。 第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le n$)，表示每个瓶子的容量。

输出格式

输出 $n$ 行，其中第 $i$ 行包含所有操作完成后第 $i$ 个瓶子中水的期望体积，对 $998244353$ 取模。

样例

样例输入 1

2
1 1

样例输出 1

1
0

样例输入 2

3
3 1 2

样例输出 2

623902723
623902721
748683265

样例输入 3

9
9 9 8 2 4 4 3 5 3

样例输出 3

304464287
164086171
361005467
588475930
898938779
983453531
155241138
69810681
467501437