Little A has $n$ coins arranged in a row, initially all facing down, numbered $1, 2, 3, \dots, n-1, n$ from left to right.

Little A decides to play a game: Little A performs $k$ operations, where each operation consists of choosing two positive integers $s$ and $t$ such that $1 \leq s < t \leq n$ and flipping the coins at positions $s$ and $t$.

After $k$ operations are completed, Little A chooses a value $p$ ($0 \leq p \leq n$). Let $a$ be the number of coins facing up among the first $p$ coins (numbered $1 \sim p$), and let $b$ be the number of coins facing up among the remaining $n-p$ coins (numbered $p+1 \sim n$).

Additionally, Little A has an aesthetic function $H$ and two constants $x$ and $y$.

The score of a game is defined as $val = x^p y^{n-p} H(a)$. Little A wants to find the sum of scores of all possible games.

To make the problem more interesting, Little A specifies the values of $a$ and $b$. We define $F(x, y)$ as the sum of scores of all distinct games that satisfy $a=x$ and $b=y$. Two games are considered distinct if and only if the sequence of $(s, t)$ pairs chosen in the operations is different, or if the final choice of $p$ is different.

Little A is not satisfied with just calculating $F(x, y)$. He further introduces two numbers $r_a$ and $r_b$, and asks you to calculate $ans_k = \sum_{i=0}^{r_a} F(i, r_b)$, where $k$ is the number of operations performed.

Beyond being a game enthusiast, Little A is a perfectionist who strives for excellence. Therefore, he asks you to calculate $ans_0, ans_1, ans_2, \dots, ans_{m-1}, ans_m$. The answers should be taken modulo $998\,244\,353$.

Input

The first line contains six natural numbers $n, x, y, r_a, r_b, m$. The second line contains $r_a+1$ numbers, representing $H(0), H(1), H(2), \ldots, H(r_a-1), H(r_a)$.

Output

A single line containing $m+1$ numbers, representing the answers.

Examples

Input 1

5 1 4 1 1 4
1919 810

Output 1

0 1231200 7387200 78796800 768268800

Input 2

100 2 3 10 20 20
1 2 3 4 5 6 7 8 9 10 11

Output 2

0 0 0 0 0 0 0 0 0 0 809274050 933560834 648523677 685804365 288106207 428246395 643105965 610311779 424132536 354030387 477940535

Subtasks

For all data, it is guaranteed that $0 \leq n, x, y, H(i) < 998244353$, $0 \leq r_a, r_b, m \leq 10^5$, $r_a + r_b \leq n$, and $x, y > 0$.

Property A: $H(x)$ is non-zero at only one position.

Each subtask may depend on subtasks with smaller data ranges.