AtCoder Beginner Contest 347

A - Divisible

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

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

A に含まれる要素のうち、K の倍数であるもののみを全て取り出し、それらを K で割って出力してください。

制約

1\leq N,K\leq 100
1\leq A_1 < A_2 < \ldots < A_N \leq 100
A には K の倍数が 1 個以上含まれる
入力される数値は全て整数

入力

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

N K
A_1 A_2 \ldots A_N

出力

A に含まれる要素のうち、K の倍数であるもの全てを K で割った値を、空白区切りで昇順に出力せよ。

入力例 1

5 2
2 5 6 7 10

出力例 1

1 3 5

A に含まれる要素のうち、2 の倍数は 2,6,10 です。それらを 2 で割って得られる 1,3,5 を空白区切りで昇順に出力してください。

入力例 2

3 1
3 4 7

出力例 2

3 4 7

入力例 3

5 10
50 51 54 60 65

出力例 3

5 6

Score: 100 points

Problem Statement

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

Extract all elements of A that are multiples of K, divide them by K, and print the quotients.

Constraints

1\leq N,K\leq 100
1\leq A_1 < A_2 < \ldots < A_N \leq 100
A has at least one multiple of K.
All given numbers are integers.

Input

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

N K
A_1 A_2 \ldots A_N

Output

Divide all elements of A that are multiples of K and print the quotients in ascending order with spaces in between.

Sample Input 1

5 2
2 5 6 7 10

Sample Output 1

1 3 5

The multiples of 2 among the elements in A are 2, 6, and 10. Divide them by 2 to get 1, 3, and 5, and print them in ascending order with spaces in between.

Sample Input 2

3 1
3 4 7

Sample Output 2

3 4 7

Sample Input 3

5 10
50 51 54 60 65

Sample Output 3

5 6

B - Substring

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

英小文字からなる文字列 S が与えられます。S の空でない部分文字列は何種類ありますか？

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

制約

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

入力

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

出力

答えを出力せよ。

入力例 1

yay

出力例 1

S の空でない部分文字列は以下の 5 種類です。

a
y
ay
ya
yay

入力例 2

aababc

出力例 2

入力例 3

abracadabra

出力例 3

Score: 200 points

Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Input

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

Output

Print the answer.

Sample Input 1

yay

Sample Output 1

S has the following five different non-empty substrings:

a
y
ay
ya
yay

Sample Input 2

aababc

Sample Output 2

Sample Input 3

abracadabra

Sample Output 3

C - Ideal Holidays

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 350 点

問題文

AtCoder 王国の 1 週間は A+B 日からなり、1 日目から A 日目が休日で、A+1 日目から A+B 日目が平日です。

高橋くんは N 個の予定があり、i 番目の予定は今日から D_i 日後です。

高橋くんは今日が 1 週間の何日目かを忘れてしまいました。高橋くんの N 個の予定が全て休日である可能性があるかを判定してください。

制約

1\leq N\leq 2\times 10^5
1\leq A,B\leq 10^9
1\leq D_1<D_2<\ldots<D_N\leq 10^9

入力

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

N A B
D_1 D_2 \ldots D_N

出力

高橋くんの N 個の予定が全て休日である可能性がある場合は Yes を、そうでない場合は No を一行に出力せよ。

入力例 1

3 2 5
1 2 9

出力例 1

Yes

入力では 1 週間は 7 日からなり、1 日目から 2 日目が休日、3 日目から 7 日目が平日です。

今日が 1 週間の 7 日目だとします。このとき、1 日後は 1 週間の 1 日目、2 日後は 1 週間の 2 日目、9 日後は 1 週間の 2 日目となり、全ての予定が休日となります。そのため、高橋くんの N 個の予定が全て休日である可能性があります。

入力例 2

2 5 10
10 15

出力例 2

No

入力例 3

4 347 347
347 700 705 710

出力例 3

Yes

Score: 350 points

Problem Statement

In the Kingdom of AtCoder, a week consists of A+B days, with the first through A-th days being holidays and the (A+1)-th through (A+B)-th being weekdays.

Takahashi has N plans, and the i-th plan is scheduled D_i days later.

He has forgotten what day of the week it is today. Determine if it is possible for all of his N plans to be scheduled on holidays.

Constraints

1\leq N\leq 2\times 10^5
1\leq A,B\leq 10^9
1\leq D_1<D_2<\ldots<D_N\leq 10^9

Input

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

N A B
D_1 D_2 \ldots D_N

Output

Print Yes in a single line if it is possible for all of Takahashi's N plans to be scheduled on holidays, and No otherwise.

Sample Input 1

3 2 5
1 2 9

Sample Output 1

Yes

In this input, a week consists of seven days, with the first through second days being holidays and the third through seventh days being weekdays.

Let us assume today is the seventh day of the week. In this case, one day later would be the first day of the week, two days later would be the second day of the week, and nine days later would also be the second day of the week, making all plans scheduled on holidays. Therefore, it is possible for all of Takahashi's N plans to be scheduled on holidays.

Sample Input 2

2 5 10
10 15

Sample Output 2

No

Sample Input 3

4 347 347
347 700 705 710

Sample Output 3

Yes

D - Popcount and XOR

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

非負整数 a,b,C が与えられます。次の 5 つの条件をすべて満たす非負整数の組 (X,Y) が存在するか判定し、存在するならひとつ出力してください。

0\leq X\lt2 ^ {60}
0\leq Y\lt2 ^ {60}
\operatorname{popcount}(X)=a
\operatorname{popcount}(Y)=b
X\oplus Y=C

ただし、\oplus はビットごとの排他的論理和を表します。

条件を満たす (X,Y) が複数存在する場合、どれを出力しても構いません。

popcount とは？

非負整数 x について x の popcount とは、x を 2 進法で表記したときの 1 の個数です。より厳密には、非負整数 x について \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) が成り立っているとき \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i です。

例えば、13 を 2 進法で表記すると 1101 なので、 \operatorname{popcount}(13)=3 となります。

ビットごとの排他的論理和とは？

非負整数 x,y について x,y のビットごとの排他的論理和 x\oplus y は以下のように定義されます。

x\oplus y を 2 進法で表記したときの 2 ^ k\ (k\geq0) の位は、x,y を 2 進法で表記したときの 2 ^ k\ (k\geq0) の位の数のうち一方のみが 1 であれば 1 、そうでなければ 0 となる。

例えば、9,3 を 2 進法で表記するとそれぞれ 1001, 0011 なので、9\oplus3=10 となります（10 を 2 進法で表記すると 1010 です）。

制約

0\leq a\leq60
0\leq b\leq60
0\leq C\lt2 ^ {60}
入力はすべて整数

入力

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

a b C

出力

条件を満たす非負整数の組が存在するならば、そのような (X,Y) をひとつ選び X,Y をこの順に空白を区切りとして出力せよ。存在しないならば、-1 を出力せよ。

入力例 1

3 4 7

出力例 1

28 27

(X,Y)=(28,27) は条件を満たします。 X,Y を 2 進法で表記するとそれぞれ 11100 と 11011 になります。

X を 2 進法で表記すると 11100 になるので、\operatorname{popcount}(X)=3 です。
Y を 2 進法で表記すると 11011 になるので、\operatorname{popcount}(Y)=4 です。
X\oplus Y を 2 進法で表記すると 00111 となり、X\oplus Y=7 です。

条件を満たす非負整数の組が複数存在する場合どれを出力しても構わないため、例えば 42 45 と出力しても正解になります。

入力例 2

34 56 998244353

出力例 2

-1

条件を満たす非負整数の組は存在しません。

入力例 3

39 47 530423800524412070

出力例 3

540431255696862041 10008854347644927

出力すべき値が 32\operatorname{bit} 整数に収まらない場合があります。

Score: 400 points

Problem Statement

You are given non-negative integers a, b, and C. Determine if there is a pair of non-negative integers (X, Y) that satisfies all of the following five conditions. If such a pair exists, print one.

0 \leq X < 2^{60}
0 \leq Y < 2^{60}
\operatorname{popcount}(X) = a
\operatorname{popcount}(Y) = b
X \oplus Y = C

Here, \oplus denotes the bitwise XOR.

If multiple pairs (X, Y) satisfy the conditions, you may print any of them.

What is popcount?

For a non-negative integer x, the popcount of x is the number of 1s in the binary representation of x. More precisely, for a non-negative integer x such that \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace), we have \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i.

For example, 13 in binary is 1101, so \operatorname{popcount}(13)=3.

What is bitwise XOR?

For non-negative integers x, y, the bitwise exclusive OR x \oplus y is defined as follows.

The 2^k's place \ (k\geq0) in the binary representation of x \oplus y is 1 if exactly one of the 2^k's places \ (k\geq0) in the binary representations of x and y is 1, and 0 otherwise.

For example, 9 and 3 in binary are 1001 and 0011, respectively, so 9 \oplus 3 = 10 (in binary, 1010).

Constraints

0 \leq a \leq 60
0 \leq b \leq 60
0 \leq C < 2^{60}
All input values are integers.

Input

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

a b C

Output

If there is a pair of non-negative integers that satisfies the conditions, choose one such pair (X, Y) and print X and Y in this order, with a space in between. If no such pair exists, print -1.

Sample Input 1

3 4 7

Sample Output 1

28 27

The pair (X, Y) = (28, 27) satisfies the conditions. Here, X and Y in binary are 11100 and 11011, respectively.

X in binary is 11100, so \operatorname{popcount}(X) = 3.
Y in binary is 11011, so \operatorname{popcount}(Y) = 4.
X \oplus Y in binary is 00111, so X \oplus Y = 7.

If multiple pairs of non-negative integers satisfy the conditions, you may print any of them, so printing 42 45, for example, would also be accepted.

Sample Input 2

34 56 998244353

Sample Output 2

-1

No pair of non-negative integers satisfies the conditions.

Sample Input 3

39 47 530423800524412070

Sample Output 3

540431255696862041 10008854347644927

Note that the values to be printed may not fit in 32-bit integers.

E - Set Add Query

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

全ての要素が 0 で初期化された長さ N の整数列 A=(A_1,A_2,\ldots,A_N) があります。また、集合 S があります。はじめ S は空です。

以下の Q 個のクエリを順に行います。Q 個のクエリを全て処理した後の数列 A の各要素の値を求めてください。 i 番目のクエリは以下の形式です。

整数 x_i が与えられる。整数 x_i が S に含まれる場合、S から x_i を削除する。そうでない場合、S に x_i を追加する。次に、j=1,2,\ldots,N について、j\in S ならば A_j に |S| を加算する。

なお、|S| は集合 S の要素数を意味します。例えば S=\lbrace 3,4,7\rbrace のとき、|S|=3 です。

制約

1\leq N,Q\leq 2\times10^5
1\leq x_i\leq N
入力される数値は全て整数

入力

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

N Q
x_1 x_2 \ldots x_Q

出力

クエリを全て処理した後の数列 A を以下の形式で出力せよ。

A_1 A_2 \ldots A_N

入力例 1

3 4
1 3 3 2

出力例 1

6 2 2

1 番目のクエリでは、S に 1 を追加し、S=\lbrace 1\rbrace となります。その後、A_1 に |S|=1 を加算します。A=(1,0,0) となります。

2 番目のクエリでは、S に 3 を追加し、S=\lbrace 1,3\rbrace となります。その後、A_1,A_3 に |S|=2 を加算します。A=(3,0,2) となります。

3 番目のクエリでは、S から 3 を削除し、S=\lbrace 1\rbrace となります。その後、A_1 に |S|=1 を加算します。A=(4,0,2) となります。

4 番目のクエリでは、S に 2 を追加し、S=\lbrace 1,2\rbrace となります。その後、A_1,A_2 に |S|=2 を加算します。A=(6,2,2) となります。

最終的に、A=(6,2,2) となります。

入力例 2

4 6
1 2 3 2 4 2

出力例 2

15 9 12 7

Score: 500 points

Problem Statement

There is an integer sequence A=(A_1,A_2,\ldots,A_N) of length N, where all elements are initially set to 0. Also, there is a set S, which is initially empty.

Perform the following Q queries in order. Find the value of each element in the sequence A after processing all Q queries. The i-th query is in the following format:

An integer x_i is given. If the integer x_i is contained in S, remove x_i from S. Otherwise, insert x_i to S. Then, for each j=1,2,\ldots,N, add |S| to A_j if j\in S.

Here, |S| denotes the number of elements in the set S. For example, if S=\lbrace 3,4,7\rbrace, then |S|=3.

Constraints

1\leq N,Q\leq 2\times10^5
1\leq x_i\leq N
All given numbers are integers.

Input

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

N Q
x_1 x_2 \ldots x_Q

Output

Print the sequence A after processing all queries in the following format:

A_1 A_2 \ldots A_N

Sample Input 1

3 4
1 3 3 2

Sample Output 1

6 2 2

In the first query, 1 is inserted to S, making S=\lbrace 1\rbrace. Then, |S|=1 is added to A_1. The sequence becomes A=(1,0,0).

In the second query, 3 is inserted to S, making S=\lbrace 1,3\rbrace. Then, |S|=2 is added to A_1 and A_3. The sequence becomes A=(3,0,2).

In the third query, 3 is removed from S, making S=\lbrace 1\rbrace. Then, |S|=1 is added to A_1. The sequence becomes A=(4,0,2).

In the fourth query, 2 is inserted to S, making S=\lbrace 1,2\rbrace. Then, |S|=2 is added to A_1 and A_2. The sequence becomes A=(6,2,2).

Eventually, the sequence becomes A=(6,2,2).

Sample Input 2

4 6
1 2 3 2 4 2

Sample Output 2

15 9 12 7

F - Non-overlapping Squares

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 525 点

問題文

N\times N のマス目があり、上から i 行目、左から j 列目 (1\leq i,j\leq N) のマスには整数 A _ {i,j} が書かれています。

整数 M が与えられます。 M\times M のマス目を重ならないように 3 つ選ぶときの、選んだマス目に書かれている整数の総和としてありえる最大値を求めてください。

問題の厳密な定義

整数の 6 つ組 (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3) が次の 3 つの条件を満たしているとき、良い 6 つ組ということにします。

1\leq i _ k\leq N-M+1\ (k=1,2,3)
1\leq j _ k\leq N-M+1\ (k=1,2,3)
k\neq l\ (k,l\in\lbrace1,2,3\rbrace) ならば、\lbrace(i,j)\mid i _ k\leq i\lt i _ k+M\wedge j _ k\leq j\lt j _ k+M\rbrace と \lbrace(i,j)\mid i _ l\leq i\lt i _ l+M\wedge j _ l\leq j\lt j _ l+M\rbrace に共通部分はない

良い 6 つ組 (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3) に対する値 \displaystyle \sum _ {k=1} ^ 3\sum _ {i=i _ k} ^ {i _ k+M-1}\sum _ {j=j _ k} ^ {j _ k+M-1}A _ {i,j} の最大値を求めてください。この問題の制約のもとで良い 6 つ組が存在することが示せます。

制約

2\leq N\leq 1000
1\leq M\leq N/2
0\leq A _ {i,j}\leq10 ^ 9
入力はすべて整数

入力

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

N M
A _ {1,1} A _ {1,2} \ldots A _ {1,N}
A _ {2,1} A _ {2,2} \ldots A _ {2,N}
 \vdots  \ \vdots  \ddots  \vdots
A _ {N,1} A _ {N,2} \ldots A _ {N,N}

出力

答えを出力せよ。

入力例 1

7 3
3 1 4 1 5 9 2
6 5 3 5 8 9 7
9 3 2 3 8 4 6
2 6 4 3 3 8 3
2 7 9 5 0 2 8
8 4 1 9 7 1 6
9 3 9 9 3 7 5

出力例 1

与えられたグリッドから、以下の図のように 3\times3 のマス目を 3 つ選ぶと（これは (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)=(1,5,2,1,5,2) とすることに対応します）、選んだマス目に書かれている数の合計は 154 となります。

問題文の条件を満たす選び方であって選んだマス目に書かれている数の合計が 155 以上であるものは存在しないため、154 を出力してください。

入力例 2

7 1
3 1 4 1 5 9 2
6 5 3 5 8 9 7
9 3 2 3 8 4 6
2 6 4 3 3 8 3
2 7 9 5 0 2 8
8 4 1 9 7 1 6
9 3 9 9 3 7 5

出力例 2

以下のように選ぶのが最適です。

入力例 3

16 4
74 16 58 32 97 52 43 51 40 58 13 24 65 11 63 29
98 75 40 77 15 50 83 85 35 46 38 37 56 38 63 55
95 42 10 70 53 40 25 10 70 32 33 19 52 79 74 58
33 91 53 11 65 63 78 77 81 46 81 63 11 82 55 62
39 95 92 69 77 89 14 84 53 78 71 81 66 39 96 29
74 26 60 55 89 35 32 64 17 26 74 92 84 33 59 82
23 69 10 95 94 14 58 58 97 95 62 58 72 55 71 43
93 77 27 87 74 72 91 37 53 80 51 71 37 35 97 46
81 88 26 79 78 30 53 68 83 28 59 28 74 55 20 86
93 13 25 19 53 53 17 24 69 14 67 81 10 19 69 90
88 83 62 92 22 31 27 34 67 48 42 32 68 14 96 87
44 69 25 48 68 42 53 82 44 42 96 31 13 56 68 83
63 87 24 75 16 70 63 99 95 10 63 26 56 12 77 49
94 83 69 95 48 41 40 97 45 61 26 38 83 91 44 31
43 69 54 64 20 60 17 15 62 25 58 50 59 63 88 70
72 95 21 28 41 14 77 22 64 78 33 55 67 51 78 40

出力例 3

以下のように選ぶのが最適です。

Score: 525 points

Problem Statement

There is an N\times N grid, and the cell at the i-th row from the top and the j-th column from the left (1\leq i,j\leq N) contains the integer A _ {i,j}.

You are given an integer M. When choosing three non-overlapping M\times M grids, find the maximum possible sum of the integers written in the chosen grids.

Formal definition of the problem

A 6-tuple of integers (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3) is called a good 6-tuple when it satisfies the following three conditions:

1\leq i _ k\leq N-M+1\ (k=1,2,3)
1\leq j _ k\leq N-M+1\ (k=1,2,3)
If k\neq l\ (k,l\in\lbrace1,2,3\rbrace), the sets \lbrace(i,j)\mid i _ k\leq i\lt i _ k+M\wedge j _ k\leq j\lt j _ k+M\rbrace and \lbrace(i,j)\mid i _ l\leq i\lt i _ l+M\wedge j _ l\leq j\lt j _ l+M\rbrace do not intersect.

Find the maximum value of \displaystyle \sum _ {k=1} ^ 3\sum _ {i=i _ k} ^ {i _ k+M-1}\sum _ {j=j _ k} ^ {j _ k+M-1}A _ {i,j} for a good 6-tuple (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3). It can be shown that a good 6-tuple exists under the constraints of this problem.

Constraints

2\leq N\leq 1000
1\leq M\leq N/2
0\leq A _ {i,j}\leq10 ^ 9
All input values are integers.

Input

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

N M
A _ {1,1} A _ {1,2} \ldots A _ {1,N}
A _ {2,1} A _ {2,2} \ldots A _ {2,N}
 \vdots  \ \vdots  \ddots  \vdots
A _ {N,1} A _ {N,2} \ldots A _ {N,N}

Output

Print the answer.

Sample Input 1

7 3
3 1 4 1 5 9 2
6 5 3 5 8 9 7
9 3 2 3 8 4 6
2 6 4 3 3 8 3
2 7 9 5 0 2 8
8 4 1 9 7 1 6
9 3 9 9 3 7 5

Sample Output 1

From the given grid, if we choose three 3\times3 grids as shown in the figure below (this corresponds to setting (i _ 1,j _ 1,i _ 2,j _ 2,i _ 3,j _ 3)=(1,5,2,1,5,2)), the sum of the numbers written in the chosen grids will be 154.

There is no way to make the sum 155 or greater while satisfying the conditions in the problem statement, so print 154.

Sample Input 2

7 1
3 1 4 1 5 9 2
6 5 3 5 8 9 7
9 3 2 3 8 4 6
2 6 4 3 3 8 3
2 7 9 5 0 2 8
8 4 1 9 7 1 6
9 3 9 9 3 7 5

Sample Output 2

The following choice is optimal.

Sample Input 3

16 4
74 16 58 32 97 52 43 51 40 58 13 24 65 11 63 29
98 75 40 77 15 50 83 85 35 46 38 37 56 38 63 55
95 42 10 70 53 40 25 10 70 32 33 19 52 79 74 58
33 91 53 11 65 63 78 77 81 46 81 63 11 82 55 62
39 95 92 69 77 89 14 84 53 78 71 81 66 39 96 29
74 26 60 55 89 35 32 64 17 26 74 92 84 33 59 82
23 69 10 95 94 14 58 58 97 95 62 58 72 55 71 43
93 77 27 87 74 72 91 37 53 80 51 71 37 35 97 46
81 88 26 79 78 30 53 68 83 28 59 28 74 55 20 86
93 13 25 19 53 53 17 24 69 14 67 81 10 19 69 90
88 83 62 92 22 31 27 34 67 48 42 32 68 14 96 87
44 69 25 48 68 42 53 82 44 42 96 31 13 56 68 83
63 87 24 75 16 70 63 99 95 10 63 26 56 12 77 49
94 83 69 95 48 41 40 97 45 61 26 38 83 91 44 31
43 69 54 64 20 60 17 15 62 25 58 50 59 63 88 70
72 95 21 28 41 14 77 22 64 78 33 55 67 51 78 40

Sample Output 3

The following choice is optimal.

G - Grid Coloring 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N\times N のマス目があり、それぞれのマスには 0 以上 5 以下の整数が書かれています。上から i 行目、左から j 列目 (1\leq i,j\leq N) のマスをマス (i,j) と表し、マス (i,j) には整数 A _ {i,j} が書かれています。

このマス目に対して、次の操作を 0 回以上好きな回数行います。

0 が書かれているマス (i,j) と 1 以上 5 以下の整数 x を 1 つ選ぶ。選ばれたマスに書かれている数を x に変更する。

操作が終了したあと、マス (i,j) に書かれている整数を B _ {i,j} とします。マス目のコストを、隣接するマスに書かれた整数の差の二乗の総和とします。つまり、コストは次の式で表されます。

\displaystyle\sum _ {i=1} ^ N\sum _ {j=1} ^ {N-1}(B _ {i,j}-B _ {i,j+1})^2+\sum _ {i=1} ^ {N-1}\sum _ {j=1} ^ N(B _ {i,j}-B _ {i+1,j})^2

操作が終了したあとのマス目としてありえるもののうち、コストが最小のものを求めてください。

ただし、コストが最小となるマス目の状態が複数ある場合、そのうちどれを出力しても構いません。

制約

1\leq N\leq20
0\leq A _ {i,j}\leq 5\ (1\leq i\leq N,1\leq j\leq N)
入力はすべて整数

入力

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

N
A _ {1,1} A _ {1,2} \ldots A _ {1,N}
A _ {2,1} A _ {2,2} \ldots A _ {2,N}
 \vdots  \ \vdots  \ddots  \vdots
A _ {N,1} A _ {N,2} \ldots A _ {N,N}

出力

N 行に出力せよ。 i 行目 (1\leq i\leq N) にはコストが最小になるように操作を行ったときの B _ {i,1},B _ {i,2},\ldots,B _ {i,N} をこの順に、空白を区切りとして出力せよ。

入力例 1

出力例 1

与えられるマス目は以下のようになります。

図の右の状態になるように操作を行うことで、コストが 2 ^ 2\times6+1 ^ 2\times18+0 ^ 2\times16=42 となります。

コストが 41 以下になることはないので、この状態に対応する B _ {i,j} を出力することで正解になります。

入力例 2

出力例 2

0 0 0
0 0 0
0 0 0

はじめからコストが 0 なので、操作を行わないことでコストが最小になります。

操作が終了した後のマスの状態のうちコストが最小のものが複数ある場合どれを出力しても構わないため、

2 2 2
2 2 2
2 2 2

のように出力しても正解となります。

入力例 3

10
1 0 0 3 0 0 0 0 0 0
1 0 0 4 0 1 0 5 0 0
0 0 0 0 0 0 2 0 3 0
0 0 2 0 0 0 4 0 0 3
0 3 4 3 3 0 3 0 0 5
4 1 3 4 4 0 2 1 0 0
2 0 1 0 5 2 0 1 1 5
0 0 0 5 0 0 3 2 4 0
4 5 0 0 3 2 0 3 5 0
4 0 0 5 0 0 0 3 0 5

出力例 3

1 2 3 3 3 2 3 4 4 4
1 2 3 4 3 1 3 5 4 4
2 2 2 3 3 2 2 3 3 3
2 2 2 3 3 3 4 3 3 3
3 3 4 3 3 3 3 2 3 5
4 1 3 4 4 3 2 1 2 4
2 2 1 4 5 2 2 1 1 5
3 3 3 5 4 3 3 2 4 5
4 5 4 4 3 2 3 3 5 5
4 4 4 5 4 3 3 3 4 5

Score: 600 points

Problem Statement

There is an N\times N grid where each cell contains an integer between 0 and 5, inclusive. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left (1\leq i,j\leq N). The integer written in cell (i,j) is A _ {i,j}.

You can perform the following operation any number of times, possibly zero:

Choose a cell (i,j) with 0 written in it and an integer x between 1 and 5, inclusive. Change the number written in the chosen cell to x.

After the operations, let B _ {i,j} be the integer written in cell (i,j). The cost of the grid is defined as the sum of the squares of the differences between the integers written in adjacent cells. In other words, the cost is represented by the following formula:

\displaystyle\sum _ {i=1} ^ N\sum _ {j=1} ^ {N-1}(B _ {i,j}-B _ {i,j+1})^2+\sum _ {i=1} ^ {N-1}\sum _ {j=1} ^ N(B _ {i,j}-B _ {i+1,j})^2

Among all possible states of the grid after the operations, find the one with the minimum cost.

If multiple grid states have the minimum cost, you may print any of them.

Constraints

1\leq N\leq20
0\leq A _ {i,j}\leq 5\ (1\leq i\leq N,1\leq j\leq N)
All input values are integers.

Input

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

N
A _ {1,1} A _ {1,2} \ldots A _ {1,N}
A _ {2,1} A _ {2,2} \ldots A _ {2,N}
 \vdots  \ \vdots  \ddots  \vdots
A _ {N,1} A _ {N,2} \ldots A _ {N,N}

Output

Print N lines. The i-th line (1\leq i\leq N) should contain B _ {i,1},B _ {i,2},\ldots,B _ {i,N} in this order, with spaces in between, after performing operations to minimize the cost.

Sample Input 1

Sample Output 1

The given grid is as follows:

After performing operations to achieve the state shown on the right of the figure, the cost will be 2 ^ 2\times6+1 ^ 2\times18+0 ^ 2\times16=42.

The cost cannot be 41 or less, so printing the corresponding B _ {i,j} for this state would be accepted.

Sample Input 2

Sample Output 2

0 0 0
0 0 0
0 0 0

The cost is already 0 from the beginning, so not performing any operations minimizes the cost.

If multiple grid states have the minimum cost, you may print any of them, so the following output would also be accepted:

2 2 2
2 2 2
2 2 2

Sample Input 3

10
1 0 0 3 0 0 0 0 0 0
1 0 0 4 0 1 0 5 0 0
0 0 0 0 0 0 2 0 3 0
0 0 2 0 0 0 4 0 0 3
0 3 4 3 3 0 3 0 0 5
4 1 3 4 4 0 2 1 0 0
2 0 1 0 5 2 0 1 1 5
0 0 0 5 0 0 3 2 4 0
4 5 0 0 3 2 0 3 5 0
4 0 0 5 0 0 0 3 0 5

Sample Output 3

1 2 3 3 3 2 3 4 4 4
1 2 3 4 3 1 3 5 4 4
2 2 2 3 3 2 2 3 3 3
2 2 2 3 3 3 4 3 3 3
3 3 4 3 3 3 3 2 3 5
4 1 3 4 4 3 2 1 2 4
2 2 1 4 5 2 2 1 1 5
3 3 3 5 4 3 3 2 4 5
4 5 4 4 3 2 3 3 5 5
4 4 4 5 4 3 3 3 4 5