AtCoder Daily Training ALL 2026/03/18 16:00start

A - Rearranging ABC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ 3 の英大文字からなる文字列 S が与えられます。

S の各文字を並び替えることで S を文字列 ABC と一致させることができるか判定してください。

制約

S は英大文字からなる長さ 3 の文字列

入力

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

出力

S の各文字を並び替えることで文字列 ABC と一致させることができるなら Yes を、そうでないなら No を出力せよ。

入力例 1

BAC

出力例 1

Yes

S の 1 文字目と S の 2 文字目を入れ替えることで ABC と一致させることができます。

入力例 2

AAC

出力例 2

No

どのように並び替えても S を ABC と一致させることはできません。

入力例 3

ABC

出力例 3

Yes

入力例 4

ARC

出力例 4

No

Score : 100 points

Problem Statement

You are given a string S of length 3 consisting of uppercase English letters.

Determine whether it is possible to rearrange the characters in S to make it match the string ABC.

Constraints

S is a string of length 3 consisting of uppercase English letters.

Input

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

Output

Print Yes if it is possible to rearrange the characters in S to make it match the string ABC, and No otherwise.

Sample Input 1

BAC

Sample Output 1

Yes

You can make S match ABC by swapping the first and second characters of S.

Sample Input 2

AAC

Sample Output 2

No

You cannot make S match ABC no matter how you rearrange the characters.

Sample Input 3

ABC

Sample Output 3

Yes

Sample Input 4

ARC

Sample Output 4

No

B - Adjacent Squares

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

縦 H 行、横 W 列のマス目があり、このうち上から i 個目、左から j 個目のマスを (i,j) と呼びます。
このとき、マス (R,C) に辺で隣接するマスの個数を求めてください。

ただし、ある 2 つのマス (a,b),(c,d) が辺で隣接するとは、 |a-c|+|b-d|=1 (|x| を x の絶対値とする) であることを言います。

制約

入力は全て整数
1 \le R \le H \le 10
1 \le C \le W \le 10

入力

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

H W
R C

出力

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

入力例 1

3 4
2 2

出力例 1

入出力例 1,2,3 に対する説明は、出力例 3 の下にまとめて示します。

入力例 2

3 4
1 3

出力例 2

入力例 3

3 4
3 4

出力例 3

H=3,W=4 のとき、マス目は以下のようになります。

入力例 1 について、マス (2,2) に隣接するマスは 4 つです。
入力例 2 について、マス (1,3) に隣接するマスは 3 つです。
入力例 3 について、マス (3,4) に隣接するマスは 2 つです。

入力例 4

1 10
1 5

出力例 4

入力例 5

8 1
8 1

出力例 5

入力例 6

1 1
1 1

出力例 6

Score : 100 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
Find the number of squares that share a side with Square (R, C).

Here, two squares (a,b) and (c,d) are said to share a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Constraints

All values in input are integers.
1 \le R \le H \le 10
1 \le C \le W \le 10

Input

Input is given from Standard Input in the following format:

H W
R C

Output

Print the answer as an integer.

Sample Input 1

3 4
2 2

Sample Output 1

We will describe Sample Inputs/Outputs 1,2, and 3 at once below Sample Output 3.

Sample Input 2

3 4
1 3

Sample Output 2

Sample Input 3

3 4
3 4

Sample Output 3

When H=3 and W=4, the grid looks as follows.

For Sample Input 1, there are 4 squares adjacent to Square (2,2).
For Sample Input 2, there are 3 squares adjacent to Square (1,3).
For Sample Input 3, there are 2 squares adjacent to Square (3,4).

Sample Input 4

1 10
1 5

Sample Output 4

Sample Input 5

8 1
8 1

Sample Output 5

Sample Input 6

1 1
1 1

Sample Output 6

C - Weak Password

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

4 桁の暗証番号 X_1X_2X_3X_4 が与えられます。番号は先頭の桁が 0 であることもあり得ます。暗証番号は以下のいずれかの条件をみたすとき弱い暗証番号と呼ばれます。

4 桁とも同じ数字である。
1\leq i\leq 3 をみたす任意の整数 i について、 X_{i+1} が、 X_i の次の数字である。ただし、 0\leq j\leq 8 について j の次の数字は j+1 であり、 9 の次の数字は 0 である。

与えられた暗証番号が弱い暗証番号ならば Weak を、そうでないならば Strong を出力してください。

制約

0 \leq X_1, X_2, X_3, X_4 \leq 9
X_1, X_2, X_3, X_4 は整数である。

入力

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

X_1X_2X_3X_4

出力

与えられた暗証番号が弱い暗証番号ならば Weak を、そうでないならば Strong を出力せよ。

入力例 1

出力例 1

Weak

4 桁ともすべて 7 であるため、 1 つめの条件をみたしており、弱い暗証番号です。

入力例 2

出力例 2

Strong

1 桁目と 2 桁目が異なっており、 3 桁目は 2 桁目の次の数字ではないため、どちらの条件もみたしていません。

入力例 3

出力例 3

Weak

9 の次の数字が 0 であることに注意してください。

Score : 200 points

Problem Statement

You are given a 4-digit PIN: X_1X_2X_3X_4, which may begin with a 0. The PIN is said to be weak when it satisfies one of the following conditions:

All of the four digits are the same.
For each integer i such that 1\leq i\leq 3, X_{i+1} follows X_i. Here, j+1 follows j for each 0\leq j\leq 8, and 0 follows 9.

If the given PIN is weak, print Weak; otherwise, print Strong.

Constraints

0 \leq X_1, X_2, X_3, X_4 \leq 9
X_1, X_2, X_3, and X_4 are integers.

Input

Input is given from Standard Input in the following format:

X_1X_2X_3X_4

Output

If the given PIN is weak, print Weak; otherwise, print Strong.

Sample Input 1

Sample Output 1

Weak

All four digits are 7, satisfying the first condition, so this PIN is weak.

Sample Input 2

Sample Output 2

Strong

The first and second digits differ, and the third digit does not follow the second digit, so neither condition is satisfied.

Sample Input 3

Sample Output 3

Weak

Note that 0 follows 9.

D - Hammer

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

数直線の原点に高橋君がいます。高橋君は座標 X にあるゴールに移動しようとしています。

座標 Y には壁があり、最初、高橋君は壁を超えて移動することができません。
座標 Z にあるハンマーを拾った後でなら、壁を破壊して通過できるようになります。

高橋君がゴールに到達することが可能か判定し、可能であれば移動距離の最小値を求めてください。

制約

-1000 \leq X,Y,Z \leq 1000
X,Y,Z は相異なり、いずれも 0 でない
入力に含まれる値は全て整数である

入力

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

X Y Z

出力

高橋君がゴールに到達することが可能であれば、移動距離の最小値を出力せよ。不可能であれば、かわりに -1 と出力せよ。

入力例 1

10 -10 1

出力例 1

高橋君はまっすぐゴールに向かうことができます。

入力例 2

20 10 -10

出力例 2

ゴールは壁の向こう側にあります。まずハンマーを拾い、壁を壊すことでゴールに到達することができます。

入力例 3

100 1 1000

出力例 3

-1

Score : 200 points

Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

-1000 \leq X,Y,Z \leq 1000
X, Y, and Z are distinct, and none of them is 0.
All values in the input are integers.

Input

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

X Y Z

Output

If Takahashi can reach the goal, print the minimum total distance he needs to travel to do so. If he cannot, print -1 instead.

Sample Input 1

10 -10 1

Sample Output 1

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

E - Neo-lexicographic Ordering

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

AtCoder 王国を治める高橋君は、英小文字のアルファベット順を変更することにしました。

新たなアルファベット順はa , b , \ldots, z を並べ替えて得られる文字列 X を用いて表されます。X の i \, (1 \leq i \leq 26) 文字目は、新たな順番において i 番目に小さい英小文字を表します。

AtCoder 王国には N 人の国民がおり、それぞれの国民の名前は S_1, S_2, \dots, S_N です。ここで、S_i \, (1 \leq i \leq N) は英小文字からなります。
これらの名前を、高橋君の定めたアルファベット順に基づく辞書順に従って並べ替えてください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 S, T の大小を判定するアルゴリズムを以下に説明します。

以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

S, T のうち長さが大きくない方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、S_j が T_j よりアルファベット順で小さい場合は S \lt T 、そうでない場合は S \gt T と決定して、アルゴリズムを終了します。
S_i \neq T_i である i が存在しない場合、S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

X は a , b , \ldots, z を並べ替えて得られる
2 \leq N \leq 50000
N は整数
1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)
S_i は英小文字からなる (1 \leq i \leq N)
S_i \neq S_j (1 \leq i \lt j \leq N)

入力

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

X
N
S_1
S_2
\vdots
S_N

出力

N 行出力せよ。i \, (1 \leq i \leq N) 行目には、高橋君の定めたアルファベット順に基づく辞書順に従って国民の名前を並べ替えたとき、i 番目に小さいものを出力すること。

入力例 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

出力例 1

bzz
bzy
abx
caa

高橋君が新たに設定したアルファベット順において、b は a より小さく、z は y より小さいです。そのため、国民の名前を辞書順に並べ替えると、小さい順に bzz , bzy , abx , caa となります。

入力例 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

出力例 2

b
a
ac
ab
abc

Score : 300 points

Problem Statement

Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.

The new alphabetical order is represented by a string X, which is a permutation of a, b, \ldots, z. The i-th character of X (1 \leq i \leq 26) would be the i-th smallest English lowercase letter in the new order.

The kingdom has N citizens, whose names are S_1, S_2, \dots, S_N, where each S_i (1 \leq i \leq N) consists of lowercase English letters.
Sort these names lexicographically according to the alphabetical order decided by Takahashi.

What is the lexicographical order?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.

Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Constraints

X is a permutation of a, b, \ldots, z.
2 \leq N \leq 50000
N is an integer.
1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)
S_i consists of lowercase English letters. (1 \leq i \leq N)
S_i \neq S_j (1 \leq i \lt j \leq N)

Input

Input is given from Standard Input in the following format:

X
N
S_1
S_2
\vdots
S_N

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the i-th smallest name when the citizens' names are sorted according to the alphabetical order decided by Takahashi.

Sample Input 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

Sample Output 1

bzz
bzy
abx
caa

In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.

Sample Input 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

Sample Output 2

b
a
ac
ab
abc

F - Ameba

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

あなたはアメーバの観察記録をつけました。

最初 1 匹のアメーバがおり、番号は 1 です。

観察記録は時系列順に N 個あり、i 番目の観察記録は「番号 A_i のアメーバが分裂して消滅し、新たに 2 匹のアメーバが生まれ、それらにそれぞれ 2i,2i+1 と番号をつけた」というものです。
このとき、アメーバ A_i をアメーバ 2i,2i+1 の親と呼びます。

各 k=1,\ldots,2N+1 について、アメーバ k から何代親を遡るとアメーバ 1 になるか求めてください。

制約

1 \leq N \leq 2\times 10^5
観察記録は矛盾していない。すなわち
- 1\leq A_i \leq 2i-1
- A_i は相異なる整数

入力

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

N
A_1 A_2 \ldots A_N

出力

2N+1 行出力せよ。k 行目にはアメーバ k から何代親を遡るとアメーバ 1 になるかを出力せよ。

入力例 1

2
1 2

出力例 1

アメーバ 1 からアメーバ 2,3 が生まれ、アメーバ 2 からアメーバ 4,5 が生まれました。

アメーバ 1 は 0 代遡るとアメーバ 1 になります。
アメーバ 2 は 1 代遡るとアメーバ 1 になります。
アメーバ 3 は 1 代遡るとアメーバ 1 になります。
アメーバ 4 は 1 代遡るとアメーバ 2 になり、2 代遡るとアメーバ 1 になります。
アメーバ 5 は 1 代遡るとアメーバ 2 になり、2 代遡るとアメーバ 1 になります。

入力例 2

4
1 3 5 2

出力例 2

Score : 300 points

Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered 1.

You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.

For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?

Constraints

1 \leq N \leq 2\times 10^5
The records are consistent. That is:
- 1\leq A_i \leq 2i-1.
- A_i are distinct integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print 2N+1 lines. The k-th line should contain the generation distance between amoeba 1 and amoeba k.

Sample Input 1

2
1 2

Sample Output 1

From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.

Amoeba 1 is zero generations away from amoeba 1.
Amoeba 2 is one generation away from amoeba 1.
Amoeba 3 is one generation away from amoeba 1.
Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.

Sample Input 2

4
1 3 5 2

Sample Output 2

G - Polynomial division

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 次多項式 A(x)=A_Nx^N+A_{N-1}x^{N-1}+\cdots +A_1x+A_0 と
M 次多項式 B(x)=B_Mx^M+B_{M-1}x^{M-1}+\cdots +B_1x+B_0 があります。
ここで、A(x), B(x) の各係数は絶対値が 100 以下の整数であり、最高次の係数は 0 ではありません。

また、それらの積を C(x)=A(x)B(x)=C_{N+M}x^{N+M}+C_{N+M-1}x^{N+M-1}+\cdots +C_1x+C_0 とします。

A_0,A_1,\ldots, A_N および C_0,C_1,\ldots, C_{N+M} が与えられるので、B_0,B_1,\ldots, B_M を求めてください。
ただし、与えられる入力に対して、条件をみたす B_0,B_1,\ldots, B_M がただ一つ存在することが保証されます。

制約

1 \leq N < 100
1 \leq M < 100
|A_i| \leq 100
|C_i| \leq 10^6
A_N \neq 0
C_{N+M} \neq 0
条件をみたす B_0,B_1,\ldots, B_M がただ一つ存在する。

入力

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

N M
A_0 A_1 \ldots A_{N-1} A_N
C_0 C_1 \ldots C_{N+M-1} C_{N+M}

出力

M+1 個の整数 B_0,B_1,\ldots, B_M を空白区切りで一行に出力せよ。

入力例 1

1 2
2 1
12 14 8 2

出力例 1

6 4 2

A(x)=x+2, B(x)=2x^2+4x+6 のとき、C(x)=A(x)B(x)=(x+2)(2x^2+4x+6)=2x^3+8x^2+14x+12 であるので、 B(x)=2x^2+4x+6 が条件をみたします。よって、B_0=6, B_1=4, B_2=2 をこの順に空白区切りで出力します。

入力例 2

1 1
100 1
10000 0 -1

出力例 2

100 -1

A(x)=x+100, C(x)=-x^2+10000 であり、B(x)=-x+100 が条件をみたします。よって、100, -1 をこの順に空白区切りで出力します。

Score : 400 points

Problem Statement

We have a polynomial of degree N, A(x)=A_Nx^N+A_{N-1}x^{N-1}+\cdots +A_1x+A_0,
and another of degree M, B(x)=B_Mx^M+B_{M-1}x^{M-1}+\cdots +B_1x+B_0.
Here, each coefficient of A(x) and B(x) is an integer whose absolute value is at most 100, and the leading coefficients are not 0.

Also, let the product of them be C(x)=A(x)B(x)=C_{N+M}x^{N+M}+C_{N+M-1}x^{N+M-1}+\cdots +C_1x+C_0.

Given A_0,A_1,\ldots, A_N and C_0,C_1,\ldots, C_{N+M}, find B_0,B_1,\ldots, B_M.
Here, the given inputs guarantee that there is a unique sequence B_0, B_1, \ldots, B_M that satisfies the given conditions.

Constraints

1 \leq N < 100
1 \leq M < 100
|A_i| \leq 100
|C_i| \leq 10^6
A_N \neq 0
C_{N+M} \neq 0
There is a unique sequence B_0, B_1, \ldots, B_M that satisfies the conditions given in the statement.

Input

Input is given from Standard Input in the following format:

N M
A_0 A_1 \ldots A_{N-1} A_N
C_0 C_1 \ldots C_{N+M-1} C_{N+M}

Output

Print the M+1 integers B_0,B_1,\ldots, B_M in one line, with spaces in between.

Sample Input 1

1 2
2 1
12 14 8 2

Sample Output 1

6 4 2

For A(x)=x+2 and B(x)=2x^2+4x+6, we have C(x)=A(x)B(x)=(x+2)(2x^2+4x+6)=2x^3+8x^2+14x+12, so B(x)=2x^2+4x+6 satisfies the given conditions. Thus, B_0=6, B_1=4, B_2=2 should be printed in this order, with spaces in between.

Sample Input 2

1 1
100 1
10000 0 -1

Sample Output 2

100 -1

We have A(x)=x+100, C(x)=-x^2+10000, for which B(x)=-x+100 satisfies the given conditions. Thus, 100, -1 should be printed in this order, with spaces in between.

H - Defect-free Squares

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

縦 H 行, 横 W 列のグリッドがあります。グリッドの上から i 行目, 左から j 列目のマスを (i, j) と呼びます。
グリッドの各マスは穴の空いたマスとそうでないマスのどちらかです。穴が空いたマスは (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N) のちょうど N マスです。

正整数の組 (i, j, n) が次の条件を満たすとき、(i, j) を左上隅, (i + n - 1, j + n - 1) を右下隅とする正方形領域を 穴のない正方形 と呼びます。

i + n - 1 \leq H
j + n - 1 \leq W
0 \leq k \leq n - 1, 0 \leq l \leq n - 1 を満たす全ての非負整数の組 (k, l) に対して、(i + k, j + l) は穴が空いていないマスである。

グリッド内に穴のない正方形は何個ありますか？

制約

1 \leq H, W \leq 3000
0 \leq N \leq \min(H \times W, 10^5)
1 \leq a_i \leq H
1 \leq b_i \leq W
(a_i, b_i) は互いに異なる
入力される値は全て整数

入力

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

H W N
a_1 b_1
a_2 b_2
\vdots
a_N b_N

出力

穴のない正方形の個数を出力せよ。

入力例 1

2 3 1
2 3

出力例 1

穴のない正方形は全部で 6 個あります。
それらを列挙すると次の通りです。このうちはじめの 5 個は n = 1 の場合であり、領域の左上隅のマスと右下隅のマスが一致します。

(1, 1) を左上隅かつ右下隅とする正方形領域
(1, 2) を左上隅かつ右下隅とする正方形領域
(1, 3) を左上隅かつ右下隅とする正方形領域
(2, 1) を左上隅かつ右下隅とする正方形領域
(2, 2) を左上隅かつ右下隅とする正方形領域
(1, 1) を左上隅, (2, 2) を右下隅とする正方形領域

入力例 2

出力例 2

穴のない正方形が存在しない場合もあります。

入力例 3

1 1 0

出力例 3

穴のない正方形がグリッド全体と一致する場合もあります。

入力例 4

3000 3000 0

出力例 4

9004500500

Score : 475 points

Problem Statement

There is 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 of the grid.
Each square of the grid is holed or not. There are exactly N holed squares: (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N).

When the triple of positive integers (i, j, n) satisfies the following condition, the square region whose top-left corner is (i, j) and whose bottom-right corner is (i + n - 1, j + n - 1) is called a holeless square.

i + n - 1 \leq H.
j + n - 1 \leq W.
For every pair of non-negative integers (k, l) such that 0 \leq k \leq n - 1, 0 \leq l \leq n - 1, square (i + k, j + l) is not holed.

How many holeless squares are in the grid?

Constraints

1 \leq H, W \leq 3000
0 \leq N \leq \min(H \times W, 10^5)
1 \leq a_i \leq H
1 \leq b_i \leq W
All (a_i, b_i) are pairwise different.
All input values are integers.

Input

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

H W N
a_1 b_1
a_2 b_2
\vdots
a_N b_N

Output

Print the number of holeless squares.

Sample Input 1

2 3 1
2 3

Sample Output 1

There are six holeless squares, listed below. For the first five, n = 1, and the top-left and bottom-right corners are the same square.

The square region whose top-left and bottom-right corners are (1, 1).
The square region whose top-left and bottom-right corners are (1, 2).
The square region whose top-left and bottom-right corners are (1, 3).
The square region whose top-left and bottom-right corners are (2, 1).
The square region whose top-left and bottom-right corners are (2, 2).
The square region whose top-left corner is (1, 1) and whose bottom-right corner is (2, 2).

Sample Input 2

Sample Output 2

There may be no holeless square.

Sample Input 3

1 1 0

Sample Output 3

The whole grid may be a holeless square.

Sample Input 4

3000 3000 0

Sample Output 4

9004500500

I - Problem where +s Separate Digits

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

1 から 9 までの数字のみで構成された文字列 S が与えられます。
この文字列 S から、以下の操作によって式 T を作ります。

はじめ、 T=S であるとする。
各要素が 1 以上 |S|-1 以下の整数である、値に重複のない集合 A を選ぶ。なお、 A が空集合であってもよい。
A の全ての要素 x について、 x の降順に以下の操作を行う。
- T の x 文字目と x+1 文字目の間に、 + を挿入する。

例えば、 S= 1234、 A= \lbrace 2,3 \rbrace であるとき、 T= 12+3+4 となります。

この操作によって得られる T としてあり得る全ての式に対して、式を計算したときの値の総和を 998244353 で割った余りを求めてください。

制約

1 \le |S| \le 2 \times 10^5
S は 1, 2, 3, 4, 5, 6, 7, 8, 9 のみからなる。

入力

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

出力

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

入力例 1

出力例 1

式 T としてあり得るものは 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34, 1+2+3+4 の 8 つです。
これらを計算した値の総和は 1736 です。

入力例 2

出力例 2

S の長さが 1 であることもあります。この場合、 A として指定可能なのは空集合のみです。

入力例 3

31415926535897932384626433832795

出力例 3

85607943

答えを 998244353 で割った余りを求めてください。

Score : 500 points

Problem Statement

Given is a string S consisting of digits from 1 through 9.
From this string S, let us make a formula T by the following operations.

Initially, let T=S.
Choose a (possibly empty) set A of different integers where each element is between 1 and |S|-1 (inclusive).
For each element x in descending order, do the following.
- Insert a + between the x-th and (x+1)-th characters of T.

For example, when S= 1234 and A= \lbrace 2,3 \rbrace, we will have T= 12+3+4.

Consider evaluating all possible formulae T obtained by these operations. Find the sum, modulo 998244353, of the evaluations.

Constraints

1 \le |S| \le 2 \times 10^5
S consists of 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

There are eight formulae that can be obtained as T: 1234, 123+4, 12+34, 12+3+4, 1+234, 1+23+4, 1+2+34, and 1+2+3+4.
The sum of the evaluations of these formulae is 1736.

Sample Input 2

Sample Output 2

S may have a length of 1, in which case the only possible choice for A is the empty set.

Sample Input 3

31415926535897932384626433832795

Sample Output 3

85607943

Be sure to find the sum modulo 998244353.