Alice and Bob have a deck of cards, which is initially empty. They play a game that lasts for $$$m$$$ rounds. In the $$$i$$$-th round, the following events occur:

a card with the value $$$a_i$$$ is added to the deck (it is guaranteed that no card with this value was previously in the deck);
if there are fewer than $$$3$$$ cards in the deck, the round ends;
otherwise, Alice chooses a card from the deck;
then Bob chooses a card (knowing which card Alice chose; he cannot choose the same one);
one more card is chosen from the remaining $$$i-2$$$ cards uniformly at random;
at the end, all three chosen cards are returned to the deck.

Let $$$a$$$ be the value on Alice's card, $$$b$$$ be the value on Bob's card, and $$$c$$$ be the value on the randomly chosen card. Then Bob receives:

$$$0$$$ points if $$$|a - c| \le |b - c|$$$ (where $$$|x|$$$ denotes the absolute value of $$$x$$$);
$$$0$$$ points if card $$$c$$$ is between cards $$$a$$$ and $$$b$$$ (i. e., $$$a \lt c \lt b$$$ or $$$b \lt c \lt a$$$);
$$$|b-c|$$$ points otherwise.

Alice's goal in each round is to minimize Bob's expected score, while Bob's goal is to maximize it. What will be the expected score for Bob in each round if both Alice and Bob play optimally? Print the expected score modulo $$$998\,244\,353$$$.

Note that the players minimize or maximize the real value of the expected score, not the result taken modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer ($$$3 \le m \le 2 \cdot 10^5$$$) — the number of rounds.

The second line contains $$$m$$$ integers $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le 10^{12}$$$; all $$$a_i$$$ are distinct).

Output

Print $$$m-2$$$ integers: the $$$i$$$-th number should be equal to the expected score for Bob in the round $$$i+2$$$ with optimal play from both players modulo $$$998\,244\,353$$$ (i. e., let the expected score be an irreducible fraction $$$\frac{x}{y}$$$; you need to output $$$x \cdot y^{-1} \bmod 998\,244\,353$$$, where $$$y^{-1}$$$ is such a number that $$$y \cdot y^{-1} \bmod 998\,244\,353 = 1$$$).

Note that the players minimize or maximize the real value of the expected score, not the result taken modulo $$$998\,244\,353$$$.

Note

In the first example, the answers are: $$$0, \frac{1}{2}, \frac{2}{3}$$$.

In the second example, the answers are: $$$0, \frac{1}{2}, 1, \frac{5}{4}$$$.

In the third example, the answers are: $$$0, \frac{3}{2}, 2, \frac{3}{2}, \frac{8}{5}, \frac{11}{6}, \frac{11}{7}$$$.

Probabilistic Card Game

Examples