A - 202<s>3</s>

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字と数字からなる文字列 S が入力されます。
S は 2023 で終わることが保証されます。
S の最後の文字を 4 に変更し、変更後の文字列を出力してください。

制約

  • S は英小文字と数字からなる長さ 4 以上 100 以下の文字列
  • S は 2023 で終わる。

入力

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

S

出力

答えを出力せよ。


入力例 1

hello2023

出力例 1

hello2024

hello2023 の最後の文字を 4 に変更すると、 hello2024 となります。


入力例 2

worldtourfinals2023

出力例 2

worldtourfinals2024

入力例 3

2023

出力例 3

2024

S が 2023 で終わることが保証されていますが、 S が 2023 そのものである場合もあります。


入力例 4

20232023

出力例 4

20232024

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters and digits.
S is guaranteed to end with 2023.
Change the last character of S to 4 and print the modified string.

Constraints

  • S is a string of length between 4 and 100, inclusive, consisting of lowercase English letters and digits.
  • S ends with 2023.

Input

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

S

Output

Print the answer.


Sample Input 1

hello2023

Sample Output 1

hello2024

Changing the last character of hello2023 to 4 yields hello2024.


Sample Input 2

worldtourfinals2023

Sample Output 2

worldtourfinals2024

Sample Input 3

2023

Sample Output 3

2024

S is guaranteed to end with 2023, possibly being 2023 itself.


Sample Input 4

20232023

Sample Output 4

20232024
B - Move Right

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

横一列に 4 つのマスが並んでいます。

各文字が 0 または 1 である長さ 4 の文字列 S が与えられます。
S の i 文字目が 1 であるとき、左から i 番目のマスには 1 人の人がおり、
S の i 文字目が 0 であるとき、左から i 番目のマスには人がいません。

全ての人が一斉に、1 つ右隣のマスへ移動します。この移動により、もともと右端のマスにいた人は消えます。

移動後の各マスに人がいるかどうかを、S と同様のルールで文字列として出力してください。

制約

  • S は 0, 1 のみからなる長さ 4 の文字列

入力

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

S

出力

長さ 4 の文字列であって、移動後、左から i 番目のマスに人がいるならば i 文字目が 1、いないならば 0 であるようなものを出力せよ。


入力例 1

1011

出力例 1

0101

移動により、左から 1 番目のマスにいた人は左から 2 番目のマスに、
左から 3 番目のマスにいた人は左から 4 番目のマスに移動し、
左から 4 番目のマス(右端のマス)にいた人は消えます。


入力例 2

0000

出力例 2

0000

入力例 3

1111

出力例 3

0111

Score : 100 points

Problem Statement

There are 4 squares lined up horizontally.

You are given a string S of length 4 consisting of 0 and 1.
If the i-th character of S is 1, there is a person in the i-th square from the left;
if the i-th character of S is 0, there is no person in the i-th square from the left.

Now, everyone will move to the next square to the right simultaneously. By this move, the person who was originally in the rightmost square will disappear.

Determine if there will be a person in each square after the move. Print the result as a string in the same format as S. (See also Sample Input / Output for clarity.)

Constraints

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

Input

Input is given from Standard Input in the following format:

S

Output

Print a string of length 4 such that the i-th character is 1 if there will be a person in the i-th square from the left after the move, and 0 otherwise.


Sample Input 1

1011

Sample Output 1

0101

After the move, the person who was originally in the 1-st square will move to the 2-nd square,
the person in the 3-rd square to the 4-th square,
and the person in the 4-th square will disappear.


Sample Input 2

0000

Sample Output 2

0000

Sample Input 3

1111

Sample Output 3

0111
C - Buy One Carton of Milk

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

スーパーマーケットで卵のパックが売られています。

卵 6 個入りのパックは S 円、卵 8 個入りのパックは M 円、卵 12 個入りのパックは L 円です。

どのパックも何パックでも購入できるとき、N 個以上の卵を買うために必要な最小の金額を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq S,M,L \leq 10^4
  • 入力は全て整数である

入力

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

N S M L

出力

答えを出力せよ。


入力例 1

16 120 150 200

出力例 1

300

8 個入りのパックを 2 個買うのが最適です。


入力例 2

10 100 50 10

出力例 2

10

12 個入りのパックを 1 個買うのが最適です。


入力例 3

99 600 800 1200

出力例 3

10000

8 個入りのパックと 12 個入りのパックを 5 個ずつ買うのが最適です。

Score : 200 points

Problem Statement

A supermarket sells egg packs.

A pack of 6 eggs costs S yen, a pack of 8 eggs costs M yen, and a pack of 12 eggs costs L yen.

When you can buy any number of each pack, find the minimum amount of money required to purchase at least N eggs.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq S,M,L \leq 10^4
  • All input values are integers.

Input

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

N S M L

Output

Print the answer.


Sample Input 1

16 120 150 200

Sample Output 1

300

It is optimal to buy two 8-egg packs.


Sample Input 2

10 100 50 10

Sample Output 2

10

It is optimal to buy one 12-egg pack.


Sample Input 3

99 600 800 1200

Sample Output 3

10000

It is optimal to buy five 8-egg packs and five 12-egg packs.

D - Vacation Together

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号がついた N 人の人がいます。
N 人の人の今後 D 日間の予定が与えられます。人 i の予定は長さ D の文字列 S_i で表されて、S_i の j 文字目が o ならば j 日目は暇であることを、x ならばそうでないことを意味します。

D 日間のうち全員が暇であるような 連続する 何日かを選ぶことを考えます。
選べる日数は最大で何日ですか?ただし、選べる日が存在しない場合は 0 日と答えてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq D \leq 100
  • N, D は整数
  • S_i は o と x からなる長さ D の文字列

入力

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

N D
S_1
S_2
\vdots
S_N

出力

選べる日数の最大値を出力せよ。選べる日が存在しない場合は 0 を出力せよ。


入力例 1

3 5
xooox
oooxx
oooxo

出力例 1

2

2 日目と 3 日目は全員が暇な日なので選ぶことができます。
この 2 日間を選ぶと、連続する日にちを選ぶ方法の中で日数を最大にすることができます。


入力例 2

3 3
oxo
oxo
oxo

出力例 2

1

選ぶ日にちは連続している必要があるのに注意してください。(1 日目と 3 日目は全員が暇な日なので選ぶことができますが、この 2 つを同時に選ぶことはできません)


入力例 3

3 3
oox
oxo
xoo

出力例 3

0

選べる日が存在しない場合は 0 を出力してください。


入力例 4

1 7
ooooooo

出力例 4

7

入力例 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

出力例 5

5

Score : 200 points

Problem Statement

There are N people numbered 1 to N.
You are given their schedule for the following D days. The schedule for person i is represented by a string S_i of length D. If the j-th character of S_i is o, person i is free on the j-th day; if it is x, they are occupied that day.

From these D days, consider choosing some consecutive days when all the people are free.
How many days can be chosen at most? If no day can be chosen, report 0.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq D \leq 100
  • N and D are integers.
  • S_i is a string of length D consisting of o and x.

Input

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

N D
S_1
S_2
\vdots
S_N

Output

Print the maximum number of days that can be chosen, or 0 if no day can be chosen.


Sample Input 1

3 5
xooox
oooxx
oooxo

Sample Output 1

2

All the people are free on the second and third days, so we can choose them.
Choosing these two days will maximize the number of days among all possible choices.


Sample Input 2

3 3
oxo
oxo
oxo

Sample Output 2

1

Note that the chosen days must be consecutive. (All the people are free on the first and third days, so we can choose either of them, but not both.)


Sample Input 3

3 3
oox
oxo
xoo

Sample Output 3

0

Print 0 if no day can be chosen.


Sample Input 4

1 7
ooooooo

Sample Output 4

7

Sample Input 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

Sample Output 5

5
E - K Swap

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の数列 A=(a_1,\ldots,a_N) があります。また、整数 K が与えられます。

あなたは次の操作を 0 回以上何度でも行えます。

  • 1 \leq i \leq N-K を満たす整数 i を選び、a_i と a_{i+K} の値を入れ替える。

A を昇順に並べ替えることが出来るかどうかを判定してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N-1
  • 1 \leq a_i \leq 10^9
  • 入力はすべて整数

入力

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

N K
a_1 \ldots a_N

出力

A を昇順に並び替えることが出来るならば Yes と、出来ないならば No と出力せよ。


入力例 1

5 2
3 4 1 3 4

出力例 1

Yes

次のように操作をすることで A を昇順に並び替えることが出来ます。

  • i=1 とし、a_1 と a_3 の値を入れ替える。数列は (1,4,3,3,4) となる。
  • i=2 とし、a_2 と a_4 の値を入れ替える。数列は (1,3,3,4,4) となる。

入力例 2

5 3
3 4 1 3 4

出力例 2

No

入力例 3

7 5
1 2 3 4 5 5 10

出力例 3

Yes

操作を行う必要が無い場合もあります。

Score : 300 points

Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

  • Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N-1
  • 1 \leq a_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
a_1 \ldots a_N

Output

If it is possible to sort A in ascending order, print Yes; otherwise, print No.


Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

  • Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
  • Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.

F - Coupon

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個の商品があります。i = 1, 2, \ldots, N について、i 番目の商品の値段は A_i 円です。

高橋君は K 枚のクーポンを持っています。
1 枚のクーポンは 1 つの商品に対して使用することができ、1 つの商品に対してはクーポンを何枚でも( 0 枚でもよい)使用することができます。 値段が a 円の商品に対して k 枚のクーポンを使用すると、その商品を \max\lbrace a - kX, 0\rbrace 円で買うことができます。

高橋君がすべての商品を買うために支払う合計金額の最小値を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K, X \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

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

N K X
A_1 A_2 \ldots A_N

出力

答えを出力せよ。


入力例 1

5 4 7
8 3 10 5 13

出力例 1

12

1 番目の商品に対してクーポン 1 枚、3 番目の商品に対してクーポン 1 枚、5 番目の商品に対してクーポン 2 枚を使用すると、

  • 1 番目の商品を \max\lbrace A_1-X, 0 \rbrace = 1 円で買うことができ、
  • 2 番目の商品を \max\lbrace A_2, 0 \rbrace = 3 円で買うことができ、
  • 3 番目の商品を \max\lbrace A_3-X, 0 \rbrace = 3 円で買うことができ、
  • 4 番目の商品を \max\lbrace A_4, 0 \rbrace = 5 円で買うことができ、
  • 5 番目の商品を \max\lbrace A_5-2X, 0 \rbrace = 0 円で買うことができます。

よって、すべての商品を 1 + 3 + 3 + 5 + 0 = 12 円で買うことができ、これが最小です。


入力例 2

5 100 7
8 3 10 5 13

出力例 2

0

入力例 3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

出力例 3

112

Score : 300 points

Problem Statement

There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).

Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.

Print the minimum amount of money Takahashi needs to buy all the items.

Constraints

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

Input

Input is given from Standard Input in the following format:

N K X
A_1 A_2 \ldots A_N

Output

Print the answer.


Sample Input 1

5 4 7
8 3 10 5 13

Sample Output 1

12

By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:

  • buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
  • buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
  • buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
  • buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
  • buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,

for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.


Sample Input 2

5 100 7
8 3 10 5 13

Sample Output 2

0

Sample Input 3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

Sample Output 3

112
G - Match or Not

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

英小文字と ? からなる文字列 S,T が与えられます。ここで、|S| \gt |T| が成り立ちます(文字列 X に対し、 |X| で X の長さを表します)。

また、|X|=|Y| を満たす文字列 X,Y は、次の条件を満たすとき及びそのときに限りマッチするといいます。

  • X,Y に含まれる ? をそれぞれ独立に好きな英小文字に置き換えることで X と Y を一致させることができる

x=0,1,\ldots,|T| に対して次の問題を解いてください。

  • S の先頭の x 文字と末尾の |T|-x 文字を順番を保ったまま連結することで得られる長さ |T| の文字列を S' とする。S' と T がマッチするならば Yes と、そうでなければ No と出力せよ。

制約

  • S,T は英小文字と ? からなる文字列
  • 1 \leq |T| \lt |S| \leq 3 \times 10^5

入力

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

S
T

出力

|T|+1 行出力せよ。
i 行目には x=i-1 に対する出力をせよ。


入力例 1

a?c
b?

出力例 1

Yes
No
No

x=0 の場合、S' は ?c となります。ここで、S' の 1 文字目の ? を b に、T の 2 文字目の ? を c に置き換えることで S' と T を一致させることができるため、S' と T はマッチします。このため、1 行目の出力は Yes です。
x=1,2 の場合は S' はそれぞれ ac、a? であり、T とマッチしません。このため、2,3 行目の出力は No です。


入力例 2

atcoder
?????

出力例 2

Yes
Yes
Yes
Yes
Yes
Yes

入力例 3

beginner
contest

出力例 3

No
No
No
No
No
No
No
No

Score : 400 points

Problem Statement

You are given strings S and T consisting of lowercase English letters and ?. Here, |S| \gt |T| holds (for a string X, |X| denotes the length of X).

Two strings X and Y such that |X|=|Y| is said to match if and only if:

  • one can make X equal Y by replacing each ? in X and Y with any English letter independently.

Solve the following problem for each x=0,1,\ldots,|T|:

  • Let S' be the string of length |T| obtained by concatenating the first x characters and the last (|T|-x) characters of S without changing the order. Print Yes if S' and T match, and No otherwise.

Constraints

  • S and T are strings consisting of lowercase English letters and ?.
  • 1 \leq |T| \lt |S| \leq 3 \times 10^5

Input

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

S
T

Output

Print (|T|+1) lines.
The i-th line should contain the answer for x=i-1.


Sample Input 1

a?c
b?

Sample Output 1

Yes
No
No

When x=0, S' equals ?c. Here, we can replace the 1-st character of S', ?, with b and the 2-nd character of T, ?, with c to make S' equal T, so S' and T match. Thus, Yes should be printed in the first line.
When x=1 and 2, respectively, S' is ac and a?, neither of which matches with T. Thus, No should be printed in the second and third lines.


Sample Input 2

atcoder
?????

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes

Sample Input 3

beginner
contest

Sample Output 3

No
No
No
No
No
No
No
No
H - Christmas Color Grid 1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

この問題は問題 G と似た設定です。問題文の相違点を赤字で示します。

H 行 W 列のグリッドがあり、グリッドの各マスは赤色あるいは緑色に塗られています。

グリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表記します。

マス (i,j) の色は文字 S_{i,j} で表され、S_{i,j} = . のときマス (i,j) は赤色、S_{i,j} = # のときマス (i,j) は緑色に塗られています。

グリッドにおいて、緑色に塗られたマスを頂点集合、隣り合った 2 つの緑色のマスを結ぶ辺全体を辺集合としたグラフにおける連結成分の個数を 緑の連結成分数 と呼びます。ただし、2 つのマス (x,y) と (x',y') が隣り合っているとは、|x-x'| + |y-y'| = 1 であることを指します。

赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えたとき、塗り替え後のグリッドの緑の連結成分数の期待値を \text{mod } 998244353 で出力してください。

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

制約

  • 1 \leq H,W \leq 1000
  • S_{i,j} = . または S_{i,j} = #
  • S_{i,j} = . なる (i,j) が存在する。

入力

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

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

出力

答えを出力せよ。


入力例 1

3 3
##.
#.#
#..

出力例 1

499122178

マス (1,3) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (2,2) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (3,2) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

マス (3,3) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

よって、赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えた後の緑の連結成分数の期待値は (1+1+2+2)/4 = 3/2 となります。


入力例 2

4 5
..#..
.###.
#####
..#..

出力例 2

598946613

入力例 3

3 4
#...
.#.#
..##

出力例 3

285212675

Score : 450 points

Problem Statement

This problem has a similar setting to Problem G. Differences in the problem statement are indicated in red.

There is a grid with H rows and W columns, where each cell is painted red or green.

Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

The color of cell (i,j) is represented by the character S_{i,j}, where S_{i,j} = . means cell (i,j) is red, and S_{i,j} = # means cell (i,j) is green.

The number of green connected components in the grid is the number of connected components in the graph with the vertex set being the green cells and the edge set being the edges connecting two adjacent green cells. Here, two cells (x,y) and (x',y') are considered adjacent when |x-x'| + |y-y'| = 1.

Consider choosing one red cell uniformly at random and repainting it green. Print the expected value of the number of green connected components in the grid after repainting, modulo 998244353.

What does "print the expected value modulo 998244353" mean? It can be proved that the sought expected value is always rational. Furthermore, the constraints of this problem guarantee that if that value is expressed as \frac{P}{Q} using two coprime integers P and Q, there is exactly one integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R < 998244353. Print this R.

Constraints

  • 1 \leq H,W \leq 1000
  • S_{i,j} = . or S_{i,j} = #.
  • There is at least one (i,j) such that S_{i,j} = ..

Input

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

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

Output

Print the answer.


Sample Input 1

3 3
##.
#.#
#..

Sample Output 1

499122178

If cell (1,3) is repainted green, the number of green connected components becomes 1.

If cell (2,2) is repainted green, the number of green connected components becomes 1.

If cell (3,2) is repainted green, the number of green connected components becomes 2.

If cell (3,3) is repainted green, the number of green connected components becomes 2.

Therefore, the expected value of the number of green connected components after choosing one red cell uniformly at random and repainting it green is (1+1+2+2)/4 = 3/2.


Sample Input 2

4 5
..#..
.###.
#####
..#..

Sample Output 2

598946613

Sample Input 3

3 4
#...
.#.#
..##

Sample Output 3

285212675
I - Two Strings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

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

文字列 X と整数 i に対し、f(X,i) を X に対して以下の操作を i 回行い得られる文字列とします。

  • X の先頭の文字を削除し、同じ文字を X の末尾に挿入する。

0 \le i,j \le N-1 を満たす正整数の組 (i,j) のうち、辞書順で f(S,i) が f(T,j) より小さいか同じであるものの個数を求めてください。

辞書順とは?

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

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

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

制約

  • 1 \le N \le 2 \times 10^5
  • S,T は英小文字からなる長さ N の文字列
  • N は整数

入力

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

N
S
T

出力

答えを出力せよ。


入力例 1

3
adb
cab

出力例 1

4

条件を満たす (i,j) の組は (0,0),(0,2),(2,0),(2,2) の 4 個があります。

(i,j)=(1,2) は、f(S,i)=dba,f(T,j)=bca であるため条件を満たしません。


入力例 2

10
wsiuhwijsl
pwqoketvun

出力例 2

56

Score : 500 points

Problem Statement

You are given strings S and T of length N each, consisting of lowercase English letters.

For a string X and an integer i, let f(X,i) be the string obtained by performing on X the following operation i times:

  • Remove the first character of X and append the same character to the end of X.

Find the number of integer pairs (i,j) satisfying 0 \le i,j \le N-1 such that f(S,i) is lexicographically smaller than or equal to f(T,j).

What is the lexicographical order?

Simply put, the lexicographical order is the order in which the words are arranged in a dictionary. Let us define it formally by describing an algorithm of finding the ordering of two distinct strings S and T consisting of lowercase English letters.

Here, we denote "the i-th character of a string S" by S_i. Also, we write S \lt T and S \gt T if S is lexicographically smaller and larger than T, respectively.

  1. Let L be the smallest of the lengths of S and T. For i=1,2,\dots,L, we check if S_i equals T_i.
  2. If there is an i such that S_i \neq T_i, let j be the smallest such i. Comparing S_j and T_j, we terminate the algorithm by determining that S \lt T if S_j is smaller than T_j in the alphabetical order, and that S \gt T otherwise.
  3. If there is no i such that S_i \neq T_i, comparing the lengths of S and T, we terminate the algorithm by determining that S \lt T if S is shorter than T, and that S \gt T otherwise.

Constraints

  • 1 \le N \le 2 \times 10^5
  • S and T are strings of length N each, consisting of lowercase English letters.
  • N is an integer.

Input

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

N
S
T

Output

Print the answer.


Sample Input 1

3
adb
cab

Sample Output 1

4

There are 4 pairs of (i, j) satisfying the conditions: (0,0),(0,2),(2,0), and (2,2).

(i,j)=(1,2) does not satisfy the conditions because f(S,i)=dba and f(T,j)=bca.


Sample Input 2

10
wsiuhwijsl
pwqoketvun

Sample Output 2

56