AtCoder Beginner Contest 445

A - Strong Word

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

配点 : 100 点

問題文

英小文字からなる 2 文字以上の文字列 S が与えられます。

S の先頭の文字と末尾の文字が同じ文字かどうか判定してください。

制約

S は英小文字からなる長さ 2 以上 10 以下の文字列

入力

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

出力

S の先頭の文字と末尾の文字が同じ文字ならば Yes を、異なる文字ならば No を出力せよ。

入力例 1

luminol

出力例 1

Yes

先頭の文字は l、末尾の文字は l で一致しています。したがって Yes を出力してください。

入力例 2

rule

出力例 2

No

先頭の文字は r、末尾の文字は e で一致していません。したがって No を出力してください。

Score : 100 points

Problem Statement

You are given a string S of length at least 2 consisting of lowercase English letters.

Determine whether the first character and the last character of S are the same.

Constraints

S is a string of length between 2 and 10, inclusive, consisting of lowercase English letters.

Input

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

Output

If the first character and the last character of S are the same, output Yes; otherwise, output No.

Sample Input 1

luminol

Sample Output 1

Yes

The first character is l and the last character is l, which match. Thus, output Yes.

Sample Input 2

rule

Sample Output 2

No

The first character is r and the last character is e, which do not match. Thus, output No.

B - Center Alignment

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

配点 : 200 点

問題文

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

S_1,S_2,\dots,S_N のうち最も長いものの長さを m とします。以下の条件を満たす文字列 T_1,T_2,\dots,T_N を求めてください。

条件：T_i はある非負整数 k について k 個の .、S_i、k 個の . をこの順に結合してできる、長さ m の文字列である。

制約

N は 1 以上 100 以下の整数
S_i は英小文字からなる長さ 1 以上 99 以下の奇数長の文字列

入力

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

N
S_1
S_2
\vdots
S_N

出力

N 行出力せよ。i\ (1 \leq i \leq N) 行目には T_i を出力せよ。

入力例 1

4
apple
blueberry
coconut
dragonfruit

出力例 1

...apple...
.blueberry.
..coconut..
dragonfruit

m=11 であり、T_1,T_2,T_3,T_4 はそれぞれ k=3,1,2,0 について問題文中の条件を満たしています。

入力例 2

6
abc
d
efghi
jkl
mnopq
r

出力例 2

.abc.
..d..
efghi
.jkl.
mnopq
..r..

Score : 200 points

Problem Statement

You are given N strings S_1,S_2,\dots,S_N of odd lengths consisting of lowercase English letters.

Let m be the length of the longest string among S_1,S_2,\dots,S_N. Find strings T_1,T_2,\dots,T_N satisfying the following condition.

Condition: T_i is a string of length m formed by concatenating k copies of ., S_i, and k copies of . in this order, for some non-negative integer k.

Constraints

N is an integer between 1 and 100, inclusive.
S_i is a string of odd length between 1 and 99, inclusive, consisting of lowercase English letters.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Output N lines. The i-th line (1 \leq i \leq N) should contain T_i.

Sample Input 1

4
apple
blueberry
coconut
dragonfruit

Sample Output 1

...apple...
.blueberry.
..coconut..
dragonfruit

m=11, and T_1,T_2,T_3,T_4 satisfy the condition in the problem statement for k=3,1,2,0, respectively.

Sample Input 2

6
abc
d
efghi
jkl
mnopq
r

Sample Output 2

.abc.
..d..
efghi
.jkl.
mnopq
..r..

C - Sugoroku Destination

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

配点 : 300 点

問題文

マス 1, マス 2,\ldots, マス N の N 個のマスが 1 列に並んでいます。マス i には整数 A _ i (i\le A_ i\le N) が書かれています。

s=1,2,\ldots,N のそれぞれについて、以下の問題を解いてください。

はじめ、マス s に駒を置く。「駒が置かれているマスに書かれている整数を x として、駒をマス x に移動させる」という操作を 10 ^ {100} 回行った後、駒が置かれているマスの番号を出力する。

制約

1\le N\le5\times10 ^ 5
i\le A _ i\le N\ (1\le i\le N)
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N

出力

s=1,2,\ldots,N に対する答えを、この順に空白を区切りとして一行に出力せよ。

入力例 1

7
2 4 7 5 5 6 7

出力例 1

5 5 7 5 5 6 7

s=1 のとき、駒は以下の図のように移動します。

駒がマス 5 に置かれているとき、操作が行われても駒は移動しないため、s=1 のときの答えは 5 となります。

入力例 2

5
1 2 3 4 5

出力例 2

1 2 3 4 5

駒が一度も移動しないこともあります。

入力例 3

15
11 3 10 7 15 10 10 11 11 13 11 12 14 14 15

出力例 3

11 14 14 14 15 14 14 11 11 14 11 12 14 14 15

Score : 300 points

Problem Statement

There are N cells, cell 1, cell 2,\ldots, cell N, arranged in a line. Cell i has an integer A_i\ (i \le A_i \le N) written on it.

For each of s=1,2,\ldots,N, solve the following problem.

Initially, place a piece on cell s. After performing the operation "let x be the integer written on the cell where the piece is placed, and then move the piece to cell x" 10^{100} times, output the number of the cell where the piece is placed.

Constraints

1 \le N \le 5\times10^5
i \le A_i \le N\ (1 \le i \le N)
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Output the answers for s=1,2,\ldots,N in this order on a single line, separated by spaces.

Sample Input 1

7
2 4 7 5 5 6 7

Sample Output 1

5 5 7 5 5 6 7

For s=1, the piece moves as shown in the following figure.

When the piece is placed on cell 5, the operation does not move the piece, so the answer for s=1 is 5.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1 2 3 4 5

It is possible that the piece never moves.

Sample Input 3

15
11 3 10 7 15 10 10 11 11 13 11 12 14 14 15

Sample Output 3

11 14 14 14 15 14 14 11 11 14 11 12 14 14 15

D - Reconstruct Chocolate

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

配点 : 425 点

問題文

N 個の板チョコのピースが机の上に置かれています。 i\ (1 \leq i \leq N) 番目のピースは縦 h_i ブロック、横 w_i ブロックの長方形状です。

これらのピースは以下の方法で得られたことがわかっています。

はじめに縦 H ブロック、横 W ブロックの板チョコを手に持つ。机には何も置かれていない。
以下の操作を N-1 回繰り返す。
- 現在手に持っているピースを 2 つに分割する。分割した後のピースはどちらもブロックの境界に沿った長方形でなくてはならない。
- 一方のピースを机に置き、もう一方のピースは手に持ったままにする。
最後に手に持っているピースを机に置く。

以下の条件を満たすように N 個のピースを縦 H ブロック、横 W ブロックの長方形状に並べる方法を一つ求めてください。

異なるピース同士は重ならない。
ピースは回転してはいけない。すなわち h\neq w に対して縦 h ブロック、横 w ブロックのピースを縦 w ブロック、横 h ブロックのピースとして配置することはできない。

制約

1 \leq H \leq 10^9
1 \leq W \leq 10^9
2 \leq N \leq 2\times 10^5
1 \leq h_i \leq H
1 \leq w_i \leq W
入力は問題文中の手順で得られたことが保証される
入力はすべて整数

入力

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

H W N
h_1 w_1
h_2 w_2
\vdots
h_N w_N

出力

条件を満たす並べ方において i\ (1 \leq i \leq N) 番目のピースの一番左上のブロックが全体で上から x_i 行目、左から y_i 列目のブロックに位置するとき、以下の形式で出力せよ。

x_1 y_1
x_2 y_2
\vdots
x_N y_N

条件を満たす並べ方が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

出力例 1

出力例の並べ方を図示すると以下のようになります。

入力例 2

出力例 2

Score : 425 points

Problem Statement

There are N pieces of a chocolate bar placed on a table. Piece i\ (1 \leq i \leq N) is a rectangle of h_i blocks tall and w_i blocks wide.

It is known that these pieces were obtained by the following procedure.

Start by holding a chocolate bar of H blocks tall and W blocks wide. Nothing is placed on the table.
Repeat the following operation N-1 times.
- Split the piece currently in hand into two pieces. Both pieces after splitting must be rectangles along the block boundaries.
- Place one of the pieces on the table, and keep the other piece in hand.
Finally, place the piece in hand on the table.

Find one way to arrange the N pieces into a rectangle of H blocks tall and W blocks wide satisfying the following conditions.

Different pieces do not overlap.
Pieces must not be rotated. That is, for h \neq w, a piece of h blocks tall and w blocks wide cannot be placed as a piece of w blocks tall and h blocks wide.

Constraints

1 \leq H \leq 10^9
1 \leq W \leq 10^9
2 \leq N \leq 2\times 10^5
1 \leq h_i \leq H
1 \leq w_i \leq W
It is guaranteed that the input was obtained by the procedure described in the problem statement.
All input values are integers.

Input

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

H W N
h_1 w_1
h_2 w_2
\vdots
h_N w_N

Output

In a valid arrangement, let the top-left block of piece i\ (1 \leq i \leq N) be located at the x_i-th row from the top and the y_i-th column from the left of the whole rectangle. Output in the following format:

x_1 y_1
x_2 y_2
\vdots
x_N y_N

If there are multiple valid arrangements, any of them will be accepted.

Sample Input 1

Sample Output 1

The arrangement in the sample output is illustrated below.

Sample Input 2

Sample Output 2

E - Many LCMs

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

配点 : 475 点

問題文

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

k=1,2,\dots,N について、A のうち A_k を除いた N-1 個の要素の最小公倍数を 998244353 で割ったあまりを求めてください。

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

制約

1 \leq T \leq 10^5
2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^7
入力はすべて整数
1 つの入力に含まれるテストケースについて、N の総和は 2 \times 10^5 以下

入力

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

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

ここで \mathrm{case}_i は i 番目のテストケースの入力を意味する。各テストケースは以下の形式で与えられる。

N
A_1 A_2 \cdots A_N

出力

以下の形式で出力せよ。

\mathrm{answer}_1
\mathrm{answer}_2
\vdots
\mathrm{answer}_T

ここで \mathrm{answer}_i は i 番目のテストケースに対する出力を意味する。各テストケースに対しては、以下の通り出力せよ。

A のうち A_k を除いた N-1 個の要素の最小公倍数を 998244353 で割ったあまりが L_k であるとする。このとき以下の形式で出力せよ。

L_1 L_2 \cdots L_N

入力例 1

3
5
9 12 25 8 15
8
592 26 167 912 171 321 327 651
10
9566582 2785103 1924635 359502 6912831 4893928 2820155 5071742 1836019 9037883

出力例 1

600 1800 360 900 1800
447582749 506009091 523568328 588652065 196217355 471970745 921220985 738745385
747032704 756838459 344127037 146466685 159487731 555429485 826726159 884617928 322846201 298477407

一個目のテストケースについて、以下のようになります。

A のうち A_1 を除いた N-1 個の要素は 12,25,8,15 であり、これらの最小公倍数は 600 です。
A のうち A_2 を除いた N-1 個の要素は 9,25,8,15 であり、これらの最小公倍数は 1800 です。
A のうち A_3 を除いた N-1 個の要素は 9,12,8,15 であり、これらの最小公倍数は 360 です。
A のうち A_4 を除いた N-1 個の要素は 9,12,25,15 であり、これらの最小公倍数は 900 です。
A のうち A_5 を除いた N-1 個の要素は 9,12,25,8 であり、これらの最小公倍数は 1800 です。

Score : 475 points

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N.

For each k=1,2,\dots,N, find the remainder when the least common multiple of the N-1 elements of A excluding A_k is divided by 998244353.

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

Constraints

1 \leq T \leq 10^5
2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^7
All input values are integers.
The sum of N over all test cases in a single input is at most 2 \times 10^5.

Input

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

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

Here, \mathrm{case}_i denotes the input for the i-th test case. Each test case is given in the following format:

N
A_1 A_2 \cdots A_N

Output

Output in the following format:

\mathrm{answer}_1
\mathrm{answer}_2
\vdots
\mathrm{answer}_T

Here, \mathrm{answer}_i denotes the output for the i-th test case. For each test case, output as follows.

Let L_k be the remainder when the least common multiple of the N-1 elements of A excluding A_k is divided by 998244353. Then, output in the following format:

L_1 L_2 \cdots L_N

Sample Input 1

3
5
9 12 25 8 15
8
592 26 167 912 171 321 327 651
10
9566582 2785103 1924635 359502 6912831 4893928 2820155 5071742 1836019 9037883

Sample Output 1

600 1800 360 900 1800
447582749 506009091 523568328 588652065 196217355 471970745 921220985 738745385
747032704 756838459 344127037 146466685 159487731 555429485 826726159 884617928 322846201 298477407

For the first test case, the following holds.

The N-1 elements of A excluding A_1 are 12,25,8,15, and their least common multiple is 600.
The N-1 elements of A excluding A_2 are 9,25,8,15, and their least common multiple is 1800.
The N-1 elements of A excluding A_3 are 9,12,8,15, and their least common multiple is 360.
The N-1 elements of A excluding A_4 are 9,12,25,15, and their least common multiple is 900.
The N-1 elements of A excluding A_5 are 9,12,25,8, and their least common multiple is 1800.

F - Exactly K Steps 2

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

配点 : 500 点

問題文

頂点 1, 頂点 2,\ldots, 頂点 N の N 頂点からなる有向グラフがあります。 1 以上 N 以下の任意の整数の 2 つ組 (i,j) について、頂点 i から頂点 j への有向辺がちょうど 1 本存在し、そのコストは C _ {i,j} です。

正整数 K が与えられます。 s=1,2,\ldots,N のそれぞれについて、以下の問題を解いてください。

頂点 s から出発し、辺に沿って移動することを K 回繰り返して頂点 s へ向かう方法のうち、通った辺のコストの総和としてありうる最小値を求めよ。厳密には、v _ 0=v _ K=s を満たす 1 以上 N 以下の整数からなる長さ K+1 の列 v=(v _ 0,v _ 1,\ldots,v _ K) に対する \displaystyle\sum _ {i=1} ^ {K}C _ {v _ {i-1},v _ i} の総和としてありうる最小値を求めよ。

制約

1\le N\le100
1\le K\le10 ^ 9
0\le C _ {i,j}\le10 ^ 9\ (1\le i\le N,1\le j\le N)
入力はすべて整数

入力

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

N K
C _ {1,1} C _ {1,2} \ldots C _ {1,N}
C _ {2,1} C _ {2,2} \ldots C _ {2,N}
\vdots
C _ {N,1} C _ {N,2} \ldots C _ {N,N}

出力

N 行にわたって出力せよ。 i 行目 (1\le i\le N) には s=i に対する問題の答えを出力せよ。

入力例 1

出力例 1

s=1 のとき、1\rightarrow2\rightarrow3\rightarrow1 と移動すると、通った辺のコストの総和は 1+2+5=8 となります。頂点 1 からスタートして 3 回辺に沿って移動し、通った辺のコストの総和を 7 以下にすることはできないため、1 行目には 8 を出力してください。

s=4 のとき、4\rightarrow4\rightarrow4\rightarrow4 と移動すると、通った辺のコストの総和は 3+3+3=9 となります。同じ辺や同じ頂点を複数回通ってもよいことと、同じ辺を複数回通った場合は通った回数だけ総和にその辺のコストが足されることに注意してください。

入力例 2

3 1000000000
100 999 999
999 100 999
999 999 100

出力例 2

100000000000
100000000000
100000000000

答えが 2 ^ {32} 以上になる場合があります。

入力例 3

10 9482
748 169 586 329 972 529 432 519 408 587
138 249 656 114 632 299 984 755 404 772
155 506 832 854 353 465 387 374 567 385
631 556 951 428 104 705 530 406 258 102
709 325 334 193 520 798 749 582 337 910
530 110 659 635 786 773 811 468 810 638
111 822 554 627 395 959 924 698 777 893
142 848 532 781 711 814 665 395 960 290
746 266 603 553 893 353 323 640 172 263
749 921 845 334 594 821 233 695 109 951

出力例 3

Score : 500 points

Problem Statement

There is a directed graph with N vertices, vertex 1, vertex 2,\ldots, vertex N. For any pair of integers (i,j) with 1 \leq i,j \leq N, there is exactly one directed edge from vertex i to vertex j with cost C_{i,j}.

You are given a positive integer K. For each of s=1,2,\ldots,N, solve the following problem.

Among the ways to start at vertex s, move along an edge K times, and return to vertex s, find the minimum possible total cost of the edges traversed. More formally, find the minimum possible value of \displaystyle\sum_{i=1}^{K}C_{v_{i-1},v_i} for a sequence v=(v_0,v_1,\ldots,v_K) of integers between 1 and N, inclusive, of length K+1 satisfying v_0=v_K=s.

Constraints

1 \le N \le 100
1 \le K \le 10^9
0 \le C_{i,j} \le 10^9\ (1 \le i \le N,1 \le j \le N)
All input values are integers.

Input

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

N K
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
\vdots
C_{N,1} C_{N,2} \ldots C_{N,N}

Output

Output N lines. The i-th line (1 \le i \le N) should contain the answer to the problem for s=i.

Sample Input 1

Sample Output 1

For s=1, moving 1\rightarrow2\rightarrow3\rightarrow1 gives a total cost of 1+2+5=8. It is impossible to start at vertex 1, move along an edge three times, and achieve a total cost of 7 or less, so print 8 on the first line.

For s=4, moving 4\rightarrow4\rightarrow4\rightarrow4 gives a total cost of 3+3+3=9. Note that the same edge or the same vertex may be traversed multiple times, and if the same edge is traversed multiple times, its cost is added to the total that many times.

Sample Input 2

3 1000000000
100 999 999
999 100 999
999 999 100

Sample Output 2

100000000000
100000000000
100000000000

The answer may be 2^{32} or greater.

Sample Input 3

10 9482
748 169 586 329 972 529 432 519 408 587
138 249 656 114 632 299 984 755 404 772
155 506 832 854 353 465 387 374 567 385
631 556 951 428 104 705 530 406 258 102
709 325 334 193 520 798 749 582 337 910
530 110 659 635 786 773 811 468 810 638
111 822 554 627 395 959 924 698 777 893
142 848 532 781 711 814 665 395 960 290
746 266 603 553 893 353 323 640 172 263
749 921 845 334 594 821 233 695 109 951

Sample Output 3

G - Knight Placement

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

配点 : 600 点

問題文

縦 N 行、横 N 列のマス目があります。上から i 行目 (1\le i\le N) 、左から j 行目 (1\le j\le N) のマスをマス (i,j) と呼びます。

それぞれのマスは空きマスか壁マスのどちらかであり、長さ N の文字列からなる長さ N の列 (S _ 1,S _ 2,\ldots,S _ N) で表されます。マス (i,j)\ (1\le i\le N,1\le j\le N) は S _ i の j 文字目が . のとき空きマスであり、# のとき壁マスです。

あなたは、このマス目にコマを置けるだけ置きたいです。コマの置き方には以下のような制約があります。

壁マスにコマを置くことはできない。
1 つのマスにコマを 2 つ以上置くことはできない。
マス (i,j) にコマが置かれているとき、マス (i,j) から縦に A マス横に B マス移動したマスおよび、縦に B マス横に A マス移動したマスにコマを置くことはできない。より厳密には、マス (i,j) にコマが置かれているとき、マス (i+A,j+B), マス (i+B,j+A), マス (i+B,j-A), マス (i+A,j-B), マス (i-A,j-B), マス (i-B,j-A), マス (i-B,j+A), マス (i-A,j+B) のどのマスにも（それぞれそのマスが存在するなら）コマを置くことはできない。

この制約のもと置くことができるコマの個数の最大値を K として、制約を満たす K 個のコマの配置をひとつ求めてください。

制約

1\le N\le300
0\le A\le B\le N
1\le B
N,A,B は整数
S _ i は ., # からなる長さ N の文字列 (1\le i\le N)

入力

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

N A B
S _ 1
S _ 2
\vdots
S _ N

出力

制約を満たす K 個のコマの配置をひとつ求め、その配置を表す文字列を N 行にわたって出力せよ。 i 行目 (1\le i\le N) には、., o, # からなる N 文字の文字列を出力せよ。 i 行目に出力する文字列の j 文字目 (1\le j\le N) は、マス (i,j) がコマが置かれていない空きマスなら . 、マス (i,j) がコマが置かれている空きマスなら o 、マス (i,j) が壁マスなら # とせよ。

条件を満たす配置が複数ある場合、そのうちどれを出力しても正答と判定される。

入力例 1

5 1 2
..#..
..##.
.#..#
##..#
.#...

出力例 1

o.#.o
oo##.
o#..#
##.o#
o#ooo

例えば、制約を満たしながら以下のように 10 個のコマを置くことができます。

制約を満たしながら 11 個のコマを置くことはできないので、上のような置き方に対応する盤面

o.#.o
oo##.
o#..#
##.o#
o#ooo

を出力すると正答と判定されます。

条件を満たす配置が複数ある場合どれを出力しても正答と判定されることに注意してください。例えば、次のようにしても制約を満たしながら 10 個のコマを置くことができます。

よって、

oo#oo
o.##o
.#..#
##..#
o#ooo

を出力しても正答と判定されます。

入力例 2

4 0 1
.###
##.#
#.##
###.

出力例 2

o###
##o#
#o##
###o

すべての空きマスに 1 つずつコマを置くことで制約を満たすことができます。

入力例 3

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

出力例 3

#ooo#....ooo....##o#
oo##o...oooo#..ooooo
ooooo##oo#ooo.###o#o
o#ooo##.##o#o#.#oo#o
#ooo#....o###..#ooo#
#...##...oo.##.##o#.
.#o...#.##.##...#oo.
#.o##.....o....#..o#
##o#.....o.o..##oo..
ooo#oo#.ooo#.#.#ooo#
#oooo.#o##o#oo.#oooo
##ooo...oooo..o.oo#o
.#oo..#o.#oo..#oooo.
........#.o......#o#
..oo....#.#o.##..o.#
.##.o...#.o..#....o.
.##o#.##...o#.#.oo##
oooooo#.oo#oo#o.oooo
.oooo..o.##ooo#oo#o#
###oooo.#ooo#.o.o#oo

Score : 600 points

Problem Statement

There is a grid with N rows and N columns. The cell at the i-th row from the top (1 \le i \le N) and the j-th column from the left (1 \le j \le N) is called cell (i,j).

Each cell is an empty cell or a wall cell, represented by a sequence of N strings of length N each, (S_1,S_2,\ldots,S_N). Cell (i,j)\ (1 \le i \le N,1 \le j \le N) is an empty cell if the j-th character of S_i is ., and a wall cell if it is #.

You want to place as many pieces as possible on this grid. The placement of pieces is subject to the following constraints.

A piece cannot be placed on a wall cell.
At most one piece can be placed on a single cell.
If a piece is placed on cell (i,j), no piece can be placed on the cell reached by moving A cells vertically and B cells horizontally from cell (i,j), or the cell reached by moving B cells vertically and A cells horizontally. More formally, if a piece is placed on cell (i,j), then no piece can be placed on any of cell (i+A,j+B), cell (i+B,j+A), cell (i+B,j-A), cell (i+A,j-B), cell (i-A,j-B), cell (i-B,j-A), cell (i-B,j+A), cell (i-A,j+B) (if those cells exist).

Let K be the maximum number of pieces that can be placed under these constraints, and find one placement of K pieces satisfying the constraints.

Constraints

1 \le N \le 300
0 \le A \le B \le N
1 \le B
N,A,B are integers.
S_i is a string of length N consisting of . and # (1 \le i \le N).

Input

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

N A B
S_1
S_2
\vdots
S_N

Output

Find one placement of K pieces satisfying the constraints, and output it as strings over N lines. The i-th line (1 \le i \le N) should contain a string of N characters consisting of ., o, and #. The j-th character (1 \le j \le N) of the string on the i-th line should be . if cell (i,j) is an empty cell with no piece, o if cell (i,j) is an empty cell with a piece, and # if cell (i,j) is a wall cell.

If there are multiple valid placements, any of them will be accepted.

Sample Input 1

5 1 2
..#..
..##.
.#..#
##..#
.#...

Sample Output 1

o.#.o
oo##.
o#..#
##.o#
o#ooo

For example, 10 pieces can be placed as follows while satisfying the constraints.

It is impossible to place 11 pieces while satisfying the constraints, so outputting the board corresponding to the placement above,

o.#.o
oo##.
o#..#
##.o#
o#ooo

will be judged as correct.

Note that any valid placement will be accepted if there are multiple of them. For example, the following also allows 10 pieces to be placed while satisfying the constraints.

Thus, outputting

oo#oo
o.##o
.#..#
##..#
o#ooo

will also be judged as correct.

Sample Input 2

4 0 1
.###
##.#
#.##
###.

Sample Output 2

o###
##o#
#o##
###o

The constraints can be satisfied by placing one piece on each empty cell.

Sample Input 3

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

Sample Output 3

#ooo#....ooo....##o#
oo##o...oooo#..ooooo
ooooo##oo#ooo.###o#o
o#ooo##.##o#o#.#oo#o
#ooo#....o###..#ooo#
#...##...oo.##.##o#.
.#o...#.##.##...#oo.
#.o##.....o....#..o#
##o#.....o.o..##oo..
ooo#oo#.ooo#.#.#ooo#
#oooo.#o##o#oo.#oooo
##ooo...oooo..o.oo#o
.#oo..#o.#oo..#oooo.
........#.o......#o#
..oo....#.#o.##..o.#
.##.o...#.o..#....o.
.##o#.##...o#.#.oo##
oooooo#.oo#oo#o.oooo
.oooo..o.##ooo#oo#o#
###oooo.#ooo#.o.o#oo