AtCoder Daily Training ALL 2026/09/17 16:00start

A - Job Interview

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君はある会社の採用面接を受けました。

面接官の人数 N と、各面接官の高橋君への評価を表す長さ N の文字列 S が与えられます。
i=1,2,\ldots,N に対し S の i 文字目が i 番目の面接官の評価に対応し、o は「良」、- は「可」、x は「不可」を表します。

高橋君は以下の 2 つの条件を両方満たすならば合格、そうでなければ不合格です。

「良」と評価した面接官が少なくとも 1 人いる
「不可」と評価した面接官がいない

高橋君が合格かどうかを判定してください。

制約

1 \leq N \leq 100
S は o, -, x のみからなる長さが N の文字列

入力

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

N
S

出力

高橋君が合格ならば Yes と、そうでなければ No と出力せよ。

入力例 1

4
oo--

出力例 1

Yes

1, 2 番目の面接官が「良」と評価していて、さらに「不可」と評価した面接官がいないため合格です。

入力例 2

3
---

出力例 2

No

「良」と評価した面接官が 1 人もいないため不合格です。

入力例 3

1
o

出力例 3

Yes

入力例 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

出力例 4

No

100 番目の面接官が「不可」と評価しているため不合格です。

Score : 100 points

Problem Statement

Takahashi had a job interview.

You are given the number of interviewers, N, and a string S of length N representing the interviewers' evaluations of him.
For each i=1,2,\ldots,N, the i-th character of S corresponds to the i-th interviewer's evaluation; o means Good, - means Fair, and x means Poor.

Takahashi will pass if both of the following conditions are satisfied, and fail otherwise.

At least one interviewer's evaluation is Good.
No interviewer's evaluation is Poor.

Determine whether Takahashi passes.

Constraints

1 \leq N \leq 100
S is a string of length N consisting of o, -, and x.

Input

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

N
S

Output

If Takahashi passes, print Yes; otherwise, print No.

Sample Input 1

4
oo--

Sample Output 1

Yes

The first and second interviewers' evaluations are Good, and no interviewer's evaluation is Poor, so he passes.

Sample Input 2

3
---

Sample Output 2

No

No interviewer's evaluation is Good, so he fails.

Sample Input 3

1
o

Sample Output 3

Yes

Sample Input 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

Sample Output 4

No

The 100-th interviewer's evaluation is Poor, so he fails.

B - Balloon Trip

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 W,B が与えられるので、以下の問題を解いてください。

高橋君の体重は W {\rm [kg]} です。 (単位が {\rm kg} であることに注意してください)
風船を n 個付けられた物体は、物体の質量が nB {\rm [g]} 未満である時、またその時に限り、空に飛び立ちます。
高橋君を空に飛ばすためには、最低何個の風船を付ける必要がありますか？

制約

1 \le W \le 100
1 \le B \le 100
入力される値は全て整数

入力

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

W B

出力

答えを出力せよ。

入力例 1

80 5

出力例 1

高橋君の体重は 80 {\rm kg} = 80000 {\rm g} です。
高橋君に風船を 16001 個付けると、高橋君の質量は 16001 \times 5=80005 {\rm g} 未満であるため、空に飛び立ちます。
16000 個では不十分であることに注意してください。

入力例 2

70 6

出力例 2

入力例 3

100 100

出力例 3

Score : 100 points

Problem Statement

Given integers W and B, solve the following problem.

Takahashi's weight is W {\rm [kg]}. (Note that the unit is {\rm kg}.)
An object attached with n balloons will fly into the sky if and only if the mass of the object is strictly less than nB {\rm [g]}.
What is the minimum number of balloons needed to make Takahashi fly into the sky?

Constraints

1 \le W \le 100
1 \le B \le 100
All input values are integers.

Input

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

W B

Output

Output the answer.

Sample Input 1

80 5

Sample Output 1

Takahashi's weight is 80 {\rm kg} = 80000 {\rm g}.
If he is attached with 16001 balloons, his mass is less than 16001 \times 5=80005 {\rm g}, so he will fly into the sky.
Note that 16000 balloons are not sufficient.

Sample Input 2

70 6

Sample Output 2

Sample Input 3

100 100

Sample Output 3

C - Call the ID Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

人 1 、人 2 、\ldots 、人 N と番号をつけられた N 人の人がいます。

N 人は、人 1 、人 2 、\ldots 、人 N の順番に下記の行動をちょうど 1 回ずつ行います。

人 i 自身がまだ一度も番号を呼ばれていないなら、人 A_i の番号を呼ぶ。

最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙してください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq N
A_i \neq i
入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

下記の形式にしたがって、最後まで番号を一度も呼ばれない人全員の番号を昇順に列挙せよ。

K
X_1 X_2 \ldots X_K

すなわち、まず 1 行目に、最後まで番号を一度も呼ばれない人の人数 K を出力し、 2 行目に、最後まで番号を一度も呼ばれない人全員の番号を昇順に並べた列 (X_1, X_2, \ldots, X_K) を空白区切りで出力せよ。

入力例 1

5
3 1 4 5 4

出力例 1

2
2 4

5 人の行動は下記の通りです。

人 1 はまだ番号を一度も呼ばれていないので、人 1 は人 3 の番号を呼びます。
人 2 はまだ番号を一度も呼ばれていないので、人 2 は人 1 の番号を呼びます。
人 3 はすでに人 1 によって番号を呼ばれているので、何もしません。
人 4 はまだ番号を一度も呼ばれていないので、人 4 は人 5 の番号を呼びます。
人 5 はすでに人 4 によって番号を呼ばれているので、何もしません。

よって、最後まで番号を一度も呼ばれないのは人 2 と人 4 です。

入力例 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

出力例 2

10
1 2 5 6 8 11 14 17 18 20

Score : 200 points

Problem Statement

There are N people whose IDs are 1, 2, \ldots, and N.

Each of person 1, person 2, \ldots, and person N performs the following action once in this order:

If person i's ID has not been called out yet, call out person A_i's ID.

Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq N
A_i \neq i
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

Enumerate the IDs of all the people whose IDs are not called out until the end in ascending order in the following format:

K
X_1 X_2 \ldots X_K

In other words, the first line should contain the number of people, K, whose IDs are never called out until the end; the second line should contain the sequence (X_1, X_2, \ldots, X_K) of IDs of such people in ascending order, with spaces in between.

Sample Input 1

5
3 1 4 5 4

Sample Output 1

2
2 4

The five people's actions are as follows.

Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
Person 3's ID has already been called out by person 1, so nothing happens.
Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
Person 5's ID has already been called out by person 4, so nothing happens.

Therefore, person 2 and 4's IDs are not called out until the end.

Sample Input 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

Sample Output 2

10
1 2 5 6 8 11 14 17 18 20

D - Nice Grid

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

次の図に示す、各マスが黒または白に塗られた縦 15 行 \times 横 15 列のグリッドにおいて、上から R 行目、左から C 列目のマスが何色かを出力して下さい。

制約

1 \leq R, C \leq 15
R, C は整数

入力

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

R C

出力

図のグリッドにおいて上から R 行目、左から C 列目のマスが黒色の場合は black と、白色の場合は white と出力せよ。ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入力例 1

3 5

出力例 1

black

図のグリッドにおいて上から 3 行目、左から 5 列目のマスは黒色です。よって、black と出力します。

入力例 2

4 5

出力例 2

white

図のグリッドにおいて上から 4 行目、左から 5 列目のマスは白色です。よって、white と出力します。

Score : 200 points

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

1 \leq R, C \leq 15
R and C are integers.

Input

Input is given from Standard Input in the following format:

R C

Output

In the grid above, if the color of the cell at the R-th row from the top and C-th column from the left is black, then print black; if the cell is white, then print white. Note that the judge is case-sensitive.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

E - Illuminate Buildings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

N 棟のビルが等間隔に一列に並んでいます。手前から i 番目のビルの高さは H_i です。

あなたは次の条件をともに満たすようにいくつかのビルを選んで電飾で飾ろうとしています。

選んだビルたちは高さが等しい
選んだビルたちは等間隔に並んでいる

最大でいくつのビルを選ぶことができますか？　なお、ちょうど 1 つのビルを選んだときは条件を満たすとみなします。

制約

1 \leq N \leq 3000
1 \leq H_i \leq 3000
入力は全て整数である

入力

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

N
H_1 \ldots H_N

出力

答えを出力せよ。

入力例 1

8
5 7 5 7 7 5 7 7

出力例 1

手前から 2,5,8 番目のビルを選ぶと条件を満たします。

入力例 2

10
100 200 300 400 500 600 700 800 900 1000

出力例 2

1つのビルを選んだときは条件を満たすとみなします。

入力例 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

出力例 3

Score : 350 points

Problem Statement

There are N buildings arranged in a line at equal intervals. The height of the i-th building from the front is H_i.

You want to decorate some of these buildings with illuminations so that both of the following conditions are satisfied:

The chosen buildings all have the same height.
The chosen buildings are arranged at equal intervals.

What is the maximum number of buildings you can choose? If you choose exactly one building, it is considered to satisfy the conditions.

Constraints

1 \leq N \leq 3000
1 \leq H_i \leq 3000
All input values are integers.

Input

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

N
H_1 \ldots H_N

Output

Print the answer.

Sample Input 1

8
5 7 5 7 7 5 7 7

Sample Output 1

Choosing the 2nd, 5th, and 8th buildings from the front satisfies the conditions.

Sample Input 2

10
100 200 300 400 500 600 700 800 900 1000

Sample Output 2

Choosing just one building is considered to satisfy the conditions.

Sample Input 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

Sample Output 3

F - Operate 1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

この問題は F 問題 (Operate K) の部分問題であり、 K=1 です。
F 問題に正解するコードをこの問題に提出することで、この問題に正解できます。

文字列 S に対して以下の操作を 0 回以上 K 回以下行って、文字列 T と一致させられるか判定してください。

次の 3 種類の操作のうちひとつを選択し、実行する。
- S 中の (先頭や末尾を含む) 任意の位置に、任意の文字を 1 つ挿入する。
- S 中の文字を 1 つ選び、削除する。
- S 中の文字を 1 つ選び、別の 1 つの文字に変更する。

制約

S,T は英小文字からなる長さ 1 以上 500000 以下の文字列
\color{red}{K=1}

入力

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

K
S
T

出力

K 回以下の操作で S を T に一致させられる時 Yes 、そうでない時 No と出力せよ。

入力例 1

1
abc
agc

出力例 1

Yes

abc の 2 文字目の b を g に置き換えることで、 abc を 1 回の操作で agc に変換できます。

入力例 2

1
abc
awtf

出力例 2

No

1 回の操作では abc を awtf に変換できません。

入力例 3

1
abc
ac

出力例 3

Yes

abc の 2 文字目の b を削除することで、 abc を 1 回の操作で ac に変換できます。

入力例 4

1
back
black

出力例 4

Yes

back の 1 文字目と 2 文字目の間に l を挿入することで、 back を 1 回の操作で black に変換できます。

入力例 5

1
same
same

出力例 5

Yes

初めから S=T である場合もあります。

入力例 6

1
leap
read

出力例 6

No

Score : 350 points

Problem Statement

This problem is a sub-problem of Problem F (Operate K), with K=1.
You can solve this problem by submitting a correct solution for Problem F to this problem.

Determine whether it is possible to perform the following operation on string S between 0 and K times, inclusive, to make it identical to string T.

Choose one of the following three operations and execute it.
- Insert any one character at any position in S (possibly the beginning or end).
- Delete one character from S.
- Choose one character in S and replace it with another character.

Constraints

Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.
\color{red}{K=1}

Input

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

K
S
T

Output

If S can be made identical to T with at most K operations, print Yes; otherwise, print No.

Sample Input 1

1
abc
agc

Sample Output 1

Yes

Replacing the second character b of abc with g converts abc to agc in one operation.

Sample Input 2

1
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf in one operation.

Sample Input 3

1
abc
ac

Sample Output 3

Yes

Deleting the second character b of abc converts abc to ac in one operation.

Sample Input 4

1
back
black

Sample Output 4

Yes

Inserting l between the first and second characters of back converts back to black in one operation.

Sample Input 5

1
same
same

Sample Output 5

Yes

It is also possible that S = T from the beginning.

Sample Input 6

1
leap
read

Sample Output 6

No

G - Step Up Robot

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

無限に続く階段があります。一番下は 0 段目で、1 段のぼるごとに 1 段目、2 段目と続きます。

0 段目に階段登りロボットがいます。階段登りロボットは、一回の動作で A _ 1,A _ 2,\ldots,A _ N 段ぶん階段をのぼることができます。つまり、階段登りロボットが i 段目にいるとき、一回動作をした後は i+A _ 1 段目、i+A _ 2 段目、⋯、i+A _ N 段目のいずれかにいることができます。それ以外の段数を一回の動作でのぼることはできません。階段登りロボットは階段を下ることもできません。

階段の B _ 1,B _ 2,\ldots,B _ M 段目にはモチが設置されています。モチが設置されている段へのぼるとロボットは動けなくなり、他の段に移動することができなくなります。

階段登りロボットは階段のちょうど X 段目にのぼりたいです。階段登りロボットが階段のちょうど X 段目にのぼることが可能か判定してください。

制約

1\leq N\leq10
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
1\leq M\leq10^5
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N
M
B _ 1 B _ 2 \ldots B _ M
X

出力

階段登りロボットが階段のちょうど X 段目にのぼることができるとき Yes を、そうでないとき No を 1 行に出力せよ。

入力例 1

出力例 1

Yes

例えば、次のようにして 15 段目に到達することができます。

階段を 3 段のぼる。ロボットは 3 段目に移動する。
階段を 4 段のぼる。ロボットは 7 段目に移動する。
階段を 5 段のぼる。ロボットは 12 段目に移動する。
階段を 3 段のぼる。ロボットは 15 段目に移動する。

入力例 2

出力例 2

No

どのように移動しても階段登りロボットが階段のちょうど 8 段目にいることはできません。

入力例 3

4
2 5 7 8
5
2 9 10 11 19
20

出力例 3

Yes

Score : 400 points

Problem Statement

There is a staircase with infinite steps. The foot of the stairs is the 0-th step, the next step is the 1-st step, the next is the 2-nd, and so on.

There is a stair-climbing robot on the 0-th step. The robot can climb up A _ 1,A _ 2,\ldots, or A _ N steps at a time. In other words, when the robot is on the i-th step, it can step onto one of the (i+A _ 1)-th step, (i+A _ 2)-th step, \ldots, and (i+A _ N)-th step, but not onto the others in a single step. The robot cannot descend the stairs, either.

There are traps on the B _ 1-th, B _ 2-th, \ldots, and B _ M-th steps. Once the robot steps onto a step with a trap, it cannot move anymore.

The robot wants to step onto the X-th step. Determine whether it is possible to do so.

Constraints

1\leq N\leq10
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
1\leq M\leq10^5
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^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
M
B _ 1 B _ 2 \ldots B _ M
X

Output

In a single line, print Yes if the robot can step onto the X-th step, and No otherwise.

Sample Input 1

Sample Output 1

Yes

For example, the robot can reach the 15-th step as follows.

Climb up 3 steps. The robot is now on the 3-rd step.
Climb up 4 steps. The robot is now on the 7-th step.
Climb up 5 steps. The robot is now on the 12-th step.
Climb up 3 steps. The robot is now on the 15-th step.

Sample Input 2

Sample Output 2

No

No matter how the robot moves, it cannot step onto the 8-th step.

Sample Input 3

4
2 5 7 8
5
2 9 10 11 19
20

Sample Output 3

Yes

H - Reachability Query

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N 頂点 0 辺の無向グラフが与えられます。
頂点には 1,2,\dots,N の番号が付けられており、最初は全ての頂点が白色です。
以下の 3 種類のクエリを合計 Q 個処理して下さい。

タイプ 1 : 頂点 u,v を結ぶ無向辺を追加する。
タイプ 2 : 頂点 v が白色なら黒色に、黒色なら白色に変更する。
タイプ 3 : 頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できるか判定し、到達できるなら Yes 、到達できないなら No と答える。

制約

入力は全て整数
1 \le N \le 2 \times 10^5
1 \le Q \le 6 \times 10^5
タイプ 1 のクエリは以下の制約を満たす。
- 1 \le u < v \le N
- 各クエリについて、そのクエリより前に u,v を結ぶ辺は追加されていない。
タイプ 2,3 のクエリは以下の制約を満たす。
- 1 \le v \le N

入力

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

N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q

但し、 \rm{Query}_i は i 個目のクエリを表す。

タイプ 1 のクエリは以下の形式で与えられる。

1 u v

タイプ 2 のクエリは以下の形式で与えられる。

2 v

タイプ 3 のクエリは以下の形式で与えられる。

3 v

出力

タイプ 3 のクエリが現れる度に、その解答を次の通りに出力せよ。

頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できるなら Yes
頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できないなら No

入力例 1

出力例 1

No
Yes
No
Yes
Yes
No

この入力では、グラフは最初 5 頂点 0 辺です。
この入力には 12 個のクエリが含まれます。

1 個目のクエリは 3 2 です。
- この時点で頂点 2 から 0 本以上の辺を辿って黒色の頂点に到達できないので、 No と解答します。
2 個目のクエリは 2 2 です。
- 頂点 2 は白色なので、黒色に変更します。
3 個目のクエリは 3 2 です。
- この時点で頂点 2 から 0 本以上の辺を辿って黒色の頂点 2 に到達できます。よって、 Yes と解答します。
4 個目のクエリは 1 2 5 です。
- 頂点 2,5 を結ぶ辺を追加します。
5 個目のクエリは 1 3 4 です。
- 頂点 3,4 を結ぶ辺を追加します。
6 個目のクエリは 3 4 です。
- この時点で頂点 4 から 0 本以上の辺を辿って黒色の頂点に到達できないので、 No と解答します。
7 個目のクエリは 3 5 です。
- この時点で頂点 5 から 0 本以上の辺を辿って黒色の頂点 2 に到達できます。よって、 Yes と解答します。
8 個目のクエリは 1 4 5 です。
- 頂点 4,5 を結ぶ辺を追加します。
9 個目のクエリは 1 1 3 です。
- 頂点 1,3 を結ぶ辺を追加します。
10 個目のクエリは 3 1 です。
- この時点で頂点 1 から 0 本以上の辺を辿って黒色の頂点 2 に到達できます。よって、 Yes と解答します。
11 個目のクエリは 2 2 です。
- 頂点 2 は黒色なので、白色に変更します。
12 個目のクエリは 3 1 です。
- この時点で頂点 1 から 0 本以上の辺を辿って黒色の頂点に到達できないので、 No と解答します。

Score : 450 points

Problem Statement

You are given an undirected graph with N vertices and zero edges.
The vertices are numbered 1,2,\dots,N, and initially all vertices are white.
Process a total of Q queries of the following three types:

Type 1 : Add an undirected edge connecting vertices u and v.
Type 2 : If vertex v is white, change it to black; if it is black, change it to white.
Type 3 : Determine whether a black vertex can be reached from vertex v by traversing zero or more edges; report Yes if reachable, and No otherwise.

Constraints

All input values are integers.
1 \le N \le 2 \times 10^5
1 \le Q \le 6 \times 10^5
Type 1 queries satisfy the following constraints:
- 1 \le u < v \le N
- For each query, no edge connecting u and v has been added before that query.
Type 2,3 queries satisfy the following constraints:
- 1 \le v \le N

Input

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

N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q

where \rm{Query}_i represents the i-th query.

Type 1 queries are given in the following format:

1 u v

Type 2 queries are given in the following format:

2 v

Type 3 queries are given in the following format:

3 v

Output

For each type 3 query, output the answer as follows:

Yes if a black vertex can be reached from vertex v by traversing zero or more edges;
No if no black vertex can be reached from vertex v by traversing zero or more edges.

Sample Input 1

Sample Output 1

No
Yes
No
Yes
Yes
No

In this input, the graph initially has five vertices and zero edges.
This input contains 12 queries.

The 1st query is 3 2.
- At this point, no black vertex can be reached from vertex 2 by traversing zero or more edges, so report No.
The 2nd query is 2 2.
- Vertex 2 is white, so change it to black.
The 3rd query is 3 2.
- At this point, black vertex 2 can be reached from vertex 2 by traversing zero or more edges. Therefore, report Yes.
The 4th query is 1 2 5.
- Add an edge connecting vertices 2,5.
The 5th query is 1 3 4.
- Add an edge connecting vertices 3,4.
The 6th query is 3 4.
- At this point, no black vertex can be reached from vertex 4 by traversing zero or more edges, so report No.
The 7th query is 3 5.
- At this point, black vertex 2 can be reached from vertex 5 by traversing zero or more edges. Therefore, report Yes.
The 8th query is 1 4 5.
- Add an edge connecting vertices 4,5.
The 9th query is 1 1 3.
- Add an edge connecting vertices 1,3.
The 10th query is 3 1.
- At this point, black vertex 2 can be reached from vertex 1 by traversing zero or more edges. Therefore, report Yes.
The 11th query is 2 2.
- Vertex 2 is black, so change it to white.
The 12th query is 3 1.
- At this point, no black vertex can be reached from vertex 1 by traversing zero or more edges, so report No.

I - Integer Division

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

10 進表記で N 桁の正整数 X が与えられます。X の各桁は 0 ではありません。
\lbrace 1,2, \ldots, N-1 \rbrace の部分集合 S に対し、f(S) を以下のように定義します。

X を 10 進表記したものを長さ N の文字列とみなし、i \in S のとき、またそのときに限り文字列の i 文字目と i + 1 文字目に区切りを入れることで |S| + 1 個の文字列に分解する。
このようにして得られた |S|+1 個の文字列を 10 進表記された整数とみなし、f(S) をこれら |S|+1 個の整数の積で定める。

S としてあり得るものは空集合を含めて 2^{N-1} 通りありますが、これら全てに対する f(S) の総和を 998244353 で割った余りを求めてください。

制約

2 \leq N \leq 2 \times 10^5
X は 10 進表記で N 桁で、各桁は 0 でない
入力はすべて整数

入力

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

N
X

出力

答えを出力せよ。

入力例 1

3
234

出力例 1

S = \emptyset とすると、f(S) = 234 です。
S = \lbrace 1 \rbrace とすると、f(S) = 2 \times 34 = 68 です。
S = \lbrace 2 \rbrace とすると、f(S) = 23 \times 4 = 92 です。
S = \lbrace 1, 2 \rbrace とすると、f(S) = 2 \times 3 \times 4 = 24 です。
234 + 68 + 92 + 24 = 418 であるため、418 を出力します。

入力例 2

4
5915

出力例 2

入力例 3

9
998244353

出力例 3

258280134

Score : 500 points

Problem Statement

You are given a positive integer X with N digits in decimal representation. None of the digits of X is 0.
For a subset S of \lbrace 1,2, \ldots, N-1 \rbrace , let f(S) be defined as follows.

See the decimal representation of X as a string of length N, and decompose it into |S| + 1 strings by splitting it between the i-th and (i + 1)-th characters if and only if i \in S.
Then, see these |S| + 1 strings as integers in decimal representation, and let f(S) be the product of these |S| + 1 integers.

There are 2^{N-1} subsets of \lbrace 1,2, \ldots, N-1 \rbrace , including the empty set, which can be S. Find the sum of f(S) over all these S, modulo 998244353.

Constraints

2 \leq N \leq 2 \times 10^5
X has N digits in decimal representation, none of which is 0.
All values in the input are integers.

Input

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

N
X

Output

Print the answer.

Sample Input 1

3
234

Sample Output 1

For S = \emptyset, we have f(S) = 234.
For S = \lbrace 1 \rbrace, we have f(S) = 2 \times 34 = 68.
For S = \lbrace 2 \rbrace, we have f(S) = 23 \times 4 = 92.
For S = \lbrace 1, 2 \rbrace, we have f(S) = 2 \times 3 \times 4 = 24.
Thus, you should print 234 + 68 + 92 + 24 = 418.

Sample Input 2

4
5915

Sample Output 2

Sample Input 3

9
998244353

Sample Output 3

258280134