A - Full House

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

配点 : 100 点

問題文

5 枚のカードがあり、それぞれのカードには整数 A,B,C,D,E が書かれています。

この 5 枚組は以下の条件を満たすとき、またそのときに限って、フルハウスであると呼ばれます。

  • 同じ数が書かれたカード 3 枚と、別の同じ数が書かれたカード 2 枚からなる。

5 枚組がフルハウスであるか判定してください。

制約

  • 1 \leq A,B,C,D,E\leq 13
  • A,B,C,D,E 全てが同じ値ではない
  • 入力は全て整数

入力

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

A B C D E

出力

フルハウスである場合 Yes を、そうでないとき No を出力せよ。


入力例 1

1 2 1 2 1

出力例 1

Yes

1 が書かれたカード 3 枚と、2 が書かれたカード 2 枚からなるため、これはフルハウスです。


入力例 2

12 12 11 1 2

出力例 2

No

フルハウスの条件を満たしません。

Score : 100 points

Problem Statement

We have five cards with integers A, B, C, D, and E written on them, one on each card.

This set of five cards is called a Full house if and only if the following condition is satisfied:

  • the set has three cards with a same number written on them, and two cards with another same number written on them.

Determine whether the set is a Full house.

Constraints

  • 1 \leq A,B,C,D,E\leq 13
  • Not all of A, B, C, D, and E are the same.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D E

Output

If the set is a Full house, print Yes; otherwise, print No.


Sample Input 1

1 2 1 2 1

Sample Output 1

Yes

The set has three cards with 1 written on them and two cards with 2 written on them, so it is a Full house.


Sample Input 2

12 12 11 1 2

Sample Output 2

No

The condition is not satisfied.

B - Middle Letter

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

配点 : 100 点

問題文

英小文字からなる長さが奇数の文字列 S が与えられます。

S の中央の文字を出力してください。

中央の文字とは ある長さが奇数の文字列 T について、 T の長さを |T| として、T の前から \frac{|T|+1}{2} 番目の文字を中央の文字とします。

制約

  • S は英小文字からなる長さが奇数の文字列
  • S の長さは 1 以上 99 以下

入力

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

S

出力

答えを出力せよ。


入力例 1

atcoder

出力例 1

o

atcoder の中央の文字は o です。


入力例 2

a

出力例 2

a

Score : 100 points

Problem Statement

You are given an odd-length string S consisting of lowercase English letters.

Print the central character of S.

What is the central character? For an odd-length string T, its central character is the \frac{|T|+1}{2}-th character from the beginning, where |T| is the length of T.

Constraints

  • S is an odd-length string consisting of lowercase English letters.
  • The length of S is between 1 and 99 (inclusive).

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer.


Sample Input 1

atcoder

Sample Output 1

o

The central character of atcoder is o.


Sample Input 2

a

Sample Output 2

a
C - Robot Weight

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

配点 : 200 点

問題文

ロボットがあり、はじめロボットの重さは X です。 このロボットには、同時に取り付けられる部品が種類 1, 種類 2,\ldots, 種類 N の N 種類あります。 種類 i\ (1\le i\le N) の部品の重さは W _ i です。 はじめ、ロボットには N 種類のうちのどの部品もついていません。

次の Q 個のクエリを順に処理してください。 i 番目 (1\le i\le Q) のクエリは、整数 P _ i で表される次のようなクエリです。

  • 現在、ロボットに種類 P _ i の部品がついていない場合は取り付け、ついている場合は取り外す。その後、現在のロボットの重さを出力する。

制約

  • 1\le X\le100
  • 1\le N\le100
  • 1\le W _ i\le100\ (1\le i\le N)
  • 1\le Q\le100
  • 1\le P _ i\le N\ (1\le i\le Q)
  • 入力はすべて整数

入力

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

X
N
W _ 1 W _ 2 \ldots W _ N
Q
P _ 1
P _ 2
\vdots
P _ Q

出力

Q 行にわたって出力せよ。 i 行目 (1\le i\le Q) には、i 番目のクエリを処理した結果を出力せよ。


入力例 1

31
4
15 92 65 35
4
3
1
4
1

出力例 1

96
111
146
131

はじめ、ロボットの重さは 31 です。 それぞれのクエリで、ロボットの重さは次のようになります。

  • 1 番目のクエリでは、種類 3 のパーツをロボットに取り付ける。ロボットの重さは 31+65=96 になる。
  • 2 番目のクエリでは、種類 1 のパーツをロボットに取り付ける。ロボットの重さは 96+15=111 になる。
  • 3 番目のクエリでは、種類 4 のパーツをロボットに取り付ける。ロボットの重さは 111+35=146 になる。
  • 4 番目のクエリでは、種類 1 のパーツをロボットから取り外す。ロボットの重さは 146-15=131 になる。

入力例 2

41
10
73 8 55 26 97 48 37 47 35 55
15
1
2
7
1
6
3
10
8
4
8
1
5
9
9
3

出力例 2

114
122
159
86
134
189
244
291
317
270
343
440
475
440
385

Score : 200 points

Problem Statement

There is a robot, and initially the weight of the robot is X. This robot has N types of parts that can be attached simultaneously: type 1, type 2,\ldots, type N. The weight of the type i\ (1\le i\le N) part is W _ i. Initially, none of the N types of parts are attached to the robot.

Process the following Q queries in order. The i-th query (1\le i\le Q) is represented by an integer P _ i and is as follows:

  • If the type P _ i part is not currently attached to the robot, attach it; if it is attached, remove it. Then, print the current weight of the robot.

Constraints

  • 1\le X\le100
  • 1\le N\le100
  • 1\le W _ i\le100\ (1\le i\le N)
  • 1\le Q\le100
  • 1\le P _ i\le N\ (1\le i\le Q)
  • All input values are integers.

Input

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

X
N
W _ 1 W _ 2 \ldots W _ N
Q
P _ 1
P _ 2
\vdots
P _ Q

Output

Output Q lines. The i-th line (1\le i\le Q) should contain the result of processing the i-th query.


Sample Input 1

31
4
15 92 65 35
4
3
1
4
1

Sample Output 1

96
111
146
131

Initially, the weight of the robot is 31. For each query, the weight of the robot becomes as follows:

  • In the 1-st query, attach the type 3 part to the robot. The weight of the robot becomes 31+65=96.
  • In the 2-nd query, attach the type 1 part to the robot. The weight of the robot becomes 96+15=111.
  • In the 3-rd query, attach the type 4 part to the robot. The weight of the robot becomes 111+35=146.
  • In the 4-th query, remove the type 1 part from the robot. The weight of the robot becomes 146-15=131.

Sample Input 2

41
10
73 8 55 26 97 48 37 47 35 55
15
1
2
7
1
6
3
10
8
4
8
1
5
9
9
3

Sample Output 2

114
122
159
86
134
189
244
291
317
270
343
440
475
440
385
D - Practical Computing

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

配点 : 200 点

問題文

以下のような N 個の整数列 A_0,\ldots,A_{N-1} を求めてください。

  • 各 i (0\leq i \leq N-1) について、A_i の長さは i+1 である。
  • 各 i,j (0\leq i \leq N-1, 0 \leq j \leq i) について、A_i の j+1 番目の値 a_{i,j} は次のように定められる。

    • j=0 または j=i の時、a_{i,j}=1
    • それ以外の時、a_{i,j} = a_{i-1,j-1} + a_{i-1,j}

制約

  • 1 \leq N \leq 30
  • N は整数

入力

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

N

出力

N 行出力せよ。 i 行目には A_{i-1} の値を順に空白区切りで出力せよ。


入力例 1

3

出力例 1

1
1 1
1 2 1

入力例 2

10

出力例 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Score : 200 points

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

  • For each i (0\leq i \leq N-1), the length of A_i is i+1.
  • For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
    • a_{i,j}=1, if j=0 or j=i.
    • a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

  • 1 \leq N \leq 30
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print N lines. The i-th line should contain the terms of A_{i-1} separated by spaces.


Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
E - Final Day

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

配点 : 300 点

問題文

N 人の生徒が 4 日間にわたる試験を受けています。

それぞれの日に行われる試験は 300 点満点です。すなわち、4 日間を通した試験の満点は 1200 点です。

現在 3 日目までの試験が終わり、これから 4 日目の試験が行われようとしています。i \, (1 \leq i \leq N) 番目の生徒は j \, (1 \leq j \leq 3) 日目の試験で P_{i, j} 点獲得しました。

それぞれの生徒について、4 日目の試験後に上位 K 位以内に入っていることがあり得るかどうか判定してください。
ただし、4 日目の試験後の生徒の順位は、その生徒よりも 4 日間の合計点が高い生徒の人数に 1 を加えた値として定めます。

制約

  • 1 \leq K \leq N \leq 10^5
  • 0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
  • 入力は全て整数である。

入力

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

N K
P_{1,1} P_{1,2} P_{1,3}
\vdots
P_{N,1} P_{N,2} P_{N,3}

出力

N 行出力せよ。i \, (1 \leq i \leq N) 行目には、i 番目の生徒が 4 日目の試験後に上位 K 位以内に入っていることがあり得るならば Yes と、そうでないならば No と出力せよ。


入力例 1

3 1
178 205 132
112 220 96
36 64 20

出力例 1

Yes
Yes
No

4 日目に全員が 100 点を取ると、1 番目の生徒が 1 位になります。 4 日目に 2 番目の生徒が 100 点を取り、それ以外の生徒が 0 点を取ると、2 番目の生徒が 1 位になります。 3 番目の生徒が 1 位になることはあり得ません。


入力例 2

2 1
300 300 300
200 200 200

出力例 2

Yes
Yes

入力例 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

出力例 3

Yes
Yes
No
Yes

Score : 300 points

Problem Statement

N students are taking a 4-day exam.

There is a 300-point test on each day, for a total of 1200 points.

The first three days of the exam are already over, and the fourth day is now about to begin. The i-th student (1 \leq i \leq N) got P_{i, j} points on the j-th day (1 \leq j \leq 3).

For each student, determine whether it is possible that he/she is ranked in the top K after the fourth day.
Here, the rank of a student after the fourth day is defined as the number of students whose total scores over the four days are higher than that of the student, plus 1.

Constraints

  • 1 \leq K \leq N \leq 10^5
  • 0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_{1,1} P_{1,2} P_{1,3}
\vdots
P_{N,1} P_{N,2} P_{N,3}

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain Yes if it is possible that the i-th student is ranked in the top K after the fourth day, and No otherwise.


Sample Input 1

3 1
178 205 132
112 220 96
36 64 20

Sample Output 1

Yes
Yes
No

If every student scores 100 on the fourth day, the 1-st student will rank 1-st.
If the 2-nd student scores 100 and the other students score 0 on the fourth day, the 2-nd student will rank 1-st.
The 3-rd student will never rank 1-st.


Sample Input 2

2 1
300 300 300
200 200 200

Sample Output 2

Yes
Yes

Sample Input 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

Sample Output 3

Yes
Yes
No
Yes
F - Loong Tracking

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

配点 : 300 点

問題文

高橋君は座標平面上で龍を操作するゲームを作成しました。

龍は 1 から N までの番号がついた N 個のパーツからなり、パーツ 1 を頭 と呼びます。

最初パーツ i は座標 (i,0) にあります。以下のクエリを Q 個処理してください。

  • 1 C: 頭を方向 C に 1 移動させる。ここで、C は R, L, U, D のいずれかであり、それぞれ x 軸正方向、x 軸負方向、y 軸正方向、y 軸負方向を意味する。頭以外の全てのパーツは前のパーツに追従するように動く。すなわち、パーツ i\ \ (2\leq i \leq N) は移動前にパーツ i-1 があった座標に移動する。
  • 2 p: パーツ p のある座標を求める。

制約

  • 2 \leq N \leq 10^6
  • 1 \leq Q \leq 2\times 10^5
  • 1 種類目のクエリにおいて、C は R, L, U, D のいずれか
  • 2 種類目のクエリにおいて、1\leq p \leq N
  • 入力に含まれる数値は全て整数

入力

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

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

各クエリは以下の 2 種類のいずれかの形式である。

1 C
2 p

出力

2 種類目のクエリの回数を q として q 行出力せよ。
i 行目には、i 番目のそのようなクエリに対する答えの座標を (x,y) としたとき、x,y を空白区切りで出力せよ。


入力例 1

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

出力例 1

3 0
2 0
1 1
1 0
1 0

2 種類目のクエリを処理する各タイミングにおいて、パーツの位置は次のようになっています。

図

複数のパーツが同じ座標に存在しうることに注意してください。

Score : 300 points

Problem Statement

Takahashi has created a game where the player controls a dragon on a coordinate plane.

The dragon consists of N parts numbered 1 to N, with part 1 being called the head.

Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

  • 1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
  • 2 p: Find the coordinates of part p.

Constraints

  • 2 \leq N \leq 10^6
  • 1 \leq Q \leq 2\times 10^5
  • For the first type of query, C is one of R, L, U, and D.
  • For the second type of query, 1\leq p \leq N.
  • All numerical input values are integers.

Input

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

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Each query is in one of the following two formats:

1 C
2 p

Output

Print q lines, where q is the number of queries of the second type.
The i-th line should contain x and y separated by a space, where (x,y) are the answer to the i-th such query.


Sample Input 1

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

Sample Output 1

3 0
2 0
1 1
1 0
1 0

At each time when processing the second type of query, the parts are at the following positions:

Figure

Note that multiple parts may exist at the same coordinates.

G - Max Straight

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

配点 : 400 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

整数列 A の部分列 B=(B_1,B_2,\ldots,B_{|B|}) であって、以下の条件を満たすものの長さの最大値を求めてください。

  • 全ての 1\le i\le |B| - 1 を満たす整数 i に対し、 B_i+1=B_{i+1} が成り立つ。
部分列とは 数列 A の部分列とは、A の要素を 0 個以上選んで削除し、残った要素を元の順序を保って並べた数列のことを指します。

制約

  • 1\le N\le 2\times 10^5
  • 1\le A_i\le 10^9
  • 入力される値は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。


入力例 1

7
3 4 3 5 7 6 2

出力例 1

4

B=(3,4,5,6) は A の部分列であり条件を満たし、その長さは 4 です。

条件を満たす部分列であって長さが 4 より長いものは存在しないので、 4 を出力してください。


入力例 2

5
5 4 3 2 1

出力例 2

1

入力例 3

10
1 2 3 4 5 6 7 8 9 10

出力例 3

10

Score : 400 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Find the maximum length of a subsequence B=(B_1,B_2,\ldots,B_{|B|}) of integer sequence A that satisfies the following condition.

  • B_i+1=B_{i+1} for all integers i satisfying 1\le i\le |B| - 1.
What is a subsequence A subsequence of sequence A is a sequence obtained by choosing zero or more elements of A to delete, and arranging the remaining elements in their original order.

Constraints

  • 1\le N\le 2\times 10^5
  • 1\le A_i\le 10^9
  • 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

Output

Output the answer.


Sample Input 1

7
3 4 3 5 7 6 2

Sample Output 1

4

B=(3,4,5,6) is a subsequence of A that satisfies the condition, and its length is 4.

There is no subsequence satisfying the condition with length greater than 4, so output 4.


Sample Input 2

5
5 4 3 2 1

Sample Output 2

1

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

10
H - Swap Places

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

配点 : 500 点

問題文

頂点に 1 から N までの、辺に 1 から M までの番号がついた N 頂点 M 辺の単純無向グラフがあります。 辺 i は頂点 u_i と頂点 v_i を結んでいます。
また、全ての頂点は赤か青のいずれか一方で塗られています。頂点 i の色は C_i で表されて、C_i が 0 ならば頂点 i は赤く、1 ならば頂点 i は青く塗られています。

今、高橋君が頂点 1 に、青木君が頂点 N にいます。
2 人は次の行動を 0 回以上好きな回数繰り返します。

  • 2 人が同時に、今いる頂点に隣接している頂点のいずれか 1 個に移動する。
    ただし、高橋君の移動先の頂点の色と、青木君の移動先の頂点の色は異なる必要がある。

上記の行動を繰り返すことで、高橋君が頂点 N に、青木君が頂点 1 にいる状態にできますか?
可能である場合は必要な行動回数の最小値を答えてください。不可能である場合は -1 を出力してください。

入力のはじめに T が与えられるので、T 個のテストケースについて問題を解いてください。

制約

  • 1 \leq T \leq 1000
  • 2 \leq N \leq 2000
  • 1 \leq M \leq \min(\frac{N(N-1)}{2}, 2000)
  • C_i \in \lbrace 0, 1 \rbrace
  • 1 \leq u_i, v_i \leq N
  • 入力で与えられるグラフは単純
  • 入力される値は全て整数
  • 全てのテストケースに対する N の総和は 2000 を超えない。
  • 全てのテストケースに対する M の総和は 2000 を超えない。

入力

入力は以下の形式で標準入力から与えられる。ここで \text{test}_i は i 番目のテストケースを意味する。

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

各テストケースは以下の形式で与えられる。

N M
C_1 C_2 \dots C_N
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。
各テストケースでは、高橋君が頂点 N に、青木君が頂点 1 にいる状態にできる場合は必要な行動回数の最小値を、できない場合は -1 を出力せよ。


入力例 1

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

出力例 1

3
-1
3

1 番目のテストケースでは、高橋君と青木君は以下のように行動することで、 3 回の行動で目的の状態を達成することができて、これが最小です。

  • 高橋君が頂点 3 に、青木君が頂点 2 に移動する。
  • 高橋君が頂点 2 に、青木君が頂点 3 に移動する。
  • 高橋君が頂点 4 に、青木君が頂点 1 に移動する。

ここで、1 回目の移動で高橋君と青木君がともに頂点 2 に移動することはできないのに注意してください。(なぜならば、高橋君の移動先の頂点の色と青木君の移動先の頂点の色は異なる必要があるからです。)

2 番目のテストケースでは、2 人はどのように行動しても目的の状態を達成することはできません。

Score : 500 points

Problem Statement

There is a simple undirected graph with N vertices numbered 1 through N and M edges numbered 1 through M. Edge i connects vertex u_i and vertex v_i.
Every vertex is painted either red or blue. The color of vertex i is represented by C_i; vertex i is painted red if C_i is 0 and blue if C_i is 1.

Now, Takahashi is on vertex 1 and Aoki is on vertex N.
They may repeat the following move zero or more times.

  • Each of the two simultaneously moves to a vertex adjacent to the current vertex.
    Here, the vertices that Takahashi and Aoki move to must have different colors.

By repeating the move above, can Takahashi and Aoki simultaneously end up on vertices N and 1, respectively?
If it is possible, find the minimum number of moves required. If it is impossible, print -1.

You are given T at the beginning of the input. Solve the problem for T test cases.

Constraints

  • 1 \leq T \leq 1000
  • 2 \leq N \leq 2000
  • 1 \leq M \leq \min(\frac{N(N-1)}{2}, 2000)
  • C_i \in \lbrace 0, 1 \rbrace
  • 1 \leq u_i, v_i \leq N
  • The graph given in the input is simple.
  • All values in the input are integers.
  • The sum of N over all test cases does not exceed 2000.
  • The sum of M over all test cases does not exceed 2000.

Input

The input is given from Standard Input in the following format, where \text{test}_i denotes the i-th test case:

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

Each test case is given in the following format:

N M
C_1 C_2 \dots C_N
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print T lines. The i-th line should contain the answer to the i-th test case.
For each test case, print the minimum number of moves required for Takahashi and Aoki to simultaneously end up in vertices N and 1, respectively, if it is possible, and -1 otherwise.


Sample Input 1

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

Sample Output 1

3
-1
3

For the 1-st test case, Takahashi and Aoki can achieve the objective by making the following 3 moves, which is the minimum number:

  • Takahashi moves to vertex 3, and Aoki moves to vertex 2.
  • Takahashi moves to vertex 2, and Aoki moves to vertex 3.
  • Takahashi moves to vertex 4, and Aoki moves to vertex 1.

Note that in the 1-st move, it is disallowed that both Takahashi and Aoki move to vertex 2 (because the colors of vertices that Takahashi and Aoki move to must be different.)

For the 2-nd case, no matter how they move, they cannot achieve the objective.

I - Shift Table

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

配点 : 525 点

問題文

高橋君と青木君は、これから N 日間アルバイトをします。
高橋君のシフト表は文字列 S により与えられ、S の i 文字目が # のとき i 日目に出勤、. のとき i 日目に欠勤します。
これをもとに、青木君は以下のようにシフト表を作りました。

  • まず、N でない N の正の約数 M をとる。
  • 次に、1 日目から M 日目までの勤怠を決める。
  • 最後に、i = 1, 2, \ldots, N - M の順に M + i 日目の勤怠が i 日目の勤怠と一致するように M + i 日目の勤怠を決める。

ここで、M の値が異なる場合でも最終的にできたシフトが同じものとなることがあることに注意してください。

N 日すべてについて高橋君と青木君の少なくとも一方が出勤することになったとき、青木君のシフト表として考えられるものの個数を 998244353 で割った余りを求めてください。

制約

  • N は 2 以上 10^5 以下の整数
  • S は 長さ N の #、. からなる文字列

入力

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

N
S

出力

答えを出力せよ。


入力例 1

6
##.#.#

出力例 1

3

高橋君は 1 \cdot 2 \cdot 4 \cdot 6 日目に出勤します。
青木君のシフト表を表す文字列を T とし、青木君は T の i 文字目が # のとき i 日目に出勤、. のとき i 日目に欠勤するとします。
T としてあり得るものは ###### \cdot #.#.#. \cdot .##.## の 3 つです。

1 つめのシフト表は M を 1 または 2 または 3、2 つめのシフト表は M = 2、3 つめのシフト表は M = 3 とすることにより実現できます。


入力例 2

7
...####

出力例 2

1

入力例 3

12
####.####.##

出力例 3

19

Score : 525 points

Problem Statement

Takahashi and Aoki will work part-time for the next N days.
Takahashi's shift schedule is given by the string S, where the i-th character of S is # if he works on the i-th day, and . if he is absent on the i-th day.
Based on this, Aoki created his shift schedule as follows.

  • First, take a positive divisor M of N that is not equal to N.
  • Next, decide the attendance for the first M days.
  • Finally, for i = 1, 2, \ldots, N - M in this order, decide the attendance for the (M + i)-th day so that it matches the attendance for the i-th day.

Note that different values of M may lead to the same final shift schedule.

Find the number of possible shift schedules for Aoki such that at least one of Takahashi and Aoki works on each of the N days, modulo 998244353.

Constraints

  • N is an integer between 2 and 10^5, inclusive.
  • S is a string of length N consisting of # and ..

Input

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

N
S

Output

Print the answer.


Sample Input 1

6
##.#.#

Sample Output 1

3

Takahashi works on days 1, 2, 4, and 6.
Let T be the string representing Aoki's shift schedule, where the i-th character of T is # if he works on the i-th day, and . if he is absent on the i-th day.
There are three possible strings for T: ######, #.#.#., and .##.##.

The first shift schedule can be realized by choosing M = 1 or 2 or 3, the second by choosing M = 2, and the third by choosing M = 3.


Sample Input 2

7
...####

Sample Output 2

1

Sample Input 3

12
####.####.##

Sample Output 3

19