A - Weak Beats

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100

問題文

01 からなる長さ 16 の文字列 S が与えられます。

2 以上 16 以下のすべての偶数 i について Si 文字目が 0 ならば Yes を、 そうでないならば No を出力してください。

制約

  • S01 からなる長さ 16 の文字列

入力

入力は以下の形式で標準入力から与えられる。

S

出力

2 以上 16 以下のすべての偶数 i について Si 文字目が 0 ならば Yes を、 そうでないならば No を出力せよ。


入力例 1

1001000000001010

出力例 1

No

S= 10010000000010104 文字目が 1 であるため、No を出力します。


入力例 2

1010100000101000

出力例 2

Yes

S= 1010100000101000 の偶数番目の文字はすべて 0 であるため、Yes を出力します。


入力例 3

1111111111111111

出力例 3

No

S の偶数文字目はすべて 1 となっています。 特に「すべて 0 」ではないため、No を出力します。

Score : 100 points

Problem Statement

You are given a string S of length 16 consisting of 0 and 1.

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.

Constraints

  • S is a string of length 16 consisting of 0 and 1.

Input

The input is given from Standard Input in the following format:

S

Output

If the i-th character of S is 0 for every even number i from 2 through 16, print Yes; otherwise, print No.


Sample Input 1

1001000000001010

Sample Output 1

No

The 4-th character of S= 1001000000001010 is 1, so you should print No.


Sample Input 2

1010100000101000

Sample Output 2

Yes

Every even-positioned character in S= 1010100000101000 is 0, so you should print Yes.


Sample Input 3

1111111111111111

Sample Output 3

No

Every even-positioned character in S is 1. Particularly, they are not all 0, so you should print No.

B - Round-Robin Tournament

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

1 から N までの番号が付いた N 人のプレイヤーが総当たり戦をしました。この総当たり戦で行われた試合全てについて、二人の一方が勝ち、もう一方が負けました。

総当たり戦の結果は N 個の長さ N の文字列 S_1,S_2,\ldots,S_N によって以下の形式で与えられます。

  • i\neq j のとき、S_ij 文字目は o, x のいずれかであり、o のときプレイヤー i がプレイヤー j に勝ったことを、x のときプレイヤー i がプレイヤー j に負けたことを意味する。

  • i=j のとき、S_ij 文字目は - である。

総当たり戦で勝った試合数が多いほうが順位が上であり、勝った試合数が同じ場合は、プレイヤーの番号が小さいほうが順位が上となります。 N 人のプレイヤーの番号を順位が高い順に答えてください。

制約

  • 2\leq N\leq 100
  • N は整数
  • S_io, x, - からなる長さ N の文字列
  • S_1,\ldots,S_N は問題文中の形式を満たす

入力

入力は以下の形式で標準入力から与えられる。

N 
S_1
S_2
\vdots
S_N

出力

N 人のプレイヤーの番号を、順位が高い順に空白区切りで出力せよ。


入力例 1

3
-xx
o-x
oo-

出力例 1

3 2 1

プレイヤー 10 勝、プレイヤー 21 勝、プレイヤー 32 勝なので、プレイヤーの番号は順位が高い順に 3,2,1 です。


入力例 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

出力例 2

4 7 3 1 5 2 6

プレイヤー 4 とプレイヤー 7 はどちらも 5 勝ですが、プレイヤー番号が小さいプレイヤー 4 のほうが順位が上になります。

Score : 200 points

Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

  • If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.

  • If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

  • 2\leq N\leq 100
  • N is an integer.
  • S_i is a string of length N consisting of o, x, and -.
  • S_1,\ldots,S_N conform to the format described in the problem statement.

Input

The input is given from Standard Input in the following format:

N 
S_1
S_2
\vdots
S_N

Output

Print the player numbers of the N players in descending order of rank.


Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.


Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

C - World Tour Finals

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250

問題文

N 人のプレイヤーが参加するプログラミングコンテスト World Tour Finals が行われており、競技時間の半分が過ぎました。 このコンテストでは M 問の問題が出題されており、問題 i の点数 A_i500 以上 2500 以下の 100 の倍数です。

i = 1, \ldots, N について、プレイヤー i がどの問題を既に解いたかを表す文字列 S_i が与えられます。 S_io, x からなる長さ M の文字列で、S_ij 文字目が o のときプレイヤー i は問題 j を既に解いており、x のときまだ解いていません。 ただし、どのプレイヤーもまだ全ての問題を解いてはいません。

プレイヤー i の総合得点は、解いた問題の点数の合計に、ボーナス点 i 点を加えた点数として計算されます。
さて、各 i = 1, \ldots, N について以下の質問に答えてください。

  • プレイヤー i がまだ解いていない問題を少なくとも何問解くことで、プレイヤー i の総合得点が他のプレイヤー全員の現在の総合得点を上回ることができますか?

なお、問題文中の条件と制約から、プレイヤー i が全ての問題を解くことで、他のプレイヤー全員の現在の総合得点を上回ることができることが証明できます。 このことから、答えは常に定義されることに注意してください。

制約

  • 2\leq N\leq 100
  • 1\leq M\leq 100
  • 500\leq A_i\leq 2500
  • A_i100 の倍数
  • S_io, x からなる長さ M の文字列
  • S_i には x が一個以上含まれる
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \ldots A_M
S_1
S_2
\vdots
S_N

出力

N 行出力せよ。 i 行目にはプレイヤー i に関する質問の答えを出力せよ。


入力例 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

出力例 1

0
1
1

競技時間の半分の経過時の各プレイヤーの総合得点は、プレイヤー 12001 点、プレイヤー 21502 点、プレイヤー 31703 点です。

プレイヤー 11 問も解かずとも、他のプレイヤー全員の総合得点を上回っています。

プレイヤー 2 は、例えば問題 4 を解けば総合得点が 3502 点となり、他のプレイヤー全員の総合得点を上回ります。

プレイヤー 3 も、例えば問題 4 を解けば総合得点が 3703 点となり、他のプレイヤー全員の総合得点を上回ります。


入力例 2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

出力例 2

1
1
1
1
0

入力例 3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

出力例 3

7
6
5
4
3
2
0

Score : 250 points

Problem Statement

The programming contest World Tour Finals is underway, where N players are participating, and half of the competition time has passed. There are M problems in this contest, and the score A_i of problem i is a multiple of 100 between 500 and 2500, inclusive.

For each i = 1, \ldots, N, you are given a string S_i that indicates which problems player i has already solved. S_i is a string of length M consisting of o and x, where the j-th character of S_i is o if player i has already solved problem j, and x if they have not yet solved it. Here, none of the players have solved all the problems yet.

The total score of player i is calculated as the sum of the scores of the problems they have solved, plus a bonus score of i points.
For each i = 1, \ldots, N, answer the following question.

  • At least how many of the problems that player i has not yet solved must player i solve to exceed all other players' current total scores?

Note that under the conditions in this statement and the constraints, it can be proved that player i can exceed all other players' current total scores by solving all the problems, so the answer is always defined.

Constraints

  • 2\leq N\leq 100
  • 1\leq M\leq 100
  • 500\leq A_i\leq 2500
  • A_i is a multiple of 100.
  • S_i is a string of length M consisting of o and x.
  • S_i contains at least one x.
  • All numeric values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_M
S_1
S_2
\vdots
S_N

Output

Print N lines. The i-th line should contain the answer to the question for player i.


Sample Input 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

Sample Output 1

0
1
1

The players' total scores at the halfway point of the competition time are 2001 points for player 1, 1502 points for player 2, and 1703 points for player 3.

Player 1 is already ahead of all other players' total scores without solving any more problems.

Player 2 can, for example, solve problem 4 to have a total score of 3502 points, which would exceed all other players' total scores.

Player 3 can also, for example, solve problem 4 to have a total score of 3703 points, which would exceed all other players' total scores.


Sample Input 2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

Sample Output 2

1
1
1
1
0

Sample Input 3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

Sample Output 3

7
6
5
4
3
2
0
D - Merge Slimes

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 425

問題文

最初、N 種類のサイズのスライムがいます。
具体的には、1\leq i\leq N について、サイズ S_i のスライムが C_i 匹います。

高橋君はスライムの合成を好きな順番で好きなだけ(0 回でも良い)繰り返すことができます。
スライムの合成では、次のことを行います。

  • 同じ サイズの 2 匹のスライムを選ぶ。選ばれたスライムのサイズが X であったとき、新しくサイズ 2X のスライムが出現する。合成後、選ばれた元のスライムは 2 匹とも消滅する。

高橋君はスライムの匹数を最小にしたいと考えています。 高橋君がうまく合成を繰り返した時、最小で何匹にすることができるでしょうか?

制約

  • 1\leq N\leq 10^5
  • 1\leq S_i\leq 10^9
  • 1\leq C_i\leq 10^9
  • S_1,S_2,\ldots,S_N はすべて異なる。
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
S_1 C_1
S_2 C_2
\vdots
S_N C_N

出力

高橋君が合成を繰り返した後のスライムの匹数としてあり得る最小の数を出力せよ。


入力例 1

3
3 3
5 1
6 1

出力例 1

3

最初、サイズ 3 のスライムが 3 匹、サイズ 5 のスライムが 1 匹、サイズ 6 のスライムが 1 匹います。
高橋君は次のように合成を 2 回行うことができます。

  • まず、サイズ 3 のスライム 2 匹を選んで合成を行います。サイズ 3 のスライムが 1 匹、サイズ 5 のスライムが 1 匹、サイズ 6 のスライムが 2 匹となります。
  • 次に、サイズ 6 のスライム 2 匹を選んで合成を行います。サイズ 3 のスライムが 1 匹、サイズ 5 のスライムが 1 匹、サイズ 12 のスライムが 1 匹となります。

高橋君は最初の状態からどのように合成を繰り返してもスライムを 2 匹以下にすることはできないため、3 を出力します。


入力例 2

3
1 1
2 1
3 1

出力例 2

3

高橋君は合成を行うことができません。


入力例 3

1
1000000000 1000000000

出力例 3

13

Score : 425 points

Problem Statement

Initially, there are N sizes of slimes.
Specifically, for each 1\leq i\leq N, there are C_i slimes of size S_i.

Takahashi can repeat slime synthesis any number of times (possibly zero) in any order.
Slime synthesis is performed as follows.

  • Choose two slimes of the same size. Let this size be X, and a new slime of size 2X appears. Then, the two original slimes disappear.

Takahashi wants to minimize the number of slimes. What is the minimum number of slimes he can end up with by an optimal sequence of syntheses?

Constraints

  • 1\leq N\leq 10^5
  • 1\leq S_i\leq 10^9
  • 1\leq C_i\leq 10^9
  • S_1,S_2,\ldots,S_N are all different.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
S_1 C_1
S_2 C_2
\vdots
S_N C_N

Output

Print the minimum possible number of slimes after Takahashi has repeated the synthesis.


Sample Input 1

3
3 3
5 1
6 1

Sample Output 1

3

Initially, there are three slimes of size 3, one of size 5, and one of size 6.
Takahashi can perform the synthesis twice as follows:

  • First, perform the synthesis by choosing two slimes of size 3. There will be one slime of size 3, one of size 5, and two of size 6.
  • Next, perform the synthesis by choosing two slimes of size 6. There will be one slime of size 3, one of size 5, and one of size 12.

No matter how he repeats the synthesis from the initial state, he cannot reduce the number of slimes to 2 or less, so you should print 3.


Sample Input 2

3
1 1
2 1
3 1

Sample Output 2

3

He cannot perform the synthesis.


Sample Input 3

1
1000000000 1000000000

Sample Output 3

13
E - Playlist

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450

問題文

高橋君は N 曲からなるプレイリストを持っています。 曲 i (1 \leq i \leq N) の長さは T_i 秒です。
高橋君は時刻 0 にプレイリストのランダム再生を開始しました。

ランダム再生では、N 曲の中から等確率で 1 つを選びその曲を最後まで再生することが繰り返されます。 ここで、曲の再生は休みなく行われ、1 つの曲が終わったらすぐに次に選ばれた曲が始まります。 また、同じ曲が連続して選ばれる事もあります。

時刻 0 から (X+0.5) 秒後に曲 1 が再生されている確率を \text{mod}998244353 で求めてください。

確率 \text{mod } 998244353 の定義

この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x998244353 で割り切れないことが保証されます。

このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。

制約

  • 2 \leq N\leq 10^3
  • 0 \leq X\leq 10^4
  • 1 \leq T_i\leq 10^4
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N X
T_1 T_2 \ldots T_N

出力

時刻 0 から (X+0.5) 秒後にプレイリストの 1 番目の曲が再生されている確率を \text{mod}998244353 で出力せよ。


入力例 1

3 6
3 5 6

出力例 1

369720131

時刻 0 から 6.5 秒後に曲 1 が流れているパターンとしてあり得るのは、

  • 1 \to1 \to1
  • 2 \to1
  • 3 \to1

の順で音楽が再生された場合であり、これらのいずれかが起こる確率は \frac{7}{27} となります。
369720131\times 27\equiv 7 \pmod{998244353} であるため、369720131 を出力します。


入力例 2

5 0
1 2 1 2 1

出力例 2

598946612

時刻 0 から 0.5 秒後には最初に再生された曲が再生されているため、求める確率は \frac{1}{5} となります。
同じ長さの異なる曲が存在することがあることに注意してください。


入力例 3

5 10000
1 2 3 4 5

出力例 3

586965467

Score : 450 points

Problem Statement

Takahashi has a playlist with N songs. Song i (1 \leq i \leq N) lasts T_i seconds.
Takahashi has started random play of the playlist at time 0.

Random play repeats the following: choose one song from the N songs with equal probability and play that song to the end. Here, songs are played continuously: once a song ends, the next chosen song starts immediately. The same song can be chosen consecutively.

Find the probability that song 1 is being played (X + 0.5) seconds after time 0, modulo 998244353.

How to print a probability modulo 998244353

It can be proved that the probability to be found in this problem is always a rational number. Also, the constraints of this problem guarantee that when the probability to be found is expressed as an irreducible fraction \frac{y}{x}, x is not divisible by 998244353.

Then, there is a unique integer z between 0 and 998244352, inclusive, such that xz \equiv y \pmod{998244353}. Report this z.

Constraints

  • 2 \leq N\leq 10^3
  • 0 \leq X\leq 10^4
  • 1 \leq T_i\leq 10^4
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N X
T_1 T_2 \ldots T_N

Output

Print the probability, modulo 998244353, that the first song in the playlist is being played (X+0.5) seconds after time 0.


Sample Input 1

3 6
3 5 6

Sample Output 1

369720131

Song 1 will be playing 6.5 seconds after time 0 if songs are played in one of the following orders.

  • Song 1 \to Song 1 \to Song 1
  • Song 2 \to Song 1
  • Song 3 \to Song 1

The probability that one of these occurs is \frac{7}{27}.
We have 369720131\times 27\equiv 7 \pmod{998244353}, so you should print 369720131.


Sample Input 2

5 0
1 2 1 2 1

Sample Output 2

598946612

0.5 seconds after time 0, the first song to be played is still playing, so the sought probability is \frac{1}{5}.
Note that different songs may have the same length.


Sample Input 3

5 10000
1 2 3 4 5

Sample Output 3

586965467
F - Push and Carry

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 525

問題文

座標平面上に高橋君と荷物があります。

高橋君は現在 (X_A,Y_A) におり、荷物は (X_B,Y_B) にあります。 高橋君は荷物を (X_C,Y_C) まで運びたいです。

高橋君は (x,y) にいるとき、1 回の行動で次のいずれかの動きをすることができます。

  • (x+1,y) に移動する。移動前の時点で荷物が (x+1,y) にあった時、荷物を (x+2,y) に移動させる。
  • (x-1,y) に移動する。移動前の時点で荷物が (x-1,y) にあった時、荷物を (x-2,y) に移動させる。
  • (x,y+1) に移動する。移動前の時点で荷物が (x,y+1) にあった時、荷物を (x,y+2) に移動させる。
  • (x,y-1) に移動する。移動前の時点で荷物が (x,y-1) にあった時、荷物を (x,y-2) に移動させる。

荷物を (X_C,Y_C) に移動させるまでに必要な最小の行動回数を求めてください。

制約

  • -10^{17}\leq X_A,Y_A,X_B,Y_B,X_C,Y_C\leq 10^{17}
  • (X_A,Y_A)\neq (X_B,Y_B)
  • (X_B,Y_B)\neq (X_C,Y_C)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

X_A Y_A X_B Y_B X_C Y_C

出力

荷物を (X_C,Y_C) に移動させるまでに必要な最小の行動回数を出力せよ。


入力例 1

1 2 3 3 0 5

出力例 1

9

高橋君は次のように行動することで 9 回で荷物を (0,5) に運ぶことができます。

  • (2,2) へ移動する。
  • (3,2) へ移動する。
  • (3,3) へ移動する。荷物は (3,4) に移動する。
  • (3,4) へ移動する。荷物は (3,5) に移動する。
  • (4,4) へ移動する。
  • (4,5) へ移動する。
  • (3,5) へ移動する。荷物は (2,5) に移動する。
  • (2,5) へ移動する。荷物は (1,5) に移動する。
  • (1,5) へ移動する。荷物は (0,5) に移動する。

8 回以下で荷物を (0,5) に運ぶことができないので、9 を出力します。


入力例 2

0 0 1 0 -1 0

出力例 2

6

入力例 3

-100000000000000000 -100000000000000000 100000000000000000 100000000000000000 -100000000000000000 -100000000000000000

出力例 3

800000000000000003

Score : 525 points

Problem Statement

Takahashi and a cargo are on a coordinate plane.

Takahashi is currently at (X_A,Y_A), and the cargo is at (X_B,Y_B). He wants to move the cargo to (X_C,Y_C).

When he is at (x,y), he can make one of the following moves in a single action.

  • Move to (x+1,y). If the cargo is at (x+1,y) before the move, move it to (x+2,y).
  • Move to (x-1,y). If the cargo is at (x-1,y) before the move, move it to (x-2,y).
  • Move to (x,y+1). If the cargo is at (x,y+1) before the move, move it to (x,y+2).
  • Move to (x,y-1). If the cargo is at (x,y-1) before the move, move it to (x,y-2).

Find the minimum number of actions required to move the cargo to (X_C,Y_C).

Constraints

  • -10^{17}\leq X_A,Y_A,X_B,Y_B,X_C,Y_C\leq 10^{17}
  • (X_A,Y_A)\neq (X_B,Y_B)
  • (X_B,Y_B)\neq (X_C,Y_C)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

X_A Y_A X_B Y_B X_C Y_C

Output

Print the minimum number of actions required to move the cargo to (X_C,Y_C).


Sample Input 1

1 2 3 3 0 5

Sample Output 1

9

Takahashi can move the cargo to (0,5) in nine actions as follows.

  • Move to (2,2).
  • Move to (3,2).
  • Move to (3,3). The cargo moves to (3,4).
  • Move to (3,4). The cargo moves to (3,5).
  • Move to (4,4).
  • Move to (4,5).
  • Move to (3,5). The cargo moves to (2,5).
  • Move to (2,5). The cargo moves to (1,5).
  • Move to (1,5). The cargo moves to (0,5).

It is impossible to move the cargo to (0,5) in eight or fewer actions, so you should print 9.


Sample Input 2

0 0 1 0 -1 0

Sample Output 2

6

Sample Input 3

-100000000000000000 -100000000000000000 100000000000000000 100000000000000000 -100000000000000000 -100000000000000000

Sample Output 3

800000000000000003
G - Inversion of Tree

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 650

問題文

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が与えられます。

頂点に 1 から N の番号が付いた N 頂点の木のうち、以下の条件を満たすものの個数を 998244353 で割ったあまりを K=0,1,\ldots,N-1 に対して求めてください。

  • 木で直接辺で結ばれた頂点の組 (u_i,v_i)\ (u_i < v_i) のうち、 P_{u_i}>P_{v_i} を満たすものがちょうど K 個ある。

制約

  • 2\leq N\leq 500
  • P(1,2,\ldots,N) の順列

入力

入力は以下の形式で標準入力から与えられる。

N 
P_1 P_2 \ldots P_N

出力

K=0,1,\ldots,N-1 に対して、条件を満たす木の個数を 998244353 で割ったあまりを空白区切りで出力せよ。


入力例 1

3
1 3 2

出力例 1

1 2 0

K=0 のときの答えは、頂点 1,2 と頂点 1,3 を結ぶ木の一つです。実際、P_1 < P_2, P_1<P_3 です。

K=1 のときの答えは、頂点 1,2 と頂点 2,3 を結ぶ木と頂点 1,3 と頂点 2,3 を結ぶ木の二つです。実際、頂点 1,2 と頂点 2,3 を結ぶ木では、P_1 < P_2, P_2>P_3 です。


入力例 2

10
3 1 4 10 8 6 9 2 7 5

出力例 2

294448 2989776 12112684 25422152 30002820 20184912 7484084 1397576 108908 2640

Score : 650 points

Problem Statement

You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

For each K=0,1,\ldots,N-1, find the number, modulo 998244353, of trees with N vertices numbered 1 to N that satisfy the following condition.

  • Among the pairs of vertices (u_i,v_i)\ (u_i < v_i) that are directly connected by an edge in the tree, exactly K pairs satisfy P_{u_i}>P_{v_i}.

Constraints

  • 2\leq N\leq 500
  • P is a permutation of (1,2,\ldots,N).

Input

The input is given from Standard Input in the following format:

N 
P_1 P_2 \ldots P_N

Output

For each K=0,1,\ldots,N-1, print the number, modulo 998244353, of trees that satisfy the condition, with spaces in between.


Sample Input 1

3
1 3 2

Sample Output 1

1 2 0

The answer for K=0 is 1: the tree with edges connecting vertices 1,2 and 1,3. Indeed, P_1 < P_2 and P_1<P_3.

The answer for K=1 is 2: the tree with edges connecting vertices 1,2 and 2,3, and another with edges connecting vertices 1,3 and 2,3. Indeed, in the tree with edges connecting vertices 1,2 and 2,3, we have P_1 < P_2, P_2>P_3.


Sample Input 2

10
3 1 4 10 8 6 9 2 7 5

Sample Output 2

294448 2989776 12112684 25422152 30002820 20184912 7484084 1397576 108908 2640