In his garden, Mr. Malnar owns a fence made of $n$ stalks of "ivica" (a plant, not Puljak), where the height of the $i$-th stalk is equal to $A_i$, and Mr. Malnar knows that the total height of all stalks is equal to $S$.

To renovate his fence, Mr. Malnar decided to trim the plants to a certain height. The stalks are fragile, so he may cut each stalk at most once. Also, Mr. Malnar is not very skilled with scissors, and to make his job easier, if he cuts a stalk at some height $v$, then every adjacent stalk strictly taller than $v$ must also be cut at that same height. Note that Mr. Malnar does not necessarily have to cut every stalk; he might have forgotten his scissors and will not cut any.

Figure I.1: On the left is an example of a valid cut, on the right is an example of an invalid cut; cutting between the 2nd and 3rd, or 4th and 5th columns is not allowed.

Mr. Malnar is interested in how many different ways he can obtain a fence with a total height equal to $X$ for each length $X$ from $0$ to $S$. Two fences are different if there exists a plant of a different height in those fences. He is not interested in the exact number, but rather the remainder when divided by $998\,244\,353$.

Input

The first line contains the number $n$ ($1 \le n \le 2\,000$), the number of stalks in the fence.

The second line contains $n$ numbers where the $i$-th number denotes $A_i$ ($0 \le A_i \le 2\,000$), the height of the $i$-th stalk.

Additionally, the sum of all heights $A_i$ satisfies $S \le 2\,000$.

Output

You need to print $S + 1$ lines, where the $i$-th line contains the remainder when the number of possible fences with a total height of $i - 1$ is divided by $998\,244\,353$.

Examples

Input 1

4
0 0 1 6

Output 1

1
0
1
1
1
1
1
1

Input 2

3
4 6 0

Output 2

1
0
1
0
1
0
1
0
1
1
1

Input 3

5
1 1 2 1 0

Output 3

1
0
0
0
1
1

Note

Explanation of the first example: In the first example, it is impossible to achieve a fence of total length 1. If we cut the 3rd stalk at height 0, then we must also cut the 4th stalk at height 0. Analogously, if we cut the 4th stalk, we must cut the 3rd stalk. For all numbers from 2 to 7, there is exactly one way to achieve that fence; from 2 to 6 by cutting the 4th column, and 7 by doing nothing. A fence of total length 0 can be achieved by cutting everything at height 0.