A - What month is it?

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

配点 : 100 点

問題文

1 以上 12 以下の整数 X,Y が与えられます。

X 月の Y ヶ月後が何月か求めてください。

制約

  • X,Y は 1 以上 12 以下の整数

入力

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

X Y

出力

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


入力例 1

5 9

出力例 1

2

5 月の 9 ヶ月後は 2 月です。したがって、 2 を出力してください。


入力例 2

1 1

出力例 2

2

入力例 3

12 12

出力例 3

12

Score : 100 points

Problem Statement

You are given integers X and Y between 1 and 12, inclusive.

Find what month it will be Y months after month X (for example, month 1 is January).

Constraints

  • X and Y are integers between 1 and 12, inclusive.

Input

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

X Y

Output

Output the answer as an integer.


Sample Input 1

5 9

Sample Output 1

2

Nine months after May is February. Therefore, output 2.


Sample Input 2

1 1

Sample Output 2

2

Sample Input 3

12 12

Sample Output 3

12
B - OS Versions

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

配点 : 100 点

問題文

ある OS のバージョンは古い順に "Ocelot", "Serval", "Lynx" です。
バージョン X がバージョン Y 以降のバージョンであるか判定してください。
なお、バージョン X 自身もバージョン X 以降のバージョンであるものとします。

制約

  • X,Y は "Ocelot", "Serval", "Lynx" のいずれか (引用符を含まない)

入力

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

X Y

出力

バージョン X がバージョン Y 以降のバージョンであれば Yes 、そうでなければ No と出力せよ。


入力例 1

Serval Ocelot

出力例 1

Yes

バージョン Serval はバージョン Ocelot 以降のバージョンです。そのため、 Yes と出力します。


入力例 2

Serval Lynx

出力例 2

No

バージョン Serval はバージョン Lynx 以降のバージョンではありません。そのため、 No と出力します。


入力例 3

Ocelot Ocelot

出力例 3

Yes

バージョン Ocelot 自身もバージョン Ocelot 以降のバージョンです。そのため、 Yes と出力します。

Score : 100 points

Problem Statement

The versions of a certain OS in chronological order are "Ocelot", "Serval", "Lynx".
Determine whether version X is the same as or newer than version Y.

Constraints

  • Each of X and Y is one of "Ocelot", "Serval", "Lynx" (without quotation marks).

Input

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

X Y

Output

If version X is the same as or newer than version Y, print Yes; otherwise, print No.


Sample Input 1

Serval Ocelot

Sample Output 1

Yes

Version Serval is the same as or newer than version Ocelot. Therefore, print Yes.


Sample Input 2

Serval Lynx

Sample Output 2

No

Version Serval is not the same as nor newer than version Lynx. Therefore, print No.


Sample Input 3

Ocelot Ocelot

Sample Output 3

Yes

Version Ocelot itself is the same as or newer than version Ocelot. Therefore, print Yes.

C - Substring 2

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

配点 : 200 点

問題文

整数 N,M と長さ N の数字列 S 、長さ M の数字列 T が与えられます。ここで、数字列とは 0 から 9 までの数字のみから構成される文字列のことを表します。

あなたは以下の操作を 0 回以上好きな回数行うことができます:

  • T から 1 文字選び、選んだ数字を 1 増やす。ただし、選んだ数字が 9 である場合は 0 にする。

T を S の部分文字列(連続する部分列)にするために必要な操作回数の最小値を求めてください。

制約

  • 1\le M\le N\le 100
  • N,M は整数
  • S は長さ N の数字列
  • T は長さ M の数字列

入力

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

N M
S
T

出力

T を S の部分文字列にするために必要な操作回数の最小値を出力せよ。


入力例 1

4 2
2025
91

出力例 1

2

以下のように 2 回操作することで T を S の部分文字列にすることができます。

  • T の 2 文字目に対して操作する。 T= 91 から T= 92 になる。
  • T の 1 文字目に対して操作する。 T= 92 から T= 02 になる。

02 は S の 2 文字目から 3 文字目までの部分文字列となっています。

2 回未満の操作で T を S の部分文字列にすることはできないため、 2 を出力してください。


入力例 2

3 2
438
38

出力例 2

0

はじめから 38 は 438 の部分文字列です。したがって、0 を出力してください。


入力例 3

5 5
00000
11111

出力例 3

45

入力例 4

8 3
20251227
438

出力例 4

13

Score : 200 points

Problem Statement

You are given integers N and M, a digit string S of length N, and a digit string T of length M. Here, a digit string is a string consisting of digits from 0 to 9.

You can perform the following operation zero or more times:

  • Choose one character from T and increase the chosen digit by 1. However, if the chosen digit is 9, change it to 0.

Find the minimum number of operations required to make T a substring (contiguous subsequence) of S.

Constraints

  • 1\le M\le N\le 100
  • N and M are integers.
  • S is a digit string of length N.
  • T is a digit string of length M.

Input

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

N M
S
T

Output

Output the minimum number of operations required to make T a substring of S.


Sample Input 1

4 2
2025
91

Sample Output 1

2

You can make T a substring of S with two operations as follows:

  • Perform the operation on the 2nd character of T. T= 91 becomes T= 92.
  • Perform the operation on the 1st character of T. T= 92 becomes T= 02.

02 is a substring from the 2nd character to the 3rd character of S.

It is impossible to make T a substring of S with less than two operations, so output 2.


Sample Input 2

3 2
438
38

Sample Output 2

0

38 is a substring of 438 from the beginning. Thus, output 0.


Sample Input 3

5 5
00000
11111

Sample Output 3

45

Sample Input 4

8 3
20251227
438

Sample Output 4

13
D - Line Sensor

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

配点 : 200 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
各マスの状態は文字 C_{i,j} で表されます。C_{i,j} が . ならば (i, j) には何も置かれておらず、 # ならば箱が 1 個置かれています。

1 \leq j \leq W を満たす整数 j に対して、整数 X_j を次のように定義します。

  • j 列目に置かれている箱の個数。言い換えると、C_{i,j} が # であるような整数 i の個数。

X_1, X_2, \dots, X_W をすべて求めてください。

制約

  • 1 \leq H \leq 1000
  • 1 \leq W \leq 1000
  • H, W は整数
  • C_{i, j} は . または #

入力

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

H W
C_{1,1}C_{1,2}\dots C_{1,W}
C_{2,1}C_{2,2}\dots C_{2,W}
\vdots
C_{H,1}C_{H,2}\dots C_{H,W}

出力

X_1, X_2, \dots, X_W を以下の形式に従って出力せよ。

X_1 X_2 \dots X_W

入力例 1

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

出力例 1

1 2 0 3

1 列目の箱が置かれているマスは (1, 1) の 1 ヵ所です。よって X_1 = 1 です。
2 列目の箱が置かれているマスは (2, 2), (3, 2) の 2 ヵ所です。よって X_2 = 2 です。
3 列目の箱が置かれているマスは存在しません。よって X_3 = 0 です。
4 列目の箱が置かれているマスは (1, 4), (2, 4), (3, 4) の 3 ヵ所です。よって X_4 = 3 です。
よって (X_1, X_2, X_3, X_4) = (1, 2, 0, 3) が答えとなります。


入力例 2

3 7
.......
.......
.......

出力例 2

0 0 0 0 0 0 0

箱が置かれているマスが存在しない場合もあります。


入力例 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

出力例 3

2 7 4

入力例 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

出力例 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3

Score : 200 points

Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.

For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.

  • X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is #.

Find all of X_1, X_2, \dots, X_W.

Constraints

  • 1 \leq H \leq 1000
  • 1 \leq W \leq 1000
  • H and W are integers.
  • C_{i, j} is . or #.

Input

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

H W
C_{1,1}C_{1,2}\dots C_{1,W}
C_{2,1}C_{2,2}\dots C_{2,W}
\vdots
C_{H,1}C_{H,2}\dots C_{H,W}

Output

Print X_1, X_2, \dots, X_W in the following format:

X_1 X_2 \dots X_W

Sample Input 1

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

Sample Output 1

1 2 0 3

In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).


Sample Input 2

3 7
.......
.......
.......

Sample Output 2

0 0 0 0 0 0 0

There may be no square that contains a box.


Sample Input 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

Sample Output 3

2 7 4

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3
E - RANDOM

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

配点 : 300 点

問題文

# と . からなる H 行 W 列の図形 S,T が与えられます。
図形 S は H 個の文字列として与えられ、 S_i の j 文字目は S の i 行 j 列にある要素を表します。 T についても同様です。

S の列を並べ替えて T と等しくできるか判定してください。

但し、図形 X の列を並べ替えるとは、以下の操作を言います。

  • (1,2,\dots,W) の順列 P=(P_1,P_2,\dots,P_W) をひとつ選択する。
  • その後、全ての 1 \le i \le H を満たす整数 i について、以下の操作を同時に行う。
    • 1 \le j \le W を満たす全ての整数 j について同時に、 X の i 行 j 列にある要素を i 行 P_j 列にある要素に置き換える。

制約

  • H,W は整数
  • 1 \le H,W
  • 1 \le H \times W \le 4 \times 10^5
  • S_i,T_i は # と . からなる長さ W の文字列

入力

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

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

出力

S を T と等しくできるなら Yes 、 そうでないなら No と出力せよ。


入力例 1

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

出力例 1

Yes

例えば S の 3,4,2,1 列目をこの順に左から並べ替えた場合、 S を T と等しくできます。


入力例 2

3 3
#.#
.#.
#.#
##.
##.
.#.

出力例 2

No

この入力では、 S を T と等しくすることができません。


入力例 3

2 1
#
.
#
.

出力例 3

Yes

S=T である場合もあります。


入力例 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

出力例 4

Yes

Score : 300 points

Problem Statement

You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.

Determine whether S can be made equal to T by rearranging the columns of S.

Here, rearranging the columns of a pattern X is done as follows.

  • Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
  • Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
    • For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.

Constraints

  • H and W are integers.
  • 1 \le H,W
  • 1 \le H \times W \le 4 \times 10^5
  • S_i and T_i are strings of length W consisting of # and ..

Input

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

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

Output

If S can be made equal to T, print Yes; otherwise, print No.


Sample Input 1

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

Sample Output 1

Yes

If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.


Sample Input 2

3 3
#.#
.#.
#.#
##.
##.
.#.

Sample Output 2

No

In this input, S cannot be made equal to T.


Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It is possible that S=T.


Sample Input 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Sample Output 4

Yes
F - Dash

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

配点 : 300 点

問題文

二次元平面の点 (0,0) に高橋君がいます。初め、高橋君の体力は H です。また、二次元平面には M 個の体力を回復するアイテムがあり、i 個目のアイテムは点 (x_i,y_i) に置いてあります。

高橋君は、これから N 回の移動をします。i 回目の移動は以下の方法で行われます。

  1. 今高橋君がいる点を (x,y) とする。体力を 1 消費し、S の i 番目の文字 S_i に応じて以下の点に移動する。

    • S_i が R のとき: (x+1,y)
    • S_i が L のとき: (x-1,y)
    • S_i が U のとき: (x,y+1)
    • S_i が D のとき: (x,y-1)
  2. 高橋君の体力が負になった場合、高橋君は倒れてしまい、移動をやめる。そうでない場合、移動した点にアイテムがあり、かつ高橋君の体力が K 未満ならば、移動した点に置かれたアイテムを消費し、高橋君の体力が K になる。

高橋君が一度も倒れることなく N 回の移動を行えるか判定してください。

制約

  • 1\leq N,M,H,K\leq 2\times 10^5
  • S は R, L, U, D からなる長さ N の文字列
  • |x_i|,|y_i| \leq 2\times 10^5
  • (x_i,y_i) は互いに異なる
  • S 以外の入力は全て整数

入力

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

N M H K
S
x_1 y_1
\vdots
x_M y_M

出力

高橋君が一度も倒れることなく N 回の移動を行える場合 Yes を、そうでない場合 No を出力せよ。


入力例 1

4 2 3 1
RUDL
-1 -1
1 0

出力例 1

Yes

初め高橋君の体力は 3 です。以下で移動を説明します。

  • 1 回目の移動: S_i が R なので点 (1,0) に移動する。高橋君の体力は 2 に減る。点 (1,0) にはアイテムが置いてあるが、高橋君の体力は K=1 以上なのでアイテムは消費されない。

  • 2 回目の移動: S_i が U なので点 (1,1) に移動する。高橋君の体力は 1 に減る。

  • 3 回目の移動: S_i が D なので点 (1,0) に移動する。高橋君の体力は 0 に減る。点 (1,0) にはアイテムが置いてあり、体力は K=1 未満なのでアイテムを消費し、体力が 1 になる。

  • 4 回目の移動: S_i が L なので点 (0,0) に移動する。高橋君の体力は 0 に減る。

以上より、高橋君は倒れずに 4 回の移動を行えるので、Yes を出力してください。体力は 0 になってもいいことに注意してください。


入力例 2

5 2 1 5
LDRLD
0 0
-1 -1

出力例 2

No

初め高橋君の体力は 1 です。以下で移動を説明します。

  • 1 回目の移動: S_i が L なので点 (-1,0) に移動する。高橋君の体力は 0 に減る。

  • 2 回目の移動: S_i が D なので点 (-1,-1) に移動する。高橋君の体力は -1 に減る。体力が -1 になってしまったので、高橋君は倒れてしまい、移動をやめる。

以上より、高橋君は倒れてしまうので、No を出力してください。

高橋君がはじめいる点 (0,0) にはアイテムが置いてありますが、移動後にアイテムは消費されるので、1 回目の移動前にアイテムを消費しないことに注意してください。

Score : 300 points

Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

  1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:

    • (x+1,y) if S_i is R;
    • (x-1,y) if S_i is L;
    • (x,y+1) if S_i is U;
    • (x,y-1) if S_i is D.
  2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

  • 1\leq N,M,H,K\leq 2\times 10^5
  • S is a string of length N consisting of R, L, U, and D.
  • |x_i|,|y_i| \leq 2\times 10^5
  • (x_i, y_i) are pairwise distinct.
  • All values in the input are integers, except for S.

Input

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

N M H K
S
x_1 y_1
\vdots
x_M y_M

Output

Print Yes if he can complete the N moves without being stunned; print No otherwise.


Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

  • 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

  • 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

  • 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

  • 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.


Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

  • 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

  • 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.

G - Synchronized Players

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

配点 : 400 点

問題文

N 行 N 列のグリッドがあり、各マスは空きマスか障害物のあるマスのいずれかです。グリッドの上から i 行目、左から j 列目のマスを (i, j) と表記します。

また、2 人のプレイヤーがグリッド上の相異なる空きマス上におり、各マスの情報は N 個の長さ N の文字列 S_1, S_2, \ldots, S_N として以下の形式で与えられます。

  • S_i の j 文字目が P であるとき、(i, j) は空きマスであり、プレイヤーがいる

  • S_i の j 文字目が . であるとき、(i, j) は空きマスであり、プレイヤーがいない

  • S_i の j 文字目が # であるとき、(i, j) は障害物のあるマスである

以下の操作を繰り返し 2 人のプレイヤーを同じマスに集めるために必要な操作回数の最小値を求めてください。ただし、操作の繰り返しにより 2 人のプレイヤーを同じマスに集めることができない場合には -1 を出力してください。

  • 上下左右のいずれかの方向を決める。そして各プレイヤーはともにその方向に隣接するマスへの移動を試みる。各プレイヤーは移動先のマスが存在し、かつ空きマスであるならば移動し、そうでないならば移動しない。

制約

  • N は 2 以上 60 以下の整数
  • S_i は長さ N の P, ., # からなる文字列
  • S_i の j 文字目が P であるような組 (i, j) の個数はちょうど 2 つ

入力

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

N
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。


入力例 1

5
....#
#..#.
.P...
..P..
....#

出力例 1

3

はじめに (3, 2) にいるプレイヤーをプレイヤー 1、(4, 3) にいるプレイヤーをプレイヤー 2 とします。

例えば以下のようにすることで、3 回の操作で 2 人のプレイヤーが同じマスに集まります。

  • 左を選択する。プレイヤー 1 は (3, 1) に移動し、プレイヤー 2 は (4, 2) に移動する。

  • 上を選択する。プレイヤー 1 は移動せず、プレイヤー 2 は (3, 2) に移動する。

  • 左を選択する。プレイヤー 1 は移動せず、プレイヤー 2 は (3, 1) に移動する。


入力例 2

2
P#
#P

出力例 2

-1

入力例 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

出力例 3

10

Score: 400 points

Problem Statement

There is an N \times N grid, where each cell is either empty or contains an obstacle. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

There are also two players on distinct empty cells of the grid. The information about each cell is given as N strings S_1, S_2, \ldots, S_N of length N, in the following format:

  • If the j-th character of S_i is P, then (i, j) is an empty cell with a player on it.

  • If the j-th character of S_i is ., then (i, j) is an empty cell without a player.

  • If the j-th character of S_i is #, then (i, j) contains an obstacle.

Find the minimum number of moves required to bring the two players to the same cell by repeating the following operation. If it is impossible to bring the two players to the same cell by repeating the operation, print -1.

  • Choose one of the four directions: up, down, left, or right. Then, each player attempts to move to the adjacent cell in that direction. Each player moves if the destination cell exists and is empty, and does not move otherwise.

Constraints

  • N is an integer between 2 and 60, inclusive.
  • S_i is a string of length N consisting of P, ., and #.
  • There are exactly two pairs (i, j) where the j-th character of S_i is P.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the answer.


Sample Input 1

5
....#
#..#.
.P...
..P..
....#

Sample Output 1

3

Let us call the player starting at (3, 2) Player 1 and the player starting at (4, 3) Player 2.

For example, doing the following brings the two players to the same cell in three moves:

  • Choose left. Player 1 moves to (3, 1), and Player 2 moves to (4, 2).

  • Choose up. Player 1 does not move, and Player 2 moves to (3, 2).

  • Choose left. Player 1 does not move, and Player 2 moves to (3, 1).


Sample Input 2

2
P#
#P

Sample Output 2

-1

Sample Input 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

Sample Output 3

10
H - LEQ

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

配点 : 500 点

問題文

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

A の連続するとは限らない、長さが 2 以上である部分列 A'=(A'_1,A'_2,\ldots,A'_k) のうち以下の条件を満たすものの個数を求めてください。

  • A'_1 \leq A'_k

なお、この値は非常に大きくなることがあるため、998244353 で割ったあまりを出力してください。

ただし、2 つの部分列は、列として同じであっても、取り出す添字が異なる場合は区別されます。

制約

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

入力

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

N
A_1 A_2 \ldots A_N

出力

A の連続するとは限らない、長さが 2 以上である部分列のうち問題文中の条件を満たすものの個数を、998244353 で割ったあまりを出力せよ。


入力例 1

3
1 2 1

出力例 1

3

A=(1,2,1) の連続するとは限らない、長さが 2 以上である部分列は (1,2), (1,1), (2,1), (1,2,1) の 4 通りあります。

そのうち問題文中の条件を満たすものは、(1,2), (1,1), (1,2,1) の 3 通りです。


入力例 2

3
1 2 2

出力例 2

4

列として同じであっても、取り出す添字が異なる場合 2 つの部分列は区別されることに注意してください。

この入出力例において、問題文中の条件を満たすような部分列は (1,2), (1,2), (2,2), (1,2,2) の 4 通りです。


入力例 3

3
3 2 1

出力例 3

0

問題文中の条件を満たすような部分列が存在しない場合もあります。


入力例 4

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

出力例 4

830

Score : 500 points

Problem Statement

Given is a sequence of N integers: A = (A_1, A_2, \dots, A_N).

Find the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the following condition:

  • A'_1 \leq A'_k.

Since the count can be enormous, print it modulo 998244353.

Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

Constraints

  • 2 \leq N \leq 3 \times 10^5
  • 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
A_1 A_2 \ldots A_N

Output

Print the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the condition in Problem Statement.


Sample Input 1

3
1 2 1

Sample Output 1

3

A=(1,2,1) has four (not necessarily contiguous) subsequences of length at least 2: (1,2), (1,1), (2,1), (1,2,1).

Three of them, (1,2), (1,1), (1,2,1), satisfy the condition in Problem Statement.


Sample Input 2

3
1 2 2

Sample Output 2

4

Note that two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.

In this Sample, there are four subsequences, (1,2), (1,2), (2,2), (1,2,2), that satisfy the condition.


Sample Input 3

3
3 2 1

Sample Output 3

0

There may be no subsequence that satisfies the condition.


Sample Input 4

10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

Sample Output 4

830
I - Concat (2nd)

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

配点 : 575 点

問題文

N 個の英小文字からなる文字列 S_1,S_2,\dots,S_N が与えられます。

(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) としてありえるもの全てについて、以下の通りに生成される文字列を書き並べます。

  • S_{P_1},S_{P_2},\dots,S_{P_N} をこの順に連結する。

書き並べられた N! 個の文字列を辞書順に並べた列を A_1,A_2,\dots,A_{N!} とします。
A_2 を出力してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \le T \le 1.5 \times 10^5
  • 2 \le N \le 3 \times 10^5
  • T,N は整数
  • S_i は英小文字からなる長さ 1 以上 10^6-1 以下の文字列
  • ひとつの入力について、 N の総和は 3 \times 10^5 を超えない
  • ひとつの入力について、全てのテストケースにおける |S_i| の総和は 10^6 を超えない

入力

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

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

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

N
S_1
S_2
\vdots
S_N

出力

T 行出力せよ。

i 行目には i 番目のテストケースについて、答えを出力せよ。


入力例 1

3
3
abc
ac
ahc
4
aaa
a
aaaa
a
15
ks
sy
k
ysk
yks
ky
ksy
sk
syk
s
kys
sky
ys
yk
y

出力例 1

abcahcac
aaaaaaaaa
kksksykykysskskyssyksyyksykyskyys

この入力には 3 個のテストケースが含まれています。

1 番目のテストケースについて、 S=( abc, ac, ahc ) です。
A=( abcacahc, abcahcac, acabcahc, acahcabc, ahcabcac, ahcacabc ) なので、 A_2= abcahcac を出力します。

Score : 575 points

Problem Statement

You are given N strings S_i consisting of lowercase English letters.

For all possible permutations P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N), write down the string generated as follows:

  • Concatenate S_{P_1},S_{P_2},\dots,S_{P_N} in this order.

Let A_1,A_2,\dots,A_{N!} be the sequence of the N! written strings sorted in lexicographical order.
Output A_2.

You are given T test cases; solve each of them.

Constraints

  • 1 \le T \le 1.5 \times 10^5
  • 2 \le N \le 3 \times 10^5
  • T,N are integers.
  • S_i is a string consisting of lowercase English letters with length between 1 and 10^6-1, inclusive.
  • For a single input, the sum of N does not exceed 3 \times 10^5.
  • For a single input, the sum of |S_i| does not exceed 10^6.

Input

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

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

Each test case is given in the following format:

N
S_1
S_2
\vdots
S_N

Output

Output T lines.

The i-th line should contain the answer for the i-th test case.


Sample Input 1

3
3
abc
ac
ahc
4
aaa
a
aaaa
a
15
ks
sy
k
ysk
yks
ky
ksy
sk
syk
s
kys
sky
ys
yk
y

Sample Output 1

abcahcac
aaaaaaaaa
kksksykykysskskyssyksyyksykyskyys

This input contains three test cases.

For the first test case, S=( abc, ac, ahc ).
We have A=( abcacahc, abcahcac, acabcahc, acahcabc, ahcabcac, ahcacabc ), so output A_2= abcahcac.