AtCoder Beginner Contest 393

A - Poisonous Oyster

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

4 種類の牡蠣 1,2,3,4 があります。このうちちょうど 1 種類の牡蠣については、食べるとお腹を壊してしまいます。それ以外の牡蠣については、食べてもお腹を壊しません。

高橋君が牡蠣 1,2 を食べ、青木君が牡蠣 1,3 を食べました。二人がこれによってお腹を壊したかどうかの情報が二つの文字列 S_1,S_2 によって与えられます。具体的には、S_1= sick であるとき高橋君がお腹を壊したことを、S_1= fine であるとき高橋君がお腹を壊さなかったことを表します。同様に、S_2= sick であるとき青木君がお腹を壊したことを、S_2= fine であるとき青木君がお腹を壊さなかったことを表します。

与えられた情報をもとに、どの種類の牡蠣を食べるとお腹を壊すか判定してください。

制約

S_1, S_2 はそれぞれ sick または fine

入力

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

S_1 S_2

出力

食べるとお腹を壊す牡蠣の種類の番号を出力せよ。

入力例 1

sick fine

出力例 1

牡蠣 1,2 を食べた高橋君はお腹を壊し、牡蠣 1,3 を食べた青木君はお腹を壊さなかったので、牡蠣 2 を食べるとお腹を壊すことがわかります。

入力例 2

fine fine

出力例 2

牡蠣 1,2 を食べた高橋君も牡蠣 1,3 を食べた青木君もお腹を壊さなかったので、残る牡蠣 4 を食べるとお腹を壊すことがわかります。

Score : 100 points

Problem Statement

There are four types of oysters, labeled 1, 2, 3, and 4. Exactly one of these types causes stomach trouble if eaten. The other types do not cause stomach trouble when eaten.

Takahashi ate oysters 1 and 2, and Aoki ate oysters 1 and 3. The information on whether each person got sick is given as two strings S_1 and S_2. Specifically, S_1 = sick means Takahashi got sick, and S_1 = fine means Takahashi did not get sick. Likewise, S_2 = sick means Aoki got sick, and S_2 = fine means Aoki did not get sick.

Based on the given information, find which type of oyster causes stomach trouble.

Constraints

Each of S_1 and S_2 is sick or fine.

Input

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

S_1 S_2

Output

Print the label of the oyster that causes stomach trouble if eaten.

Sample Input 1

sick fine

Sample Output 1

Takahashi (who ate oysters 1 and 2) got sick, and Aoki (who ate oysters 1 and 3) did not get sick, so it can be concluded that oyster 2 causes stomach trouble.

Sample Input 2

fine fine

Sample Output 2

Neither Takahashi (who ate oysters 1 and 2) nor Aoki (who ate oysters 1 and 3) got sick, so it can be concluded that oyster 4 causes stomach trouble.

B - A..B..C

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

文字列 S が与えられます。

S の中に A, B, C がこの順に等間隔に並んでいる場所が何箇所あるか求めてください。

厳密には、3 つの整数の組 (i,j,k) であって、以下の条件をすべて満たすものの個数を求めてください。ここで、|S| で S の長さを、S_x で S の x 文字目を表すものとします。

1\leq i<j<k\leq |S|
j-i = k-j
S_i= A
S_j= B
S_k= C

制約

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

入力

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

出力

答えを出力せよ。

入力例 1

AABCC

出力例 1

(i,j,k)=(1,3,5),(2,3,4) の 2 つの組が条件を満たします。

入力例 2

ARC

出力例 2

入力例 3

AABAAABBAEDCCCD

出力例 3

Score : 200 points

Problem Statement

A string S is given.

Find how many places in S have A, B, and C in this order at even intervals.

Specifically, find the number of triples of integers (i,j,k) that satisfy all of the following conditions. Here, |S| denotes the length of S, and S_x denotes the x-th character of S.

1 \leq i < j < k \leq |S|
j - i = k - j
S_i = A
S_j = B
S_k = C

Constraints

S is an uppercase English string with length between 3 and 100, inclusive.

Input

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

Output

Print the answer.

Sample Input 1

AABCC

Sample Output 1

There are two triples (i,j,k) = (1,3,5) and (2,3,4) that satisfy the conditions.

Sample Input 2

ARC

Sample Output 2

Sample Input 3

AABAAABBAEDCCCD

Sample Output 3

C - Make it Simple

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

頂点に 1 から N の、辺に 1 から M の番号がついた N 頂点 M 辺の無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結ぶ辺です。
グラフから辺を取り除いてグラフを単純にするためには、少なくとも何本の辺を取り除く必要がありますか？
ここでグラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。

制約

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 5 \times 10^5
1 \leq u_i \leq N
1 \leq v_i \leq N
入力される値は全て整数

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

グラフを単純にするために取り除く必要がある辺の本数の最小値を出力せよ。

入力例 1

出力例 1

辺 3 と辺 5 を取り除くとグラフを単純にすることが出来て、これが取り除く辺の本数が最小となる選び方の 1 つです。よって答えは 2 本です。

入力例 2

1 0

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given an undirected graph with N vertices and M edges, where the vertices are numbered 1 through N and the edges are numbered 1 through M. Edge i connects vertices u_i and v_i.
To make the graph simple by removing edges, what is the minimum number of edges that must be removed?
Here, a graph is called simple if and only if it does not contain self-loops or multi-edges.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 5 \times 10^5
1 \leq u_i \leq N
1 \leq v_i \leq N
All input values are integers.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the minimum number of edges that must be removed to make the graph simple.

Sample Input 1

Sample Output 1

By removing edges 3 and 5, the graph becomes simple. This is one of the ways to remove the minimum number of edges, so the answer is 2.

Sample Input 2

1 0

Sample Output 2

Sample Input 3

Sample Output 3

D - Swap to Gather

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

0 および 1 からなる長さ N の文字列 S が与えられます。ここで、S には 1 が 1 つ以上含まれることが保証されます。

あなたは、以下の操作を繰り返し（0 回でも良い）行うことができます。

1\leq i\leq N-1 を満たす整数 i を選び、S の i 文字目と i+1 文字目を入れ替える。

すべての 1 がひとかたまりになった状態にするために必要な操作回数の最小値を求めてください。

なお、すべての 1 がひとかたまりになっているとは、ある整数 l,r\ (1\leq l\leq r\leq N) が存在し、 S の i 文字目は l\leq i\leq r ならば 1、そうでないならば 0 であることをいいます。

制約

2\leq N\leq 5\times 10^5
N は整数
S は 0 および 1 からなる長さ N の文字列
S には 1 が 1 つ以上含まれる

入力

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

N
S

出力

答えを出力せよ。

入力例 1

7
0101001

出力例 1

例えば、以下のように操作を 3 回行うと、すべての 1 がひとかたまりになります。

i=2 を選び、S の 2 文字目と 3 文字目を入れ替える。S= 0011001 になる。
i=6 を選び、S の 6 文字目と 7 文字目を入れ替える。S= 0011010 になる。
i=5 を選び、S の 5 文字目と 6 文字目を入れ替える。S= 0011100 になる。

2 回以下の操作ですべての 1 をひとかたまりにすることはできないため、答えは 3 です。

入力例 2

3
100

出力例 2

既にすべての 1 がひとかたまりになっているため、操作は必要ありません。

入力例 3

10
0101001001

出力例 3

Score : 425 points

Problem Statement

You are given a string S of length N consisting of 0 and 1. It is guaranteed that S contains at least one 1.

You may perform the following operation any number of times (possibly zero):

Choose an integer i (1 \leq i \leq N-1) and swap the i-th and (i+1)-th characters of S.

Find the minimum number of operations needed so that all 1s are contiguous.

Here, all 1s are said to be contiguous if and only if there exist integers l and r (1 \leq l \leq r \leq N) such that the i-th character of S is 1 if and only if l \leq i \leq r, and 0 otherwise.

Constraints

2 \leq N \leq 5 \times 10^5
N is an integer.
S is a length N string of 0 and 1.
S contains at least one 1.

Input

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

N
S

Output

Print the answer.

Sample Input 1

7
0101001

Sample Output 1

For example, the following three operations make all 1s contiguous:

Choose i=2 and swap the 2nd and 3rd characters. Then, S= 0011001.
Choose i=6 and swap the 6th and 7th characters. Then, S= 0011010.
Choose i=5 and swap the 5th and 6th characters. Then, S= 0011100.

It is impossible to do this in two or fewer swaps, so the answer is 3.

Sample Input 2

3
100

Sample Output 2

All 1s are already contiguous, so no swaps are needed.

Sample Input 3

10
0101001001

Sample Output 3

E - GCD of Subset

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

長さ N の数列 A=(A_1,A_2,\dots,A_N) と N 以下の正整数 K が与えられます。
i=1,2,\dots,N について次の問題を解いてください。

A_i を含むように K 個の要素を A から選ぶ時、それらの最大公約数 (GCD) としてあり得る最大値を求めてください。

制約

1 \leq K \leq N \leq 1.2 \times 10^6
1 \leq A_i \leq 10^6
入力される値は全て整数

入力

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

N K
A_1 A_2 \dots A_N

出力

N 行出力せよ。j 行目には i=j の時の答えを出力せよ。

入力例 1

5 2
3 4 6 7 12

出力例 1

i=1 の時は A_1 と A_3 を選ぶと最大公約数が \gcd(\lbrace 3, 6 \rbrace) = 3 となり、これが最大です。
i=2 の時は A_2 と A_5 を選ぶと最大公約数が \gcd(\lbrace 4, 12 \rbrace) = 4 となり、これが最大です。
i=3 の時は A_3 と A_5 を選ぶと最大公約数が \gcd(\lbrace 6, 12 \rbrace) = 6 となり、これが最大です。
i=4 の時は A_4 と A_2 を選ぶと最大公約数が \gcd(\lbrace 7, 4 \rbrace) = 1 となり、これが最大です。
i=5 の時は A_5 と A_3 を選ぶと最大公約数が \gcd(\lbrace 12, 6 \rbrace) = 6 となり、これが最大です。

入力例 2

3 3
6 10 15

出力例 2

1
1
1

入力例 3

10 3
414003 854320 485570 52740 833292 625990 909680 885153 435420 221663

出力例 3

Score : 475 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N and a positive integer K (at most N).
For each i = 1, 2, \dots, N, solve the following problem:

When you choose K elements from A that include A_i, find the maximum possible GCD (greatest common divisor) of those chosen elements.

Constraints

1 \leq K \leq N \leq 1.2 \times 10^6
1 \leq A_i \leq 10^6
All input values are integers.

Input

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

N K
A_1 A_2 \dots A_N

Output

Print N lines. The j-th line should contain the answer for i=j.

Sample Input 1

5 2
3 4 6 7 12

Sample Output 1

For i=1, choosing A_1 and A_3 yields \gcd(\lbrace 3,6 \rbrace) = 3, which is the maximum.
For i=2, choosing A_2 and A_5 yields \gcd(\lbrace 4,12 \rbrace) = 4, which is the maximum.
For i=3, choosing A_3 and A_5 yields \gcd(\lbrace 6,12 \rbrace) = 6, which is the maximum.
For i=4, choosing A_4 and A_2 yields \gcd(\lbrace 7,4 \rbrace) = 1, which is the maximum.
For i=5, choosing A_5 and A_3 yields \gcd(\lbrace 12,6 \rbrace) = 6, which is the maximum.

Sample Input 2

3 3
6 10 15

Sample Output 2

1
1
1

Sample Input 3

10 3
414003 854320 485570 52740 833292 625990 909680 885153 435420 221663

Sample Output 3

F - Prefix LIS Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

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

Q 個のクエリを処理してください。 i\ (1\leq i\leq Q) 番目のクエリは以下の通りです：

整数 R_i,X_i が与えられる。数列 (A_1,A_2,\dots,A_{R_i}) の（連続とは限らない）部分列であって、狭義単調増加であり、かつ全ての要素が X_i 以下であるようなものの長さの最大値を求めよ。なお、X_i \geq \min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace が保証される。

制約

1\leq N,Q \leq 2\times 10^5
1\leq A_i \leq 10^9
1\leq R_i\leq N
\min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace\leq X_i\leq 10^9
入力は全て整数

入力

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

N Q
A_1 A_2 \dots A_N
R_1 X_1
R_2 X_2
\vdots
R_Q X_Q

出力

Q 行出力せよ。 i\ (1\leq i \leq Q) 行目には、i 番目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

2
1
2

1 番目のクエリ：数列 (2,4) の狭義単調増加な部分列であって、全ての要素が 5 以下であるようなものの長さの最大値は 2 です。
具体的には、部分列 (2,4) が該当します。
2 番目のクエリ：数列 (2,4,1,3,3) の狭義単調増加な部分列であって、全ての要素が 2 以下であるようなものの長さの最大値は 1 です。
具体的には、部分列 (2) および (1) が該当します。
3 番目のクエリ：数列 (2,4,1,3,3) の狭義単調増加な部分列であって、全ての要素が 3 以下であるようなものの長さの最大値は 2 です。
具体的には、部分列 (2,3) および (1,3) が該当します。

入力例 2

10 8
2 5 6 5 2 1 7 9 7 2
7 8
5 2
2 3
2 6
7 3
8 9
9 6
8 7

出力例 2

Score : 500 points

Problem Statement

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

Answer Q queries. The i-th query (1 \leq i \leq Q) is as follows:

You are given integers R_i and X_i. Consider a subsequence (not necessarily contiguous) of (A_1, A_2, \dots, A_{R_i}) that is strictly increasing and consists only of elements at most X_i. Find the maximum possible length of such a subsequence. It is guaranteed that X_i \geq \min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace.

Constraints

1 \leq N,Q \leq 2 \times 10^5
1 \leq A_i \leq 10^9
1 \leq R_i \leq N
\min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace\leq X_i\leq 10^9
All input values are integers.

Input

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

N Q
A_1 A_2 \dots A_N
R_1 X_1
R_2 X_2
\vdots
R_Q X_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

Sample Output 1

2
1
2

1st query: For the sequence (2,4), the longest strictly increasing subsequence with all elements at most 5 has length 2.
Specifically, (2,4) qualifies.
2nd query: For the sequence (2,4,1,3,3), the longest strictly increasing subsequence with all elements at most 2 has length 1.
Specifically, (2) and (1) qualify.
3rd query: For the sequence (2,4,1,3,3), the longest strictly increasing subsequence with all elements at most 3 has length 2.
Specifically, (2,3) and (1,3) qualify.

Sample Input 2

10 8
2 5 6 5 2 1 7 9 7 2
7 8
5 2
2 3
2 6
7 3
8 9
9 6
8 7

Sample Output 2

G - Unevenness

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 675 点

問題文

縦 N マス、横 N マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と呼びます。(i, j) には整数 A_{i,j} が書かれています。
また、互いに素な正整数 P, Q が与えられます。
あなたは次の操作を 0 回以上自由に行うことが出来ます。ただし、操作により発生するコストの総和が \displaystyle \frac{P}{Q} を超えてはいけません。

正の実数 x を選ぶ。マスを 1 つ選び、選んだマスに書かれている数を x 増やすか x 減らす。この操作にはコストが x かかる。

操作を全て終了した後の (i, j) に書かれている数を B_{i,j} とします。この時、 不揃いさ U を隣接する要素の差分の総和として定義します。厳密に述べると、U は以下の式で定義されます。

\displaystyle U = \sum_{i=1}^N \sum_{j=1}^{N-1} \vert B_{i,j} - B_{i,j+1} \vert + \sum_{i=1}^{N-1} \sum_{j=1}^N \vert B_{i,j} - B_{i+1,j} \vert

U が最小になるように操作を行った時の U の値を出力してください。また、U が最小になるように操作を行った時の B_{i,j} の値としてあり得るものを 1 つ出力してください。

制約

2 \leq N \leq 10
1 \leq P \leq 10^{12}
1 \leq Q \leq 10^{12}
\gcd(P, Q) = 1
0 \leq A_{i,j} \leq 10
入力される値は全て整数

入力

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

N P Q
A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{N,1} A_{N,2} \dots A_{N,N}

出力

U および B_{i,j} を以下の形式で出力せよ。

U
B_{1,1} B_{1,2} \dots B_{1,N}
B_{2,1} B_{2,2} \dots B_{2,N}
\vdots
B_{N,1} B_{N,2} \dots B_{N,N}

出力された U および B_{i,j} が以下の条件を満たす時に正答となる。(U の許容誤差が厳しい点に注意せよ。)

U の真の値との絶対誤差または相対誤差が 2^{-51} (\approx 4.44 \times 10^{-16}) 以下である。
\sum_{i=1}^N \sum_{j=1}^{N-1} \vert B_{i,j} - B_{i,j+1} \vert + \sum_{i=1}^{N-1} \sum_{j=1}^N \vert B_{i,j} - B_{i+1,j} \vert の U との絶対誤差または相対誤差が 10^{-10} 以下である。
\sum_{i=1}^N \sum_{j=1}^N \vert A_{i,j} - B_{i,j}\vert が \displaystyle \frac{P}{Q} + \max \left(1, \frac{P}{Q} \right) \times 10^{-10} 以下である。

答えが複数ある場合は、どれを出力しても正答となる。

入力例 1

出力例 1

24.0000000000000000000
3.0000000000000000000 4.0000000000000000000 1.0000000000000000000
3.0000000000000000000 4.0000000000000000000 2.0000000000000000000
5.0000000000000000000 7.0000000000000000000 9.0000000000000000000

以下の操作を行うと U = 24 になり、これが不揃いさとしてあり得る値の最小です。この時のコストは 2 + 1 = 3 です。

x=2 とする。(1,2) に書かれている数を 2 減らす。
x=1 とする。(2,1) に書かれている数を 1 増やす。

入力例 2

出力例 2

20.5714285714285714281
1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000
1.0000000000000000000 2.7142857142857142857 2.7142857142857142857 2.7142857142857142857 1.0000000000000000000
1.0000000000000000000 2.7142857142857142857 2.7142857142857142857 2.7142857142857142857 1.0000000000000000000
1.0000000000000000000 2.7142857142857142857 2.7142857142857142857 2.7142857142857142857 1.0000000000000000000
1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000

入力例 3

2 393 1
0 0
0 0

出力例 3

0.0000000000000000000
0.0000000000000000000 0.0000000000000000000
0.0000000000000000000 0.0000000000000000000

入力例 4

出力例 4

71.4000000000000000014
4.0000000000000000000 8.0000000000000000000 7.0000000000000000000 5.0000000000000000000 4.0000000000000000000
2.2285714285714285714 6.0000000000000000000 7.0000000000000000000 4.0000000000000000000 5.0000000000000000000
3.0000000000000000000 7.0000000000000000000 1.7428571428571428571 4.0000000000000000000 5.0000000000000000000
4.0000000000000000000 7.0000000000000000000 1.7428571428571428571 5.0000000000000000000 6.0000000000000000000
2.0000000000000000000 1.4857142857142857144 2.0000000000000000000 4.0000000000000000000 6.0000000000000000000

入力例 5

出力例 5

65.4285714285714285685
6.0000000000000000000 3.0000000000000000000 3.0000000000000000000 7.0000000000000000000 9.0000000000000000000
1.0000000000000000000 1.0000000000000000000 5.0000000000000000000 5.0000000000000000000 7.0000000000000000000
7.0000000000000000000 7.0000000000000000000 5.0000000000000000000 5.0000000000000000000 5.0000000000000000000
4.0000000000000000000 4.0000000000000000000 5.0000000000000000000 5.0000000000000000000 5.0238095238095238086
3.0000000000000000000 5.0238095238095238086 5.0000000000000000000 5.0952380952380952371 0.0000000000000000000

入力例 6

10 193926872645 2752096782
5 0 8 0 0 2 6 5 4 5
5 5 5 9 7 0 3 3 6 5
0 0 0 2 7 2 8 0 5 9
4 8 2 5 8 2 4 9 2 0
8 7 3 2 8 4 7 9 8 4
4 1 0 4 9 3 7 5 8 7
1 6 2 6 5 3 5 4 7 9
7 3 7 6 3 9 3 2 2 5
8 9 3 6 3 0 8 6 4 0
0 0 9 7 6 2 1 9 7 6

出力例 6

346.6045935084415210714
5.0000000000000000000 5.0000000000000000000 5.0943878534377365339 0.0000000000000000000 0.0000000000000000000 2.0000000000000000000 5.0314626178125788449 5.0000000000000000000 5.0000000000000000000 5.0000000000000000000
5.0000000000000000000 5.0000000000000000000 5.0000000000000000000 7.0000000000000000000 7.0000000000000000000 2.0000000000000000000 3.0000000000000000000 3.0000000000000000000 5.0000000000000000000 5.0000000000000000000
0.0000000000000000000 0.0000000000000000000 0.0000000000000000000 2.0000000000000000000 7.0000000000000000000 2.0000000000000000000 4.0000000000000000000 3.0000000000000000000 5.0000000000000000000 5.1258504712503153793
4.0000000000000000000 7.0000000000000000000 2.0000000000000000000 5.0000000000000000000 8.0000000000000000000 2.0000000000000000000 4.0000000000000000000 8.0314626178125788445 2.0000000000000000000 2.0000000000000000000
7.0314626178125788445 7.0000000000000000000 3.0000000000000000000 3.0000000000000000000 8.0000000000000000000 4.0000000000000000000 7.0000000000000000000 8.0314626178125788445 8.0000000000000000000 4.0000000000000000000
4.0000000000000000000 2.0000000000000000000 2.0000000000000000000 4.0000000000000000000 8.0000000000000000000 3.0000000000000000000 7.0000000000000000000 5.0000000000000000000 8.0000000000000000000 7.0000000000000000000
4.0000000000000000000 6.0000000000000000000 2.0000000000000000000 6.0000000000000000000 5.0000000000000000000 3.0000000000000000000 5.0000000000000000000 4.0000000000000000000 7.0000000000000000000 7.0629252356251576894
7.0000000000000000000 6.0000000000000000000 6.0000000000000000000 6.0000000000000000000 3.0000000000000000000 3.0000000000000000000 3.0000000000000000000 3.0000000000000000000 3.0000000000000000000 5.0000000000000000000
8.0000000000000000000 8.0000000000000000000 6.0000000000000000000 6.0000000000000000000 3.0000000000000000000 2.0000000000000000000 6.0000000000000000000 6.0000000000000000000 4.0000000000000000000 4.0000000000000000000
0.0000000000000000000 0.0000000000000000000 7.0629252356251576894 7.0000000000000000000 6.0000000000000000000 2.0000000000000000000 2.0000000000000000000 7.0629252356251576894 7.0000000000000000000 6.0000000000000000000

Score : 675 points

Problem Statement

There is a grid with N rows and N columns. Let (i,j) denote the cell at the i-th row and j-th column. (i,j) contains an integer A_{i,j}.
You are also given two coprime positive integers P and Q.

You may perform the following operation any number of times (possibly zero), as long as the total cost does not exceed \displaystyle \frac{P}{Q}:

Choose a positive real number x. Choose one cell in the grid and either increase or decrease the value in that cell by x. This operation incurs a cost of x.

After performing all operations, let B_{i,j} be the value in cell (i,j). Define the non-uniformity U as the sum of absolute differences of adjacent cells. Formally,

\displaystyle U = \sum_{i=1}^N \sum_{j=1}^{N-1} \vert B_{i,j} - B_{i,j+1} \vert + \sum_{i=1}^{N-1} \sum_{j=1}^N \vert B_{i,j} - B_{i+1,j} \vert.

Find the minimum possible value of U after performing the operations in an optimal way, and print that value. Also, print one valid final configuration B_{i,j} that achieves this minimum U.

Constraints

2 \leq N \leq 10
1 \leq P \leq 10^{12}
1 \leq Q \leq 10^{12}
\gcd(P, Q) = 1
0 \leq A_{i,j} \leq 10
All input values are integers.

Input

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

N P Q
A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{N,1} A_{N,2} \dots A_{N,N}

Output

Print U and B_{i,j} in the following format:

U
B_{1,1} B_{1,2} \dots B_{1,N}
B_{2,1} B_{2,2} \dots B_{2,N}
\vdots
B_{N,1} B_{N,2} \dots B_{N,N}

Your output is considered correct if it meets all of the following conditions. (Note that the tolerance for U is very strict.)

The absolute or relative error between your output U and its true minimum value is at most 2^{-51} (\approx 4.44 \times 10^{-16}).
The absolute or relative error between \sum_{i=1}^N \sum_{j=1}^{N-1} \vert B_{i,j} - B_{i,j+1} \vert + \sum_{i=1}^{N-1} \sum_{j=1}^N \vert B_{i,j} - B_{i+1,j} \vert and U is at most 10^{-10}.
\sum_{i=1}^N \sum_{j=1}^N \vert A_{i,j} - B_{i,j}\vert is at most \displaystyle \frac{P}{Q} + \max \left(1, \frac{P}{Q} \right) \times 10^{-10}.

If there are multiple solutions, you may print any one of them.

Sample Input 1

Sample Output 1

24.0000000000000000000
3.0000000000000000000 4.0000000000000000000 1.0000000000000000000
3.0000000000000000000 4.0000000000000000000 2.0000000000000000000
5.0000000000000000000 7.0000000000000000000 9.0000000000000000000

By performing the following operations, we obtain U = 24, which is the minimum possible value. The total cost is 2 + 1 = 3.

Let x = 2. Decrease the value in cell (1,2) by 2.
Let x = 1. Increase the value in cell (2,1) by 1.

Sample Input 2

Sample Output 2

20.5714285714285714281
1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000
1.0000000000000000000 2.7142857142857142857 2.7142857142857142857 2.7142857142857142857 1.0000000000000000000
1.0000000000000000000 2.7142857142857142857 2.7142857142857142857 2.7142857142857142857 1.0000000000000000000
1.0000000000000000000 2.7142857142857142857 2.7142857142857142857 2.7142857142857142857 1.0000000000000000000
1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000 1.0000000000000000000

Sample Input 3

2 393 1
0 0
0 0

Sample Output 3

0.0000000000000000000
0.0000000000000000000 0.0000000000000000000
0.0000000000000000000 0.0000000000000000000

Sample Input 4

Sample Output 4

71.4000000000000000014
4.0000000000000000000 8.0000000000000000000 7.0000000000000000000 5.0000000000000000000 4.0000000000000000000
2.2285714285714285714 6.0000000000000000000 7.0000000000000000000 4.0000000000000000000 5.0000000000000000000
3.0000000000000000000 7.0000000000000000000 1.7428571428571428571 4.0000000000000000000 5.0000000000000000000
4.0000000000000000000 7.0000000000000000000 1.7428571428571428571 5.0000000000000000000 6.0000000000000000000
2.0000000000000000000 1.4857142857142857144 2.0000000000000000000 4.0000000000000000000 6.0000000000000000000

Sample Input 5

Sample Output 5

65.4285714285714285685
6.0000000000000000000 3.0000000000000000000 3.0000000000000000000 7.0000000000000000000 9.0000000000000000000
1.0000000000000000000 1.0000000000000000000 5.0000000000000000000 5.0000000000000000000 7.0000000000000000000
7.0000000000000000000 7.0000000000000000000 5.0000000000000000000 5.0000000000000000000 5.0000000000000000000
4.0000000000000000000 4.0000000000000000000 5.0000000000000000000 5.0000000000000000000 5.0238095238095238086
3.0000000000000000000 5.0238095238095238086 5.0000000000000000000 5.0952380952380952371 0.0000000000000000000

Sample Input 6

10 193926872645 2752096782
5 0 8 0 0 2 6 5 4 5
5 5 5 9 7 0 3 3 6 5
0 0 0 2 7 2 8 0 5 9
4 8 2 5 8 2 4 9 2 0
8 7 3 2 8 4 7 9 8 4
4 1 0 4 9 3 7 5 8 7
1 6 2 6 5 3 5 4 7 9
7 3 7 6 3 9 3 2 2 5
8 9 3 6 3 0 8 6 4 0
0 0 9 7 6 2 1 9 7 6

Sample Output 6

346.6045935084415210714
5.0000000000000000000 5.0000000000000000000 5.0943878534377365339 0.0000000000000000000 0.0000000000000000000 2.0000000000000000000 5.0314626178125788449 5.0000000000000000000 5.0000000000000000000 5.0000000000000000000
5.0000000000000000000 5.0000000000000000000 5.0000000000000000000 7.0000000000000000000 7.0000000000000000000 2.0000000000000000000 3.0000000000000000000 3.0000000000000000000 5.0000000000000000000 5.0000000000000000000
0.0000000000000000000 0.0000000000000000000 0.0000000000000000000 2.0000000000000000000 7.0000000000000000000 2.0000000000000000000 4.0000000000000000000 3.0000000000000000000 5.0000000000000000000 5.1258504712503153793
4.0000000000000000000 7.0000000000000000000 2.0000000000000000000 5.0000000000000000000 8.0000000000000000000 2.0000000000000000000 4.0000000000000000000 8.0314626178125788445 2.0000000000000000000 2.0000000000000000000
7.0314626178125788445 7.0000000000000000000 3.0000000000000000000 3.0000000000000000000 8.0000000000000000000 4.0000000000000000000 7.0000000000000000000 8.0314626178125788445 8.0000000000000000000 4.0000000000000000000
4.0000000000000000000 2.0000000000000000000 2.0000000000000000000 4.0000000000000000000 8.0000000000000000000 3.0000000000000000000 7.0000000000000000000 5.0000000000000000000 8.0000000000000000000 7.0000000000000000000
4.0000000000000000000 6.0000000000000000000 2.0000000000000000000 6.0000000000000000000 5.0000000000000000000 3.0000000000000000000 5.0000000000000000000 4.0000000000000000000 7.0000000000000000000 7.0629252356251576894
7.0000000000000000000 6.0000000000000000000 6.0000000000000000000 6.0000000000000000000 3.0000000000000000000 3.0000000000000000000 3.0000000000000000000 3.0000000000000000000 3.0000000000000000000 5.0000000000000000000
8.0000000000000000000 8.0000000000000000000 6.0000000000000000000 6.0000000000000000000 3.0000000000000000000 2.0000000000000000000 6.0000000000000000000 6.0000000000000000000 4.0000000000000000000 4.0000000000000000000
0.0000000000000000000 0.0000000000000000000 7.0629252356251576894 7.0000000000000000000 6.0000000000000000000 2.0000000000000000000 2.0000000000000000000 7.0629252356251576894 7.0000000000000000000 6.0000000000000000000