AtCoder Daily Training MEDIUM 2024/07/10 20:00start

C - ASCII Art

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

配点 : 200 点

問題文

0 以上 26 以下の整数からなる H 行 W 列の行列 A が与えられます。A の上から i 行目、左から j 列目の要素は A_{i,j} です。

H 個の長さ W の文字列 S_1, S_2, \dots, S_H を次の条件を満たすように定めます。

S_i の j 文字目は、 A_{i,j} が 0 ならばピリオド (.)、そうでなければ A_{i,j} 番目の大文字アルファベットである。

S_1, S_2, \dots, S_H を順に出力してください。

制約

1 \leq H \leq 100
1 \leq W \leq 100
0 \leq A_{i,j} \leq 26
入力される値はすべて整数

入力

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

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

出力

H 行出力せよ。i 行目には S_i を出力せよ。

入力例 1

2 3
0 1 2
0 0 3

出力例 1

.AB
..C

S_1 = .AB、S_2 = ..C です。この 2 つを順に出力します。

入力例 2

出力例 2

X..
.Y.
..Z

入力例 3

出力例 3

B
I
D

入力例 4

24 60
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0
0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0
0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0
0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0
0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0
0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例 4

................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................

Score : 200 points

Problem Statement

You are given an H-by-W matrix A consisting of integers between 0 and 26. The element at the i-th row from the top and j-th column from the left is A_{i,j}.

Let S_1, S_2, \dots, S_H be H strings of length W that satisfy the following.

The j-th character of S_i is a period (.) if A_{i,j} is 0, and the A_{i,j}-th uppercase English letter otherwise. (For instance, the 4-th letter is D.)

Print S_1, S_2, \dots, S_H in order.

Constraints

1 \leq H \leq 100
1 \leq W \leq 100
0 \leq A_{i,j} \leq 26
All values in the input are integers.

Input

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

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

Output

Print H lines. The i-th line should contain S_i.

Sample Input 1

2 3
0 1 2
0 0 3

Sample Output 1

.AB
..C

We have S_1 = .AB and S_2 = ..C. Print these in order.

Sample Input 2

Sample Output 2

X..
.Y.
..Z

Sample Input 3

Sample Output 3

B
I
D

Sample Input 4

24 60
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0
0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0
0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0
0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0
0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0
0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 4

................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................

D - Farthest Point

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

配点 : 200 点

問題文

xy 平面上に 1 から N までの番号が付いた N 個の点があります。点 i は座標 (X_i, Y_i) にあり、相異なる 2 点の座標は異なります。

各点について、その点からの距離が最大である点を求めてその点の番号を出力してください。ただし、距離が最大である点が複数ある場合はその中で最も番号が小さい点の番号を出力してください。

ここで、距離はユークリッド距離、すなわち 2 点 (x_1,y_1) と (x_2,y_2) に対し、この 2 点間の距離が \sqrt{(x_1-x_2)^{2}+(y_1-y_2)^{2}} であるものとして定められています。

制約

2 \leq N \leq 100
-1000 \leq X_i, Y_i \leq 1000
i \neq j ならば (X_i, Y_i) \neq (X_j, Y_j)
入力は全て整数である。

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

N 行出力せよ。i 行目には点 i からの距離が最大である点の番号を出力せよ。

入力例 1

出力例 1

以下の図のように点が並んでいます。ここで P_i は点 i を表します。点 1 からの距離が最大である点は点 3,4 で、その中で番号が小さいのは点 3 です。

点 2 からの距離が最大である点は点 3 です。

点 3 からの距離が最大である点は点 1,2 で、その中で番号が小さいのは点 1 です。

点 4 からの距離が最大である点は点 1 です。

入力例 2

出力例 2

Score: 200 points

Problem Statement

On the xy-plane, there are N points with ID numbers from 1 to N. Point i is located at coordinates (X_i, Y_i), and no two points have the same coordinates.

From each point, find the farthest point and print its ID number. If multiple points are the farthest, print the smallest of the ID numbers of those points.

Here, we use the Euclidean distance: for two points (x_1,y_1) and (x_2,y_2), the distance between them is \sqrt{(x_1-x_2)^{2}+(y_1-y_2)^{2}}.

Constraints

2 \leq N \leq 100
-1000 \leq X_i, Y_i \leq 1000
(X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
All input values are integers.

Input

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print N lines. The i-th line should contain the ID number of the farthest point from point i.

Sample Input 1

Sample Output 1

The following figure shows the arrangement of the points. Here, P_i represents point i. The farthest point from point 1 are points 3 and 4, and point 3 has the smaller ID number.

The farthest point from point 2 is point 3.

The farthest point from point 3 are points 1 and 2, and point 1 has the smaller ID number.

The farthest point from point 4 is point 1.

Sample Input 2

Sample Output 2

E - XX to XXX

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

配点 : 300 点

問題文

英小文字からなる 2 つの文字列 S, T が与えられます。次の操作を好きな回数（ 0 回でも良い）行うことで、S を T と一致させることができるかを判定してください。

S において同じ文字が 2 文字連続しているところの間に、その文字と同じ文字を 1 つ挿入する。すなわち、下記の 3 つの手順からなる操作を行う。

現在の S の長さを N とし、S = S_1S_2\ldots S_N とする。

1 以上 N-1 以下の整数 i であって、S_i = S_{i+1} を満たすものを 1 つ選択する。（ただし、そのような i が存在しない場合は、何もせずに手順 3.をスキップして操作を終了する。）

S の i 文字目と i+1 文字目の間に文字 S_i(= S_{i+1}) を 1 つ挿入する。その結果、S は長さ N+1 の文字列 S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N となる。

制約

S と T はそれぞれ英小文字からなる長さ 2 以上 2 \times 10^5 以下の文字列

入力

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

S
T

出力

S を T と一致させることができる場合は Yes を、そうでない場合は No を出力せよ。ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入力例 1

abbaac
abbbbaaac

出力例 1

Yes

下記の 3 回の操作によって、S = abbaac を T = abbbbaaac に一致させることができます。

まず、S の 2 文字目と 3 文字目の間に b を挿入する。その結果、S = abbbaac となる。
次に、再び S の 2 文字目と 3 文字目の間に b を挿入する。その結果、S = abbbbaac となる。
最後に、S の 6 文字目と 7 文字目の間に a を挿入する。その結果、S = abbbbaaac となる。

よって、Yes を出力します。

入力例 2

xyzz
xyyzz

出力例 2

No

どのように操作を行っても、 S = xyzz を T = xyyzz に一致させることはできません。よって、No を出力します。

Score : 300 points

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

Let N be the current length of S, and S = S_1S_2\ldots S_N.

Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)

Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S
T

Output

If it is possible to make S equal T, print Yes; otherwise, print No. Note that the judge is case-sensitive.

Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.

Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

F - Bingo 2

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

配点 : 300 点

問題文

縦 N 行、横 N 列のマス目があり、上から i 行目、左から j 列目のマスには整数 N\times (i-1)+j が書かれています。

今から T ターンにわたって相異なる整数が宣言されます。i ターン目には A_i が宣言され、A_i が書かれたマスに印をつけます。初めてビンゴを達成するのは何ターン目か求めてください。ただし、T ターンの中でビンゴを達成しない場合は -1 を出力してください。

ここで、ビンゴを達成するとは以下のいずれかのうち少なくとも一つ満たされることを言います。

マス目の横の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する
マス目の縦の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する
マス目の対角線の列であって、列に含まれる N 個のマスすべてに印がついているものが存在する

制約

2\leq N\leq 2\times 10^3
1\leq T\leq \min(N^2,2\times 10^5)
1\leq A_i\leq N^2
i\neq j ならば A_i\neq A_j
入力は全て整数

入力

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

N T
A_1 A_2 \ldots A_T

出力

T ターンの中でビンゴを達成するならば初めてビンゴを達成するターンを、そうでないならば -1 を出力せよ。

入力例 1

3 5
5 1 8 9 7

出力例 1

マス目の状態は以下のように変化します。初めてビンゴを達成するのは 4 ターン目です。

入力例 2

3 5
4 2 9 7 5

出力例 2

-1

5 ターンの中でビンゴを達成できないので -1 を出力してください。

入力例 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11

出力例 3

Score : 300 points

Problem Statement

There is an N \times N grid, where the cell at the i-th row from the top and the j-th column from the left contains the integer N \times (i-1) + j.

Over T turns, integers will be announced. On Turn i, the integer A_i is announced, and the cell containing A_i is marked. Determine the turn on which Bingo is achieved for the first time. If Bingo is not achieved within T turns, print -1.

Here, achieving Bingo means satisfying at least one of the following conditions:

There exists a row in which all N cells are marked.
There exists a column in which all N cells are marked.
There exists a diagonal line (from top-left to bottom-right or from top-right to bottom-left) in which all N cells are marked.

Constraints

2 \leq N \leq 2 \times 10^3
1 \leq T \leq \min(N^2, 2 \times 10^5)
1 \leq A_i \leq N^2
A_i \neq A_j if i \neq j.
All input values are integers.

Input

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

N T
A_1 A_2 \ldots A_T

Output

If Bingo is achieved within T turns, print the turn number on which Bingo is achieved for the first time; otherwise, print -1.

Sample Input 1

3 5
5 1 8 9 7

Sample Output 1

The state of the grid changes as follows. Bingo is achieved for the first time on Turn 4.

Sample Input 2

3 5
4 2 9 7 5

Sample Output 2

-1

Bingo is not achieved within five turns, so print -1.

Sample Input 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11

Sample Output 3

G - Square Pair

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

配点 : 400 点

問題文

長さ N の非負整数列 A=(A_1,\ldots,A_N) が与えられます。以下の条件を共に満たす整数組 (i,j) の個数を求めてください。

1\leq i < j\leq N
A_i A_j は平方数

ここで非負整数 a は、ある非負整数 d を用いて a=d^2 と表せる場合平方数と呼ばれます。

制約

入力は全て整数
2\leq N\leq 2\times 10^5
0\leq A_i\leq 2\times 10^5

入力

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

N
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

5
0 3 2 8 12

出力例 1

条件を満たす整数組は (i,j)=(1,2),(1,3),(1,4),(1,5),(2,5),(3,4) の 6 つです。

例えば、A_2A_5=36 であり 36 は平方数なので、(i,j)=(2,5) は条件を満たします。

入力例 2

8
2 2 4 6 3 100 100 25

出力例 2

Score: 400 points

Problem Statement

You are given a sequence of non-negative integers A=(A_1,\ldots,A_N) of length N. Find the number of pairs of integers (i,j) that satisfy both of the following conditions:

1\leq i < j\leq N
A_i A_j is a square number.

Here, a non-negative integer a is called a square number when it can be expressed as a=d^2 using some non-negative integer d.

Constraints

All inputs are integers.
2\leq N\leq 2\times 10^5
0\leq A_i\leq 2\times 10^5

Input

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

N
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

5
0 3 2 8 12

Sample Output 1

Six pairs of integers, (i,j)=(1,2),(1,3),(1,4),(1,5),(2,5),(3,4), satisfy the conditions.

For example, A_2A_5=36, and 36 is a square number, so the pair (i,j)=(2,5) satisfies the conditions.

Sample Input 2

8
2 2 4 6 3 100 100 25