A - Zero Sum Game

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

1 から N の番号が付けられた N 人の人がおり、この中で一対一の勝敗のつくゲームを何度か行いました。N 人は最初にそれぞれ持ち点として 0 を持っており、各ゲームでは勝者の持ち点が 1 増え、敗者の持ち点が 1 減ります(持ち点が負になることもあります)。最終的に人 i\ (1\leq i\leq N-1) の持ち点が A_i になったとき、人 N の持ち点を求めてください。なお、ゲームの進行によらず最終的な人 N の持ち点は一意に定まることが示せます。

制約

  • 2\leq N\leq 100
  • -100\leq A_i\leq 100
  • 入力は全て整数

入力

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

N
A_1 A_2 \ldots A_{N-1}

出力

答えを出力せよ。


入力例 1

4
1 -2 -1

出力例 1

2

最終的に人 1,2,3 の持ち点が 1,-2,-1 となるような進行として、例えば次のようなものが考えられます。

  • 最初、人 1,2,3,4 の持ち点はそれぞれ 0,0,0,0 である。
  • 人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-1,0,0 である。
  • 人 1 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 0,-1,0,1 である。
  • 人 1 と 2 が対戦して、人 1 が勝利する。4 人の持ち点はそれぞれ 1,-2,0,1 である。
  • 人 2 と 3 が対戦して、人 2 が勝利する。4 人の持ち点はそれぞれ 1,-1,-1,1 である。
  • 人 2 と 4 が対戦して、人 4 が勝利する。4 人の持ち点はそれぞれ 1,-2,-1,2 である。

この場合、人 4 の持ち点は 2 になります。ほかにも別の進行が考えられますが、どのような進行であっても人 4 の持ち点は 2 になります。


入力例 2

3
0 0

出力例 2

0

入力例 3

6
10 20 30 40 50

出力例 3

-150

Score: 100 points

Problem Statement

There are N people labeled 1 to N, who have played several one-on-one games without draws. Initially, each person started with 0 points. In each game, the winner's score increased by 1 and the loser's score decreased by 1 (scores can become negative). Determine the final score of person N if the final score of person i\ (1\leq i\leq N-1) is A_i. It can be shown that the final score of person N is uniquely determined regardless of the sequence of games.

Constraints

  • 2 \leq N \leq 100
  • -100 \leq A_i \leq 100
  • All input values are integers.

Input

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

N
A_1 A_2 \ldots A_{N-1}

Output

Print the answer.


Sample Input 1

4
1 -2 -1

Sample Output 1

2

Here is one possible sequence of games where the final scores of persons 1, 2, 3 are 1, -2, -1, respectively.

  • Initially, persons 1, 2, 3, 4 have 0, 0, 0, 0 points, respectively.
  • Persons 1 and 2 play, and person 1 wins. The players now have 1, -1, 0, 0 point(s).
  • Persons 1 and 4 play, and person 4 wins. The players now have 0, -1, 0, 1 point(s).
  • Persons 1 and 2 play, and person 1 wins. The players now have 1, -2, 0, 1 point(s).
  • Persons 2 and 3 play, and person 2 wins. The players now have 1, -1, -1, 1 point(s).
  • Persons 2 and 4 play, and person 4 wins. The players now have 1, -2, -1, 2 point(s).

In this case, the final score of person 4 is 2. Other possible sequences of games exist, but the score of person 4 will always be 2 regardless of the progression.


Sample Input 2

3
0 0

Sample Output 2

0

Sample Input 3

6
10 20 30 40 50

Sample Output 3

-150
B - New Scheme

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

8 個の整数 S_1,S_2,\dots,S_8 が与えられます。 以下の 3 つの条件が全て満たされるならば Yes を、そうでないならば No を出力してください。

  • 数列 (S_1,S_2,\dots,S_8) は広義単調増加である。すなわち、S_1 \leq S_2 \leq \dots \leq S_8 である。
  • S_1,S_2,\dots,S_8 は全て 100 以上 675 以下である。
  • S_1,S_2,\dots,S_8 は全て 25 の倍数である。

制約

  • 0\leq S_i \leq 1000
  • 入力は全て整数

入力

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

S_1 S_2 \dots S_8

出力

答えを出力せよ。


入力例 1

125 175 250 300 400 525 600 650

出力例 1

Yes

3 つの条件を全て満たしています。


入力例 2

100 250 300 400 325 575 625 675

出力例 2

No

S_4 > S_5 であるため、1 つ目の条件を満たしていません。


入力例 3

0 23 24 145 301 413 631 632

出力例 3

No

2 つ目の条件と 3 つ目の条件を満たしていません。

Score : 100 points

Problem Statement

Given eight integers S_1,S_2,\dots, and S_8, print Yes if they satisfy all of the following three conditions, and No otherwise.

  • The sequence (S_1,S_2,\dots,S_8) is monotonically non-decreasing. In other words, S_1 \leq S_2 \leq \dots \leq S_8.
  • S_1,S_2,\dots, and S_8 are all between 100 and 675, inclusive.
  • S_1,S_2,\dots, and S_8 are all multiples of 25.

Constraints

  • 0\leq S_i \leq 1000
  • All input values are integers.

Input

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

S_1 S_2 \dots S_8

Output

Print the answer.


Sample Input 1

125 175 250 300 400 525 600 650

Sample Output 1

Yes

They satisfy all of the three conditions.


Sample Input 2

100 250 300 400 325 575 625 675

Sample Output 2

No

They violate the first condition because S_4 > S_5.


Sample Input 3

0 23 24 145 301 413 631 632

Sample Output 3

No

They violate the second and third conditions.

C - Triangle (Easier)

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, \dots, N の番号が付けられており、i \, (1 \leq i \leq M) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。

以下の条件を全て満たす整数 a, b, c の組の総数を求めてください。

  • 1 \leq a \lt b \lt c \leq N
  • 頂点 a と頂点 b を結ぶ辺が存在する。
  • 頂点 b と頂点 c を結ぶ辺が存在する。
  • 頂点 c と頂点 a を結ぶ辺が存在する。

制約

  • 3 \leq N \leq 100
  • 1 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
  • (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
  • 入力は全て整数

入力

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

N M
U_1 V_1
\vdots
U_M V_M

出力

答えを出力せよ。


入力例 1

5 6
1 5
4 5
2 3
1 4
3 5
2 5

出力例 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) が条件を満たします。


入力例 2

3 1
1 2

出力例 2

0

入力例 3

7 10
1 7
5 7
2 5
3 6
4 7
1 5
2 4
1 3
1 6
2 7

出力例 3

4

Score : 200 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertex U_i and Vertex V_i.

Find the number of tuples of integers a, b, c that satisfy all of the following conditions:

  • 1 \leq a \lt b \lt c \leq N
  • There is an edge connecting Vertex a and Vertex b.
  • There is an edge connecting Vertex b and Vertex c.
  • There is an edge connecting Vertex c and Vertex a.

Constraints

  • 3 \leq N \leq 100
  • 1 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
  • (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
U_1 V_1
\vdots
U_M V_M

Output

Print the answer.


Sample Input 1

5 6
1 5
4 5
2 3
1 4
3 5
2 5

Sample Output 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) satisfy the conditions.


Sample Input 2

3 1
1 2

Sample Output 2

0

Sample Input 3

7 10
1 7
5 7
2 5
3 6
4 7
1 5
2 4
1 3
1 6
2 7

Sample Output 3

4
D - Longest Uncommon Prefix

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。 S の x 文字目 (1 \le x \le N) は S_x です。

i=1,2,\dots,N-1 それぞれについて、以下の条件を全て満たす最大の非負整数 l を求めてください。

  • l+i \le N である。
  • 全ての 1 \le k \le l を満たす整数 k について、 S_{k} \neq S_{k+i} を満たす。

なお、 l=0 は常に条件を満たすことに注意してください。

制約

  • N は 2 \le N \le 5000 を満たす整数
  • S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

N-1 行にわたって出力せよ。そのうち x 行目 (1 \le x < N) には i=x とした場合の答えを整数として出力せよ。


入力例 1

6
abcbac

出力例 1

5
1
2
0
1

この入力では、 S= abcbac です。

  • i=1 のとき、 S_1 \neq S_2, S_2 \neq S_3, \dots ,S_5 \neq S_6 であるため、 最大値は l=5 です。
  • i=2 のとき、 S_1 \neq S_3 ですが S_2 = S_4 であるため、 最大値は l=1 です。
  • i=3 のとき、 S_1 \neq S_4, S_2 \neq S_5 ですが S_3 = S_6 であるため、 最大値は l=2 です。
  • i=4 のとき、 S_1 = S_5 であるため、 最大値は l=0 です。
  • i=5 のとき、 S_1 \neq S_6 であるため、 最大値は l=1 です。

Score : 200 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.

For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:

  • l+i \le N, and
  • for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.

Note that l=0 always satisfies the conditions.

Constraints

  • N is an integer such that 2 \le N \le 5000.
  • S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print (N-1) lines. The x-th (1 \le x < N) line should contain the answer as an integer when i=x.


Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, S= abcbac.

  • When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
  • When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
  • When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
  • When i=4, we have S_1 = S_5, so the maximum value is l=0.
  • When i=5, we have S_1 \neq S_6, so the maximum value is l=1.
E - A+B+C

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 250 点

問題文

3 個の数列 A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), C=(C_1,\ldots,C_L) が与えられます。

さらに数列 X=(X_1,\ldots,X_Q) が与えられるので、各 i=1,\ldots,Q に対して次の問題を解いてください。

問題:A,B,C からそれぞれ 1 個ずつ要素を選び、和を X_i にすることができるか?

制約

  • 1 \leq N,M,L \leq 100
  • 0 \leq A_i, B_i ,C_i \leq 10^8
  • 1 \leq Q \leq 2\times 10^5
  • 0 \leq X_i \leq 3\times 10^8
  • 入力は全て整数である

入力

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

N
A_1 \ldots A_N
M
B_1 \ldots B_M
L
C_1 \ldots C_L
Q
X_1 \ldots X_Q

出力

Q 行出力せよ。
i 行目には、A,B,C からそれぞれ 1 個ずつ要素を選び和を X_i にすることができるならば Yes、できないならば No と出力せよ。


入力例 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

出力例 1

No
Yes
Yes
No
  • A,B,C からそれぞれ 1 個ずつ要素を選び和を 1 にすることはできません。
  • A,B,C からそれぞれ 1,2,2 を選ぶと和を 5 にすることができます。
  • A,B,C からそれぞれ 2,4,4 を選ぶと和を 10 にすることができます。
  • A,B,C からそれぞれ 1 個ずつ要素を選び和を 50 にすることはできません。

Score: 250 points

Problem Statement

You are given three sequences A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), and C=(C_1,\ldots,C_L).

Additionally, a sequence X=(X_1,\ldots,X_Q) is given. For each i=1,\ldots,Q, solve the following problem:

Problem: Is it possible to select one element from each of A, B, and C so that their sum is X_i?

Constraints

  • 1 \leq N,M,L \leq 100
  • 0 \leq A_i, B_i ,C_i \leq 10^8
  • 1 \leq Q \leq 2\times 10^5
  • 0 \leq X_i \leq 3\times 10^8
  • All input values are integers.

Input

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

N
A_1 \ldots A_N
M
B_1 \ldots B_M
L 
C_1 \ldots C_L
Q
X_1 \ldots X_Q

Output

Print Q lines. The i-th line should contain Yes if it is possible to select one element from each of A, B, and C so that their sum is X_i, and No otherwise.


Sample Input 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

Sample Output 1

No
Yes
Yes
No
  • It is impossible to select one element from each of A, B, and C so that their sum is 1.
  • Selecting 1, 2, and 2 from A, B, and C, respectively, makes the sum 5.
  • Selecting 2, 4, and 4 from A, B, and C, respectively, makes the sum 10.
  • It is impossible to select one element from each of A, B, and C so that their sum is 50.
F - Ideal Holidays

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 350 点

問題文

AtCoder 王国の 1 週間は A+B 日からなり、1 日目から A 日目が休日で、A+1 日目から A+B 日目が平日です。

高橋くんは N 個の予定があり、i 番目の予定は今日から D_i 日後です。

高橋くんは今日が 1 週間の何日目かを忘れてしまいました。高橋くんの N 個の予定が全て休日である可能性があるかを判定してください。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq A,B\leq 10^9
  • 1\leq D_1<D_2<\ldots<D_N\leq 10^9

入力

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

N A B
D_1 D_2 \ldots D_N

出力

高橋くんの N 個の予定が全て休日である可能性がある場合は Yes を、そうでない場合は No を一行に出力せよ。


入力例 1

3 2 5
1 2 9

出力例 1

Yes

入力では 1 週間は 7 日からなり、1 日目から 2 日目が休日、3 日目から 7 日目が平日です。

今日が 1 週間の 7 日目だとします。このとき、1 日後は 1 週間の 1 日目、2 日後は 1 週間の 2 日目、9 日後は 1 週間の 2 日目となり、全ての予定が休日となります。そのため、高橋くんの N 個の予定が全て休日である可能性があります。


入力例 2

2 5 10
10 15

出力例 2

No

入力例 3

4 347 347
347 700 705 710

出力例 3

Yes

Score: 350 points

Problem Statement

In the Kingdom of AtCoder, a week consists of A+B days, with the first through A-th days being holidays and the (A+1)-th through (A+B)-th being weekdays.

Takahashi has N plans, and the i-th plan is scheduled D_i days later.

He has forgotten what day of the week it is today. Determine if it is possible for all of his N plans to be scheduled on holidays.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq A,B\leq 10^9
  • 1\leq D_1<D_2<\ldots<D_N\leq 10^9

Input

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

N A B
D_1 D_2 \ldots D_N

Output

Print Yes in a single line if it is possible for all of Takahashi's N plans to be scheduled on holidays, and No otherwise.


Sample Input 1

3 2 5
1 2 9

Sample Output 1

Yes

In this input, a week consists of seven days, with the first through second days being holidays and the third through seventh days being weekdays.

Let us assume today is the seventh day of the week. In this case, one day later would be the first day of the week, two days later would be the second day of the week, and nine days later would also be the second day of the week, making all plans scheduled on holidays. Therefore, it is possible for all of Takahashi's N plans to be scheduled on holidays.


Sample Input 2

2 5 10
10 15

Sample Output 2

No

Sample Input 3

4 347 347
347 700 705 710

Sample Output 3

Yes
G - Flip Cards

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

1 から N までの番号がついた N 枚のカードが一列に並んでいて、各 i\ (1\leq i < N) に対してカード i とカード i+1 が隣り合っています。 カード i の表には A_i が、裏には B_i が書かれており、最初全てのカードは表を向いています。

今から、N 枚のカードのうち好きな枚数 (0 枚でも良い) を選んで裏返すことを考えます。 裏返すカードの選び方は 2^N 通りありますが、そのうち以下の条件を満たすものの数を 998244353 で割った余りを求めてください。

  • 選んだカードを裏返した後、どの隣り合う 2 枚のカードについても、向いている面に書かれた数が相異なる。

制約

  • 1\leq N \leq 2\times 10^5
  • 1\leq A_i,B_i \leq 10^9
  • 入力は全て整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを整数として出力せよ。


入力例 1

3
1 2
4 2
3 4

出力例 1

4

裏返すカードの番号の集合を S とします。

例えば S=\{2,3\} を選ぶと、向いている面に書かれた数はカード 1 から順に 1,2,4 となるため条件を満たします。

一方 S=\{3\} を選ぶと、向いている面に書かれた数はカード 1 から順に 1,4,4 となり、カード 2 とカード 3 の数が一致するため条件を満たしません。

条件を満たす S は \{\},\{1\},\{2\},\{2,3\} の 4 通りです。


入力例 2

4
1 5
2 6
3 7
4 8

出力例 2

16

入力例 3

8
877914575 602436426
861648772 623690081
476190629 262703497
971407775 628894325
822804784 450968417
161735902 822804784
161735902 822804784
822804784 161735902

出力例 3

48

Score : 400 points

Problem Statement

N cards, numbered 1 through N, are arranged in a line. For each i\ (1\leq i < N), card i and card (i+1) are adjacent to each other. Card i has A_i written on its front, and B_i written on its back. Initially, all cards are face up.

Consider flipping zero or more cards chosen from the N cards. Among the 2^N ways to choose the cards to flip, find the number, modulo 998244353, of such ways that:

  • when the chosen cards are flipped, for every pair of adjacent cards, the integers written on their face-up sides are different.

Constraints

  • 1\leq N \leq 2\times 10^5
  • 1\leq A_i,B_i \leq 10^9
  • All values in the input are integers.

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the answer as an integer.


Sample Input 1

3
1 2
4 2
3 4

Sample Output 1

4

Let S be the set of card numbers to flip.

For example, when S=\{2,3\} is chosen, the integers written on their visible sides are 1,2, and 4, from card 1 to card 3, so it satisfies the condition.

On the other hand, when S=\{3\} is chosen, the integers written on their visible sides are 1,4, and 4, from card 1 to card 3, where the integers on card 2 and card 3 are the same, violating the condition.

Four S satisfy the conditions: \{\},\{1\},\{2\}, and \{2,3\}.


Sample Input 2

4
1 5
2 6
3 7
4 8

Sample Output 2

16

Sample Input 3

8
877914575 602436426
861648772 623690081
476190629 262703497
971407775 628894325
822804784 450968417
161735902 822804784
161735902 822804784
822804784 161735902

Sample Output 3

48
H - Pac-Takahashi

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点 : 475 点

問題文

H 行 W 列のグリッドがあります。 上から i 行目、左から j 列目のマス目を (i,j) と表します。 グリッドの各マスはスタートマス、ゴールマス、空マス、壁マス、お菓子マスのいずれかです。 (i,j) が何のマスであるかは文字 A_{i,j} によって表され、A_{i,j}= S のときスタートマス、 A_{i,j}= G のときゴールマス、 A_{i,j}= . のとき空マス、 A_{i,j}= # のとき壁マス、 A_{i,j}= o のときお菓子マスです。 ここで、スタートマスとゴールマスはちょうど 1 つずつあり、お菓子マスは 18 個以下であることが保証されます。

高橋くんは現在スタートマスにいます。 高橋くんは、上下左右に隣接するマスであって壁マスでないマスに移動することを繰り返し行えます。 高橋くんは今から T 回以下の移動によってゴールマスに到達したいです。 そのようなことは可能かどうか判定してください。 可能な場合は、最終的にゴールマスにいるという条件のもとで、移動の途中に訪れるお菓子マスの数の最大値を求めてください。 ただし、1 つのお菓子マスに複数回訪れた場合でも、カウントするのは 1 回のみです。

制約

  • 1\leq H,W \leq 300
  • 1 \leq T \leq 2\times 10^6
  • H,W,T は整数
  • A_{i,j} は S, G, ., #, o のいずれか
  • A_{i,j}= S を満たす (i,j) の組がちょうど 1 つ存在する
  • A_{i,j}= G を満たす (i,j) の組がちょうど 1 つ存在する
  • A_{i,j}= o を満たす (i,j) の組は 18 個以下

入力

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

H W T
A_{1,1}A_{1,2}\dots A_{1,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}

出力

T 回以下の移動によってゴールマスに到達することが不可能ならば -1 を出力せよ。 可能ならば、最終的にゴールマスにいるという条件のもとで、移動の途中に訪れるお菓子マスの数の最大値を出力せよ。


入力例 1

3 3 5
S.G
o#o
.#.

出力例 1

1

(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3) と 4 回移動すると、 1 個のお菓子マスを訪れた上で最終的にゴールマスにいることができます。 5 回以下の移動で 2 個のお菓子マスを訪れた上で最終的にゴールマスにいることはできないので、1 が答えです。

なお、(1,1) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) と移動すると 5 回の移動で 2 個のお菓子マスを訪れることができますが、最終的にゴールマスにいないため無効であることに注意してください。


入力例 2

3 3 1
S.G
.#o
o#.

出力例 2

-1

1 回以下の移動でゴールマスに到達することはできません。


入力例 3

5 10 2000000
S.o..ooo..
..o..o.o..
..o..ooo..
..o..o.o..
..o..ooo.G

出力例 3

18

Score : 475 points

Problem Statement

We have a grid with H rows and W columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left. Each square in the grid is one of the following: the start square, the goal square, an empty square, a wall square, and a candy square. (i,j) is represented by a character A_{i,j}, and is the start square if A_{i,j}= S, the goal square if A_{i,j}= G, an empty square if A_{i,j}= ., a wall square if A_{i,j}= #, and a candy square if A_{i,j}= o. Here, it is guaranteed that there are exactly one start, exactly one goal, and at most 18 candy squares.

Takahashi is now at the start square. He can repeat moving to a vertically or horizontally adjacent non-wall square. He wants to reach the goal square in at most T moves. Determine whether it is possible. If it is possible, find the maximum number of candy squares he can visit on the way to the goal square, where he must finish. Each candy square counts only once, even if it is visited multiple times.

Constraints

  • 1\leq H,W \leq 300
  • 1 \leq T \leq 2\times 10^6
  • H, W, and T are integers.
  • A_{i,j} is one of S, G, ., #, and o.
  • Exactly one pair (i,j) satisfies A_{i,j}= S.
  • Exactly one pair (i,j) satisfies A_{i,j}= G.
  • At most 18 pairs (i,j) satisfy A_{i,j}= o.

Input

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

H W T
A_{1,1}A_{1,2}\dots A_{1,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}

Output

If it is impossible to reach the goal square in at most T moves, print -1. Otherwise, print the maximum number of candy squares that can be visited on the way to the goal square, where Takahashi must finish.


Sample Input 1

3 3 5
S.G
o#o
.#.

Sample Output 1

1

If he makes four moves as (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3), he can visit one candy square and finish at the goal square. He cannot make five or fewer moves to visit two candy squares and finish at the goal square, so the answer is 1.

Note that making five moves as (1,1) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) to visit two candy squares is invalid since he would not finish at the goal square.


Sample Input 2

3 3 1
S.G
.#o
o#.

Sample Output 2

-1

He cannot reach the goal square in one or fewer moves.


Sample Input 3

5 10 2000000
S.o..ooo..
..o..o.o..
..o..ooo..
..o..o.o..
..o..ooo.G

Sample Output 3

18
I - Double Chance

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

カード 1, カード 2, \ldots, カード N の N 枚のカードがあり、 カード i (1\leq i\leq N) には整数 A_i が書かれています。

K=1,2,\ldots,N について、次の問題を解いてください。

カード 1, カード 2, \ldots, カード K の K 枚のカードが入っている袋があります。
次の操作を 2 回繰り返し、記録された数を順に x,y とします。

袋から無作為にカードを 1 枚取り出し、カードに書かれている数を記録する。その後、カードを 袋の中に戻す 。

\max(x,y) の値の期待値を \text{mod} 998244353 で出力してください(注記参照)。
ただし、\max(x,y) で x と y のうち小さくない方の値を表します。

注記

求める期待値は必ず有限値かつ有理数となることが証明できます。また、この問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を出力してください。

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_i \leq 2\times 10^5
  • 入力は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

N 行出力せよ。 i 行目 (1\leq i\leq N) には、K=i の時の問題に対する答えを出力せよ。


入力例 1

3
5 7 5

出力例 1

5
499122183
443664163

例えば、K=2 の時の答えは次のようにして求まります。

袋の中にはカード 1 とカード 2 が入っており、それぞれには A_1=5 と A_2=7 が書かれています。

  • 1 回目に取り出されたカードがカード 1 、2 回目に取り出されたカードもカード 1 のとき、x=y=5 であり、\max(x,y)=5 となります。
  • 1 回目に取り出されたカードがカード 1 、2 回目に取り出されたカードはカード 2 のとき、x=5, y=7 であり、\max(x,y)=7 となります。
  • 1 回目に取り出されたカードがカード 2 、2 回目に取り出されたカードはカード 1 のとき、x=7, y=5 であり、\max(x,y)=7 となります。
  • 1 回目に取り出されたカードがカード 2 、2 回目に取り出されたカードもカード 2 のとき、x=y=7 であり、\max(x,y)=7 となります。

これらが等確率で起こるため、期待値は \frac{5+7+7+7}{4}=\frac{13}{2} となります。 499122183\times 2\equiv 13 \pmod{998244353} であるため、499122183 を出力します。


入力例 2

7
22 75 26 45 72 81 47

出力例 2

22
249561150
110916092
873463862
279508479
360477194
529680742

Score : 500 points

Problem Statement

There are N cards called card 1, card 2, \ldots, card N. On card i (1\leq i\leq N), an integer A_i is written.

For K=1, 2, \ldots, N, solve the following problem.

We have a bag that contains K cards: card 1, card 2, \ldots, card K.
Let us perform the following operation twice, and let x and y be the numbers recorded, in the recorded order.

Draw a card from the bag uniformly at random, and record the number written on that card. Then, return the card to the bag.

Print the expected value of \max(x,y), modulo 998244353 (see Notes).
Here, \max(x,y) denotes the value of the greater of x and y (or x if they are equal).

Notes

It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} with two coprime integers P and Q, it can be proved that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print this R.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_i \leq 2\times 10^5
  • All values in the input are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print N lines. The i-th line (1\leq i\leq N) should contain the answer to the problem for K=i.


Sample Input 1

3
5 7 5

Sample Output 1

5
499122183
443664163

For instance, the answer for K=2 is found as follows.

The bag contains card 1 and card 2, with A_1=5 and A_2=7 written on them, respectively.

  • If you draw card 1 in the first draw and card 1 again in the second draw, we have x=y=5, so \max(x,y)=5.
  • If you draw card 1 in the first draw and card 2 in the second draw, we have x=5 and y=7, so \max(x,y)=7.
  • If you draw card 2 in the first draw and card 1 in the second draw, we have x=7 and y=5, so \max(x,y)=7.
  • If you draw card 2 in the first draw and card 2 again in the second draw, we have x=y=7, so \max(x,y)=7.

These events happen with the same probability, so the sought expected value is \frac{5+7+7+7}{4}=\frac{13}{2}. We have 499122183\times 2\equiv 13 \pmod{998244353}, so 499122183 should be printed.


Sample Input 2

7
22 75 26 45 72 81 47

Sample Output 2

22
249561150
110916092
873463862
279508479
360477194
529680742