AtCoder Daily Training ALL 2025/08/21 16:30start

A - On and Off

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君は、毎日 S 時 0 分に部屋の電気をつけ、毎日 T 時 0 分に消します。
電気をつけている間に日付が変わることもあります。

X 時 30 分に部屋の電気がついているかどうか判定してください。

制約

0 \leq S, T, X \leq 23
S \neq T
入力は全て整数である。

入力

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

S T X

出力

X 時 30 分に部屋の電気がついているならば Yes と、そうでなければ No と出力せよ。

入力例 1

7 20 12

出力例 1

Yes

部屋の電気がついているのは 7 時 0 分から 20 時 0 分までの間です。12 時 30 分には電気がついているので、Yes と出力します。

入力例 2

20 7 12

出力例 2

No

部屋の電気がついているのは 0 時 0 分から 7 時 0 分までの間と、20 時 0 分から（次の日の）0 時 0 分までの間です。 12 時 30 分には電気がついていないので、No と出力します。

入力例 3

23 0 23

出力例 3

Yes

Score : 100 points

Problem Statement

Takahashi turns on the light of his room at S o'clock (on the 24-hour clock) every day and turns it off at T o'clock every day.
The date may change while the light is on.

Determine whether the light is on at 30 minutes past X o'clock.

Constraints

0 \leq S, T, X \leq 23
S \neq T
All values in input are integers.

Input

Input is given from Standard Input in the following format:

S T X

Output

If the light is on at 30 minutes past X o'clock, print Yes; otherwise, print No.

Sample Input 1

7 20 12

Sample Output 1

Yes

The light is on between 7 o'clock and 20 o'clock. At 30 minutes past 12 o'clock, it is on, so we print Yes.

Sample Input 2

20 7 12

Sample Output 2

No

The light is on between 0 o'clock and 7 o'clock, and between 20 o'clock and 0 o'clock (on the next day). At 30 minutes past 12 o'clock, it is off, so we print No.

Sample Input 3

23 0 23

Sample Output 3

Yes

B - Tomorrow

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder 国の暦では、1 年は 1 月から M 月までの M ヶ月からなり、どの月も 1 日から D 日までの D 日からなります。

AtCoder 国の暦で y 年 m 月 d 日の翌日は何年何月何日であるか求めてください。

制約

1000 \leq y \leq 9000
1 \leq m \leq M \leq 99
1 \leq d \leq D \leq 99
入力は全て整数である

入力

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

M D
y m d

出力

AtCoder 国の暦で y 年 m 月 d 日の翌日が y' 年 m' 月 d' 日であるとき、y',m',d' をこの順に空白区切りで出力せよ。

入力例 1

12 30
2023 12 30

出力例 1

2024 1 1

AtCoder 国の暦では 1 年は 12 ヶ月であり、どの月も 30 日からなります。よって、2023 年 12 月 30 日の翌日は 2024 年 1 月 1 日になります。

入力例 2

36 72
6789 23 45

出力例 2

6789 23 46

AtCoder 国の暦では 1 年は 36 ヶ月であり、どの月も 72 日からなります。よって、6789 年 23 月 45 日の翌日は 6789 年 23 月 46 日になります。

入力例 3

12 30
2012 6 20

出力例 3

2012 6 21

Score : 100 points

Problem Statement

In the calendar of AtCoder Kingdom, a year consists of M months from month 1 to month M, and each month consists of D days from day 1 to day D.

What day follows year y, month m, day d in this calendar?

Constraints

1000 \leq y \leq 9000
1 \leq m \leq M \leq 99
1 \leq d \leq D \leq 99
All input values are integers.

Input

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

M D
y m d

Output

If the day following year y, month m, day d in the calendar of AtCoder Kingdom is year y', month m', day d', print y', m', and d' in this order, separated by spaces.

Sample Input 1

12 30
2023 12 30

Sample Output 1

2024 1 1

In the calendar of the kingdom, a year consists of 12 months, and each month consists of 30 days. Thus, the day following year 2023, month 12, day 30 is year 2024, month 1, day 1.

Sample Input 2

36 72
6789 23 45

Sample Output 2

6789 23 46

In the calendar of the kingdom, one year consists of 36 months, and each month consists of 72 days. Thus, the day following year 6789, month 23, day 45 is year 6789, month 23, day 46.

Sample Input 3

12 30
2012 6 20

Sample Output 3

2012 6 21

C - Cutoff

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

以下の手順で行われる試験があります。

試験は 1 ラウンド目から N ラウンド目までの N ラウンドからなる。
各ラウンドに対し、 0 以上 100 以下の整数でスコアが与えられる。
N ラウンドのスコアのうち、最高スコアと最低スコアを除いた N-2 ラウンドのスコアの合計が最終結果となる。
- 厳密には、各ラウンドのスコアを昇順に並べた列を S=(S_1,S_2,\dots,S_N) としたとき、最終結果は S_2+S_3+\dots+S_{N-1} となる。

現在、試験のうち N-1 ラウンドが終了し、 i ラウンド目のスコアは A_i でした。
最終結果を X 以上とするために N ラウンド目に取るべきスコアの最小値を出力してください。
但し、 N ラウンド目にどのようなスコアを取っても最終結果が X 以上にならない場合、代わりに -1 と出力してください。
なお、 N ラウンド目に取りうるスコアは 0 以上 100 以下の整数であることに注意してください。

制約

入力は全て整数
3 \le N \le 100
0 \le X \le 100 \times (N-2)
0 \le A_i \le 100

入力

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

N X
A_1 A_2 \dots A_{N-1}

出力

答えを出力せよ。

入力例 1

5 180
40 60 80 50

出力例 1

4 ラウンド目までのスコアは 40,60,80,50 でした。
5 ラウンド目にスコア 70 を取ると、スコアを昇順に並べた列は S=(40,50,60,70,80) となり、最終結果は 50+60+70=180 となります。
なお、最終結果を 180 以上にするために取るべきスコアの最小値が 70 であることが示せます。

入力例 2

3 100
100 100

出力例 2

2 ラウンド目までのスコアは 100,100 でした。
3 ラウンド目にスコア 0 を取ると、スコアを昇順に並べた列は S=(0,100,100) となり、最終結果は 100 となります。
最大スコアである 100 が複数ありますが、そのうち 1 つしか除かれないことに注意してください。(最小スコアについても同様です)
なお、最終結果を 100 以上にするために取るべきスコアの最小値が 0 であることが示せます。

入力例 3

5 200
0 0 99 99

出力例 3

-1

4 ラウンド目までのスコアは 0,0,99,99 でした。
5 ラウンド目にどのようなスコアを取っても、最終結果を 200 以上にすることができないことが示せます。

入力例 4

10 480
59 98 88 54 70 24 8 94 46

出力例 4

Score : 200 points

Problem Statement

There is an exam structured as follows.

The exam consists of N rounds called round 1 to N.
In each round, you are given an integer score between 0 and 100, inclusive.
Your final grade is the sum of the N-2 of the scores earned in the rounds excluding the highest and lowest.
- Formally, let S=(S_1,S_2,\dots,S_N) be the sequence of the scores earned in the rounds sorted in ascending order, then the final grade is S_2+S_3+\dots+S_{N-1}.

Now, N-1 rounds of the exam have ended, and your score in round i was A_i.
Print the minimum score you must earn in round N for a final grade of X or higher.
If your final grade will never be X or higher no matter what score you earn in round N, print -1 instead.
Note that your score in round N can only be an integer between 0 and 100.

Constraints

All input values are integers.
3 \le N \le 100
0 \le X \le 100 \times (N-2)
0 \le A_i \le 100

Input

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

N X
A_1 A_2 \dots A_{N-1}

Output

Print the answer.

Sample Input 1

5 180
40 60 80 50

Sample Output 1

Your scores in the first four rounds were 40, 60, 80, and 50.
If you earn a score of 70 in round 5, the sequence of the scores sorted in ascending order will be S=(40,50,60,70,80), for a final grade of 50+60+70=180.
It can be shown that 70 is the minimum score you must earn for a final grade of 180 or higher.

Sample Input 2

3 100
100 100

Sample Output 2

Your scores in the first two rounds were 100 and 100.
If you earn a score of 0 in round 3, the sequence of the scores sorted in ascending order will be S=(0,100,100), for a final grade of 100.
Note that the highest score, 100, is earned multiple times, and only one of them is excluded. (The same goes for the lowest score.)
It can be shown that 0 is the minimum score you must earn for a final grade of 100 or higher.

Sample Input 3

5 200
0 0 99 99

Sample Output 3

-1

Your scores in the first four rounds were 0, 0, 99, and 99.
It can be shown that your final grade will never be 200 or higher no matter what score you earn in round 5.

Sample Input 4

10 480
59 98 88 54 70 24 8 94 46

Sample Output 4

D - Card Pile

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 0 の書かれたカードが 100 枚積み重なったカードの山があります。

Q 個のクエリを処理してください。それぞれのクエリは以下のいずれかです。

タイプ 1 : 整数 x の書かれたカードを 1 枚カードの山の一番上に積み重ねる。
タイプ 2 : カードの山の一番上のカードを取り除き、取り除いたカードに書かれている整数を出力する。ここで、本問題の制約下では必ず山にカードが存在する。

制約

1\le Q\le 100
1\le x\le 100
タイプ 2 のクエリが 1 つ以上存在する。
入力される値は全て整数

入力

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

i 番目のクエリ \text{query}_i では、まずクエリのタイプ c_i （1,2 のいずれか）が与えられる。 c_i=1 の場合はさらに整数 x が追加で与えられる。

すなわち、各クエリは以下に示す 2 つの形式のいずれかである。

1 x

出力

c_i=2 を満たすクエリの回数を q として、 q 行出力せよ。

j (1\le j\le q) 行目では j 番目のそのようなクエリに対する答えを出力せよ。

入力例 1

出力例 1

各クエリを処理した後の山は順に以下のようになります：

カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 0 であるため、 0 を出力する。
- カードの山は 0 の書かれたカードが 99 枚となる。
4 が書かれたカードを山の上に追加する。
- カードの山は上から順に 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
3 が書かれたカードを山の上に追加する。
- カードの山は上から順に 3 の書かれたカードが 1 枚、 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 3 であるため、 3 を出力する。
- カードの山は上から順に 4 の書かれたカードが 1 枚、 0 の書かれたカードが 99 枚となる。
カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 4 であるため、 4 を出力する。
- カードの山は 0 の書かれたカードが 99 枚となる。
カードの山の一番上のカードを取り除く。取り除いたカードに書かれた整数は 0 であるため、 0 を出力する。
- カードの山は 0 の書かれたカードが 98 枚となる。

入力例 2

出力例 2

Score : 200 points

Problem Statement

There is a stack of 100 cards, each labeled with the integer 0.

Process Q queries. Each query is of one of the following:

Type 1: Place a card labeled with an integer x on top of the stack.
Type 2: Remove the top card of the stack and output the integer written on that removed card. Under the constraints of this problem, the stack always has at least one card.

Constraints

1 \le Q \le 100
1 \le x \le 100
There is at least one query of type 2.
All input values are integers.

Input

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

The i-th query \text{query}_i starts with the query type c_i (1 or 2), followed by the integer x if c_i=1.

That is, each query is in one of the following two formats:

1 x

Output

Let q be the number of queries with c_i=2. Print q lines.

The j-th line (1 \le j \le q) should contain the answer to the j-th such query.

Sample Input 1

Sample Output 1

After processing each query, the stack is as follows:

Remove the top card of the stack. The integer on the removed card is 0, so output 0.
- The stack then has 99 cards labeled with 0.
Add a card labeled 4 on top.
- The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
Add a card labeled 3 on top.
- The stack then has 1 card labeled 3, 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
Remove the top card. The integer on that card is 3, so output 3.
- The stack then has 1 card labeled 4, and 99 cards labeled 0, from top to bottom.
Remove the top card. The integer on that card is 4, so output 4.
- The stack then has 99 cards labeled 0.
Remove the top card. The integer on that card is 0, so output 0.
- The stack then has 98 cards labeled 0.

Sample Input 2

Sample Output 2

E - Inverse of Permutation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1,2,\dots,N が 1 回ずつ現れる長さ N の数列を「長さ N の順列」と呼びます。
長さ N の順列 P = (p_1, p_2,\dots,p_N) が与えられるので、以下の条件を満たす長さ N の順列 Q = (q_1,\dots,q_N) を出力してください。

全ての i (1 \leq i \leq N) に対して Q の p_i 番目の要素が i である。

ただし、条件を満たす Q は必ずただ 1 つ存在することが証明できます。

制約

1 \leq N \leq 2 \times 10^5
(p_1,p_2,\dots,p_N) は長さ N の順列である。
入力は全て整数である。

入力

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

N
p_1 p_2 \dots p_N

出力

数列 Q を空白区切りで 1 行で出力せよ。

q_1 q_2 \dots q_N

入力例 1

3
2 3 1

出力例 1

3 1 2

以下に説明する通り、 Q=(3,1,2) は条件を満たす順列です。

i = 1 のとき p_i = 2, q_2 = 1
i = 2 のとき p_i = 3, q_3 = 2
i = 3 のとき p_i = 1, q_1 = 3

入力例 2

3
1 2 3

出力例 2

1 2 3

全ての i (1 \leq i \leq N) に対して p_i = i が成り立つときは P = Q になります。

入力例 3

5
5 3 2 4 1

出力例 3

5 3 2 4 1

Score : 300 points

Problem Statement

We will call a sequence of length N where each of 1,2,\dots,N occurs once as a permutation of length N.
Given a permutation of length N, P = (p_1, p_2,\dots,p_N), print a permutation of length N, Q = (q_1,\dots,q_N), that satisfies the following condition.

For every i (1 \leq i \leq N), the p_i-th element of Q is i.

It can be proved that there exists a unique Q that satisfies the condition.

Constraints

1 \leq N \leq 2 \times 10^5
(p_1,p_2,\dots,p_N) is a permutation of length N (defined in Problem Statement).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 \dots p_N

Output

Print the sequence Q in one line, with spaces in between.

q_1 q_2 \dots q_N

Sample Input 1

3
2 3 1

Sample Output 1

3 1 2

The permutation Q=(3,1,2) satisfies the condition, as follows.

For i = 1, we have p_i = 2, q_2 = 1.
For i = 2, we have p_i = 3, q_3 = 2.
For i = 3, we have p_i = 1, q_1 = 3.

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3

If p_i = i for every i (1 \leq i \leq N), we will have P = Q.

Sample Input 3

5
5 3 2 4 1

Sample Output 3

5 3 2 4 1

F - Index × A(Continuous ver.)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

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

長さ M の A の連続部分列 B=(B_1,B_2,\dots,B_M) に対する、\displaystyle \sum_{i=1}^{M} i \times B_i の最大値を求めてください。

注記

数列の連続部分列とは、数列の先頭から 0 個以上、末尾から 0 個以上の要素を削除して得られる列のことをいいます。

例えば (2, 3) や (1, 2, 3) は (1, 2, 3, 4) の連続部分列ですが、(1, 3) や (3,2,1) は (1, 2, 3, 4) の連続部分列ではありません。

制約

1 \le M \le N \le 2 \times 10^5
- 2 \times 10^5 \le A_i \le 2 \times 10^5
入力は全て整数。

入力

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

N M
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4 2
5 4 -1 8

出力例 1

B=(A_3,A_4) とした場合、\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15 となります。16 以上の値を達成することはできないため、解は 15 です。

B=(A_1,A_4) などを選ぶことができないことに注意してください。

入力例 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

出力例 2

Score : 300 points

Problem Statement

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

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.

Notes

A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.

For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).

Constraints

1 \le M \le N \le 2 \times 10^5
- 2 \times 10^5 \le A_i \le 2 \times 10^5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.

Note that you are not allowed to choose, for instance, B=(A_1,A_4).

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

G - Square Permutation

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

数字のみからなる、長さ N の文字列 S が与えられます。

S を並べ替えてできる文字列を十進法の整数として解釈したもののうち、平方数であるようなものがいくつあるか求めてください。

より厳密には、次のようになります。

S の先頭から i 番目 (1\leq i\leq N) の数字に対応する数を s _ i とします。

(1, \ldots, N) の順列 P=(p _ 1,p _ 2,\ldots,p _ N) によって \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} と書ける整数のうち、平方数であるようなものがいくつあるか求めてください。

制約

1\leq N\leq 13
S は数字のみからなる長さ N の文字列
N は整数

入力

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

N
S

出力

答えを 1 行で出力せよ。

入力例 1

4
4320

出力例 1

P=(4,2,3,1) とすると、s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2 となります。
P=(3,2,4,1) とすると、s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2 となります。

これら以外の並べ替え方では平方数にならないため、2 を出力してください。

入力例 2

3
010

出力例 2

P=(1,3,2) もしくは P=(3,1,2) とすると、\displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2 となります。
P=(2,1,3) もしくは P=(2,3,1) とすると、\displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2 となります。

これら以外の並べ替え方では平方数にならないため、2 を出力してください。異なる並べ替え方でも、並べ替えた結果の数が同じなら 1 つと数えることに注意してください。

入力例 3

13
8694027811503

出力例 3

Score : 425 points

Problem Statement

You are given a string S of length N consisting of digits.

Find the number of square numbers that can be obtained by interpreting a permutation of S as a decimal integer.

More formally, solve the following.

Let s _ i be the number corresponding to the i-th digit (1\leq i\leq N) from the beginning of S.

Find the number of square numbers that can be represented as \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} with a permutation P=(p _ 1,p _ 2,\ldots,p _ N) of (1, \dots, N).

Constraints

1\leq N\leq 13
S is a string of length N consisting of digits.
N is an integer.

Input

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

N
S

Output

Print the answer in a single line.

Sample Input 1

4
4320

Sample Output 1

For P=(4,2,3,1), we have s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2.
For P=(3,2,4,1), we have s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2.

No other permutations result in square numbers, so you should print 2.

Sample Input 2

3
010

Sample Output 2

For P=(1,3,2) or P=(3,1,2), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2.
For P=(2,1,3) or P=(2,3,1), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2.

No other permutations result in square numbers, so you should print 2. Note that different permutations are not distinguished if they result in the same number.

Sample Input 3

13
8694027811503

Sample Output 3

H - Random Swaps of Balls

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N - 1 個の白いボールと 1 個の黒いボールがあります。これらの N 個のボールが横一列に並んでおり、はじめ黒いボールが最も左にあります。

高橋くんは、これから以下の操作をちょうど K 回行います。

1 以上 N 以下の整数を一様ランダムに選ぶ試行を 2 回行う。選んだ整数をそれぞれ a, b とする。さらに、 a \neq b であれば左から a 番目のボールと b 番目のボールを交換する。

K 回の操作のあと黒いボールがある位置を左から x 番目とします。x の期待値を \text{mod} \ 998244353 で求めてください。

期待値 \text{mod} \ 998244353 とは

求める期待値は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。この R を答えてください。

制約

1 \leq N \leq 998244352
1 \leq K \leq 10^5

入力

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

N K

出力

答えを 1 行に出力せよ。

入力例 1

2 1

出力例 1

499122178

1 回の操作が終わった後、黒いボールが左から 1 番目にある確率、 2 番目にある確率はそれぞれ \displaystyle \frac{1}{2} です。よって期待値は \displaystyle \frac{3}{2} です。

入力例 2

3 2

出力例 2

554580198

入力例 3

4 4

出力例 3

592707587

Score : 450 points

Problem Statement

There are N - 1 white balls and one black ball. These N balls are arranged in a row, with the black ball initially at the leftmost position.

Takahashi will perform the following operation exactly K times.

Choose an integer uniformly at random between 1 and N, inclusive, twice. Let a and b the chosen integers. If a \neq b, swap the a-th and b-th balls from the left.

After K operations, let the black ball be at the x-th position from the left. Find the expected value of x, modulo 998244353.

What is expected value modulo 998244353?

It can be proved that the sought expected value will always be rational. Additionally, under the constraints of this problem, it can be proved that if this value is expressed as an irreducible fraction \frac{P}{Q}, then Q \not \equiv 0 \pmod{998244353}. Therefore, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Report this R.

Constraints

1 \leq N \leq 998244352
1 \leq K \leq 10^5

Input

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

N K

Output

Print the answer in one line.

Sample Input 1

2 1

Sample Output 1

499122178

After one operation, the probabilities that the black ball is at the 1st position and the 2nd position from the left are both \displaystyle \frac{1}{2}. Thus, the expected value is \displaystyle \frac{3}{2}.

Sample Input 2

3 2

Sample Output 2

554580198

Sample Input 3

4 4

Sample Output 3

592707587

I - Operate K

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

この問題は C 問題 (Operate 1) を完全に含んでおり、 K \le 20 です。
この問題に正解するコードを C 問題に提出することで、 C 問題に正解できます。

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

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

制約

S,T は英小文字からなる長さ 1 以上 500000 以下の文字列
K は \color{red}{1 \le K \le 20} を満たす整数

入力

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

K
S
T

出力

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

入力例 1

3
abc
awtf

出力例 1

Yes

例えば、次のように操作することで、 3 回の操作で abc を awtf に変換できます。

2 文字目の b を w に変更する。操作後の文字列は awc となる。
3 文字目の c を f に変更する。操作後の文字列は awf となる。
2 文字目と 3 文字目の間に t を挿入する。操作後の文字列は awtf となる。

入力例 2

2
abc
awtf

出力例 2

No

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

入力例 3

17
twothousandtwentyfour
happynewyear

出力例 3

Yes

Score : 525 points

Problem Statement

This problem fully contains Problem C (Operate 1), with K \le 20.
You can solve Problem C by submitting a correct solution to this problem for Problem C.

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.
K is an integer satisfying \color{red}{1 \le K \le 20}.

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

3
abc
awtf

Sample Output 1

Yes

For example, here is a way to convert abc to awtf with three operations:

Replace the second character b with w. After the operation, the string becomes awc.
Replace the third character c with f. After the operation, the string becomes awf.
Insert t between the second and third characters. After the operation, the string becomes awtf.

Sample Input 2

2
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf with two or fewer operations.

Sample Input 3

17
twothousandtwentyfour
happynewyear

Sample Output 3

Yes