AtCoder Beginner Contest 395

A - Strictly Increasing?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

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

A が狭義単調増加であるとは、 1\leq i\lt N なるすべての整数 i について A_i\lt A_{i+1} が成り立つことをを指します。

A が狭義単調増加であるか判定してください。

制約

2\leq N\leq 100
1\leq A_i\leq 1000 (1\leq i\leq N)
入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

A が狭義単調増加であるならば Yes と、そうでないならば No と出力せよ。

正誤判定器は大文字と小文字を区別せず、どちらも受理する。例えば、答えが Yes となるときに yes や YES、yEs などと出力しても正解と判定される。

入力例 1

3
1 2 5

出力例 1

Yes

A_1\lt A_2 かつ A_2\lt A_3 なので A は狭義単調増加です。

入力例 2

3
3 9 5

出力例 2

No

A_1\lt A_2 ですが、A_2\lt A_3 でないので A は狭義単調増加ではありません。

入力例 3

10
1 1 2 3 5 8 13 21 34 55

出力例 3

No

A_1\lt A_2 でないので A は狭義単調増加ではありません。

Score : 100 points

Problem Statement

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

Determine whether A is strictly increasing, that is, whether A_i < A_{i+1} holds for every integer i with 1 \leq i < N.

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 1000 \ (1 \leq i \leq N)
All input values are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

If A is strictly increasing, print Yes; otherwise, print No.

The judge is case-insensitive. For example, if the correct answer is Yes, any of yes, YES, and yEs will be accepted.

Sample Input 1

3
1 2 5

Sample Output 1

Yes

A_1 < A_2 and A_2 < A_3, so A is strictly increasing.

Sample Input 2

3
3 9 5

Sample Output 2

No

A_1 < A_2, but A_2 < A_3 does not hold, so A is not strictly increasing.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

No

A_1 < A_2 does not hold, so A is not strictly increasing.

B - Make Target

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

概要：以下のような N\times N の模様を作成してください。
###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

正整数 N が与えられます。

N\times N のグリッドがあります。このグリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表します。はじめ、どのマスにも色は塗られていません。

これから、i=1,2,\dots,N の順に、以下の操作を行います。

j=N+1-i とする。
i\leq j であるならば、i が奇数ならば黒、偶数ならば白で、マス (i,i) を左上、マス (j,j) を右下とする矩形領域に含まれるマスを塗りつぶす。このとき、既に色が塗られているマスについては色を上書きする。
i\gt j であるならば、何もしない。

すべての操作を行った後、色が塗られていないマスが存在しないことが証明できます。最終的に各マスがどの色で塗られているかを求めてください。

制約

1\leq N\leq 50
入力はすべて整数

入力

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

出力

N 行出力せよ。i 行目には、最終的にグリッドの i 行目に塗られている色を以下のような長さ N の文字列 S_i として出力せよ。入出力例も参考にすること。

マス (i,j) が最終的に黒で塗られているならば、S_i の j 文字目は # である。
マス (i,j) が最終的に白で塗られているならば、S_i の j 文字目は . である。

入力例 1

出力例 1

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

概要で示した模様と同じです。

入力例 2

出力例 2

#####
#...#
#.#.#
#...#
#####

以下のように色が塗られます。ここで、まだ色が塗られていないマスを ? と表します。

         i=1      i=2      i=3      i=4      i=5
?????    #####    #####    #####    #####    #####
?????    #####    #...#    #...#    #...#    #...#
????? -> ##### -> #...# -> #.#.# -> #.#.# -> #.#.#
?????    #####    #...#    #...#    #...#    #...#
?????    #####    #####    #####    #####    #####

入力例 3

出力例 3

########
#......#
#.####.#
#.#..#.#
#.#..#.#
#.####.#
#......#
########

入力例 4

出力例 4

##
##

Score : 200 points

Problem Statement

Overview: Create an N \times N pattern as follows.

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

You are given a positive integer N.

Consider an N \times N grid. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left. Initially, no cell is colored.

Then, for i = 1,2,\dots,N in order, perform the following operation:

Let j = N + 1 - i.
If i \leq j, fill the rectangular region whose top-left cell is (i,i) and bottom-right cell is (j,j) with black if i is odd, or white if i is even. If some cells are already colored, overwrite their colors.
If i > j, do nothing.

After all these operations, it can be proved that there are no uncolored cells. Determine the final color of each cell.

Constraints

1 \leq N \leq 50
All input values are integers.

Input

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

Output

Print N lines. The i-th line should contain a length-N string S_i representing the colors of the i-th row of the grid after all operations, as follows:

If cell (i,j) is finally colored black, the j-th character of S_i should be #.
If cell (i,j) is finally colored white, the j-th character of S_i should be ..

Sample Input 1

Sample Output 1

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

This matches the pattern shown in the Overview.

Sample Input 2

Sample Output 2

#####
#...#
#.#.#
#...#
#####

Colors are applied as follows, where ? denotes a cell not yet colored:

         i=1      i=2      i=3      i=4      i=5
?????    #####    #####    #####    #####    #####
?????    #####    #...#    #...#    #...#    #...#
????? -> ##### -> #...# -> #.#.# -> #.#.# -> #.#.#
?????    #####    #...#    #...#    #...#    #...#
?????    #####    #####    #####    #####    #####

Sample Input 3

Sample Output 3

########
#......#
#.####.#
#.#..#.#
#.#..#.#
#.####.#
#......#
########

Sample Input 4

Sample Output 4

##
##

C - Shortest Duplicate Subarray

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

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

A の空でない連続部分列であって、同じ値を複数個含むようなものが存在するか判定してください。存在するならばそのようなもののうち最も短いものの長さを求めてください。

制約

1\leq N\leq 2\times 10^5
1\leq A_i\leq 10^6 (1\leq i\leq N)
入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

問題文中の条件を満たす連続部分列が存在しないならば -1 と出力せよ。存在するならば、そのようなもののうち最も短いものの長さを出力せよ。

入力例 1

5
3 9 5 3 1

出力例 1

(3,9,5,3) と (3,9,5,3,1) が条件を満たします。短いのは (3,9,5,3) で、その長さは 4 です。

入力例 2

4
2 5 3 1

出力例 2

-1

条件を満たす連続部分列は存在しません。

入力例 3

10
1 1 2 3 5 8 13 21 34 55

出力例 3

Score : 300 points

Problem Statement

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

Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^6 \ (1 \leq i \leq N)
All input values are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

If there is no (contiguous) subarray satisfying the condition in the problem statement, print -1. Otherwise, print the length of the shortest such subarray.

Sample Input 1

5
3 9 5 3 1

Sample Output 1

(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.

Sample Input 2

4
2 5 3 1

Sample Output 2

-1

There is no subarray that satisfies the condition.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

D - Pigeon Swap

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

鳩 1, 鳩 2,\ldots, 鳩 N の N 羽の鳩と、巣 1, 巣 2,\ldots, 巣 N の N 個の巣があります。

はじめ、鳩 i (1\leq i\leq N) は巣 i にいます。

鳩たちに対して Q 回の操作を行います。

操作は次の 3 種類のうちのいずれかです。

種類 1 : 整数 a,b (1\leq a\leq N,1\leq b\leq N) が与えられる。鳩 a を今いる巣から取り出し、巣 b へ移動する。
種類 2 : 整数 a,b (1\leq a\lt b\leq N) が与えられる。巣 a にいる鳩をすべて巣 b へ移動し、巣 b にいる鳩をすべて巣 a へ移動する。これら 2 つの移動は一斉に行われる。
種類 3 : 整数 a (1\leq a\leq N) が与えられる。鳩 a が今いる巣の番号を報告する。

Q 回の操作を順に行ったときの、種類 3 の各操作における報告の結果を出力してください。

制約

1\leq N\leq10 ^ 6
1\leq Q\leq3\times10 ^ 5
入力される操作はすべて種類 1, 種類 2, 種類 3 のいずれかである。
入力される操作は問題文中の制約を満たす。
入力される操作のうちに種類 3 の操作が 1 つ以上含まれる。
入力はすべて整数

入力

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

N Q
op _ 1
op _ 2
\vdots
op _ Q

ただし、i+1 行目の入力 op _ i は i 番目の操作を表しており、op _ i は次のいずれかの形式である。

i 番目の操作が種類 1 の操作のとき、i+1 行目は次の形式で与えられる。

1 a b

これは、与えられる整数を a と b として種類 1 の操作を行うことを表している。

i 番目の操作が種類 2 の操作のとき、i+1 行目は次の形式で与えられる。

2 a b

これは、与えられる整数を a と b として種類 2 の操作を行うことを表している。

i 番目の操作が種類 3 の操作のとき、i+1 行目は次の形式で与えられる。

3 a

これは、与えられる整数を a として種類 3 の操作を行うことを表している。

出力

与えられる種類 3 の操作の個数を q 個として、q 行にわたって出力せよ。

i 行目 (1\leq i\leq q) には、種類 3 の操作のうち i 番目の操作で報告される巣の番号を出力せよ。

入力例 1

出力例 1

与えられる操作で、鳩は以下の図のように移動します。

種類 3 の操作でそれぞれ報告すべき巣の番号は 4,5,2,5 なので、4 5 2 5 を 4 行にわたって出力してください。

入力例 2

1 2
1 1 1
3 1

出力例 2

種類 1 の操作で、鳩を取り出した巣にそのまま戻す場合もあります。

入力例 3

出力例 3

3
15
7

Score : 350 points

Problem Statement

There are N pigeons labeled 1, 2, \ldots, N and N nests labeled 1, 2, \ldots, N.

Initially, pigeon i (1 \leq i \leq N) is in nest i.

You will perform Q operations on these pigeons.

There are three types of operations:

Type 1: You are given integers a and b (1 \leq a \leq N, 1 \leq b \leq N). Take pigeon a out of its current nest and move it to nest b.
Type 2: You are given integers a and b (1 \leq a < b \leq N). Move all pigeons in nest a to nest b, and move all pigeons in nest b to nest a. These two moves happen simultaneously.
Type 3: You are given an integer a (1 \leq a \leq N). Pigeon a reports the label of the nest it is currently in.

Print the result of each Type 3 operation in the order the operations are given.

Constraints

1 \leq N \leq 10^6
1 \leq Q \leq 3 \times 10^5
Every operation is of Type 1, 2, or 3.
All operations are valid according to the problem statement.
There is at least one Type 3 operation.
All input values are integers.

Input

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

N Q
op _ 1
op _ 2
\vdots
op _ Q

Here, op _ i on the line i+1 represents the i-th operation in one of the following formats.

If the i-th operation is of Type 1, op _ i is in the following format:

1 a b

This corresponds to a Type 1 operation with the given integers being a and b.

If the i-th operation is of Type 2, op _ i is in the following format:

2 a b

This corresponds to a Type 2 operation with the given integers being a and b.

If the i-th operation is of Type 3, op _ i is in the following format:

3 a

This corresponds to a Type 3 operation with the given integer being a.

Output

Let the number of Type 3 operations be q. Print q lines. The i-th line (1 \leq i \leq q) should contain the nest number reported in the i-th Type 3 operation.

Sample Input 1

Sample Output 1

In the operations given, the pigeons move as shown in the figure below:

The nest numbers to be reported for the Type 3 operations are 4,5,2,5. Print 4, 5, 2, 5 on separate lines.

Sample Input 2

1 2
1 1 1
3 1

Sample Output 2

The destination nest of a Type 1 operation may be the same as the nest the pigeon is currently in.

Sample Input 3

Sample Output 3

3
15
7

E - Flip Edge

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

N 頂点 M 辺の有向グラフが与えられます。 i 番目 (1\leq i\leq M) の辺は頂点 u _ i から頂点 v _ i への有向辺です。

はじめ、あなたは頂点 1 におり、以下の操作を繰り返して頂点 N にたどり着きたいです。

次の操作のうちのいずれかを行う。
- 今いる頂点から辺をたどって移動する。コストが 1 かかる。より厳密には、今いる頂点を v として、v から u への有向辺が存在するような u を 1 つ選び、頂点 u へ移動する。
- すべての辺の向きを反転する。コストが X かかる。より厳密には、この操作の直前に v から u への有向辺が存在しているとき、かつそのときに限り、この操作の直後に u から v への有向辺が存在する。

与えられるグラフにおいて、上の操作を繰り返して頂点 1 から頂点 N にたどり着くことができることが保証されます。

頂点 N にたどりつくまでにかかるコストの総和の最小値を求めてください。

制約

2\leq N\leq2\times10 ^ 5
1\leq M\leq2\times10 ^ 5
1\leq X\leq10 ^ 9
1\leq u _ i\leq N\ (1\leq i\leq M)
1\leq v _ i\leq N\ (1\leq i\leq M)
与えられるグラフにおいて、上記の操作を繰り返して頂点 1 から頂点 N にたどり着くことができる。
入力はすべて整数

入力

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

N M X
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

出力

頂点 N にたどりつくまでにかかるコストの総和の最小値を出力せよ。

入力例 1

出力例 1

与えられたグラフは以下のようになります。

次のように操作を行うことで、コストの総和を 4 として頂点 5 にたどり着くことができます。

コストを 1 かけて頂点 2 に移動する。
コストを 1 かけて頂点 4 に移動する。
コストを 1 かけて頂点 3 に移動する。
コストを 1 かけて頂点 5 に移動する。

コストの総和を 3 以下として頂点 5 にたどり着くことはできないため、4 を出力してください。

入力例 2

出力例 2

与えられたグラフは入出力例 1 と同じですが、辺を反転させるのにかかるコストが異なります。

次のように操作を行うことで、コストの総和を 3 として頂点 5 にたどり着くことができます。

コストを 1 かけて頂点 2 に移動する。
コストを 1 かけてすべての辺を反転させる。
コストを 1 かけて頂点 5 に移動する。

コストの総和を 2 以下として頂点 5 にたどり着くことはできないため、3 を出力してください。

入力例 3

8 7 613566756
2 1
2 3
4 3
4 5
6 5
6 7
8 7

出力例 3

4294967299

答えが 32\operatorname{bit} 整数に収まらない場合があることに注意してください。

入力例 4

出力例 4

Score : 425 points

Problem Statement

You are given a directed graph with N vertices and M edges. The i-th edge (1 \leq i \leq M) is a directed edge from vertex u _ i to vertex v _ i.

Initially, you are at vertex 1. You want to repeat the following operations until you reach vertex N:

Perform one of the two operations below:
- Move along a directed edge from your current vertex. This incurs a cost of 1. More precisely, if you are at vertex v, choose a vertex u such that there is a directed edge from v to u, and move to vertex u.
- Reverse the direction of all edges. This incurs a cost of X. More precisely, if and only if there was a directed edge from v to u immediately before this operation, there is a directed edge from u to v immediately after this operation.

It is guaranteed that, for the given graph, you can reach vertex N from vertex 1 by repeating these operations.

Find the minimum total cost required to reach vertex N.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq M \leq 2 \times 10^5
1 \leq X \leq 10^9
1 \leq u _ i \leq N \ (1 \leq i \leq M)
1 \leq v _ i \leq N \ (1 \leq i \leq M)
For the given graph, it is guaranteed that you can reach vertex N from vertex 1 by the operations described.
All input values are integers.

Input

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

N M X
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

Output

Print the minimum total cost required to reach vertex N.

Sample Input 1

Sample Output 1

The given graph looks like this:

You can reach vertex 5 with a total cost of 4 by doing the following:

Move to vertex 2 at a cost of 1.
Move to vertex 4 at a cost of 1.
Move to vertex 3 at a cost of 1.
Move to vertex 5 at a cost of 1.

It is impossible to reach vertex 5 with a total cost of 3 or less, so print 4.

Sample Input 2

Sample Output 2

The graph is the same as in Sample 1, but the cost to reverse edges is different.

You can reach vertex 5 with a total cost of 3 as follows:

Move to vertex 2 at a cost of 1.
Reverse all edges at a cost of 1.
Move to vertex 5 at a cost of 1.

It is impossible to reach vertex 5 with a total cost of 2 or less, so print 3.

Sample Input 3

8 7 613566756
2 1
2 3
4 3
4 5
6 5
6 7
8 7

Sample Output 3

4294967299

Note that the answer may exceed the 32-bit integer range.

Sample Input 4

Sample Output 4

F - Smooth Occlusion

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

高橋くんには歯が 2N 本あり、N 本は上の歯、残りの N 本は下の歯です。

左から i 本目 (1\leq i\leq N) の上の歯の長さは U _ i で、左から i 本目 (1\leq i\leq N) の下の歯の長さは D _ i です。

高橋くんの歯が次の 2 つの条件をどちらも満たしているとき、歯が「うまく噛み合っている」ということにします。

ある整数 H が存在し、1\leq i\leq N を満たすすべての整数 i について、U _ i+D _ i=H が成り立つ。
1\leq i\lt N を満たすすべての整数 i について、\vert U _ i-U _ {i+1}\vert\leq X が成り立つ。

高橋くんは次の操作を好きなだけ繰り返すことができます。

1 円を支払って歯削り機を使い、長さが正であるような歯を 1 つ選んでその歯の長さを 1 減らす。

この操作以外の方法で歯の長さを変えることはできません。

高橋くんが歯をうまく噛み合わせるために支払うことになる最小の金額を求めてください。

制約

2\leq N\leq2\times10 ^ 5
1\leq U _ i\leq10 ^ 9\ (1\leq i\leq N)
1\leq D _ i\leq10 ^ 9\ (1\leq i\leq N)
1\leq X\leq10 ^ 9
入力はすべて整数

入力

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

N X
U _ 1 D _ 1
U _ 2 D _ 2
\vdots
U _ N D _ N

出力

答えを出力せよ。

入力例 1

出力例 1

はじめ、高橋くんのそれぞれの歯の高さは以下のようになっています。

たとえば、以下のようにして高橋くんの歯をうまく噛み合わせることができます。

15 円を支払うことでそれぞれの歯をこの長さにすることができます。

14 円以下を支払って高橋くんの歯をうまく噛み合わせることはできないため、15 を出力してください。

入力例 2

4 1000000000
3 3
3 3
3 3
3 3

出力例 2

歯の長さを変えなくてもうまく噛み合っている場合があります。

入力例 3

4 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1 1

出力例 3

5999999994

答えが 32\operatorname{bit} 整数に収まらない場合があることに注意してください。

入力例 4

出力例 4

Score : 500 points

Problem Statement

Takahashi has 2N teeth: N upper teeth and N lower teeth.

The length of the i-th upper tooth from the left (1 \leq i \leq N) is U _ i, and the length of the i-th lower tooth from the left (1 \leq i \leq N) is D _ i.

His teeth are said to “fit together well” if both of the following conditions are satisfied:

There exists an integer H such that U _ i + D _ i = H for every integer i with 1 \leq i \leq N.
\lvert U _ i - U _ {i+1} \rvert \leq X for every integer i with 1 \leq i < N.

He can perform the following operation any number of times:

Pay 1 yen to use a tooth-grinding machine, choose exactly one tooth whose length is positive, and reduce its length by 1.

No other method may be used to change the lengths of the teeth.

Find the minimum total amount of money he needs to pay to make his teeth fit together well.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq U _ i \leq 10^9 \ (1 \leq i \leq N)
1 \leq D _ i \leq 10^9 \ (1 \leq i \leq N)
1 \leq X \leq 10^9
All input values are integers.

Input

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

N X
U _ 1 D _ 1
U _ 2 D _ 2
\vdots
U _ N D _ N

Output

Print the answer.

Sample Input 1

Sample Output 1

Initially, Takahashi’s teeth have the following lengths:

For example, you can make them fit together well in the following way:

It costs 15 yen to achieve these lengths.

It is impossible to make them fit together well with 14 yen or less, so print 15.

Sample Input 2

4 1000000000
3 3
3 3
3 3
3 3

Sample Output 2

It is possible that the teeth already fit together well without any changes.

Sample Input 3

4 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1 1

Sample Output 3

5999999994

Note that the answer may exceed the 32-bit integer range.

Sample Input 4

Sample Output 4

G - Minimum Steiner Tree 2

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 625 点

問題文

正整数 N,K が与えられます。また、N\times N 行列 C=(C_{i,j}) (1\leq i,j\leq N) が与えられます。ここで、C_{i,i}=0,C_{i,j}=C_{j,i} が保証されます。

頂点に 1,2,\dots,N と番号がつけられた N 頂点の重み付き完全グラフがあります。i\lt j なる頂点の組 i,j について、頂点 i と頂点 j を結ぶ辺の重みは C_{i,j} です。

Q 個のクエリが与えられます。i 番目のクエリでは K+1 以上 N 以下の相異なる整数の組 s_i,t_i が与えられるので、以下の問題を解いてください。

このグラフから 0 個以上好きな個数辺と頂点を取り除いてできる連結なグラフのうち、頂点 1,2,\dots,K,s_i,t_i をすべて含むようなものを良いグラフとよびます。

良いグラフのコストを、グラフに含まれる辺の重みの総和とします。

良いグラフのコストの最小値を求めてください。

制約

3\leq N\leq 80
1\leq K\leq \min(N-2,\textcolor{red}{8})
0\leq C_{i,j}\leq 10^9 (1\leq i,j\leq N,i\ne j)
C_{i,j}=C_{j,i} (1\leq i,j\leq N,i\ne j)
C_{i,i}=0 (1\leq i\leq N)
1\leq Q\leq 5000
K+1\leq s_i,t_i\leq N (1\leq i\leq Q)
s_i\ne t_i (1\leq i\leq Q)
入力はすべて整数

入力

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

N K
C_{1,1} C_{1,2} \dots C_{1,N}
C_{2,1} C_{2,2} \dots C_{2,N}
\vdots
C_{N,1} C_{N,2} \dots C_{N,N}
Q
s_1 t_1
s_2 t_2
\vdots
s_Q t_Q

出力

Q 行出力せよ。

i 行目には、i 番目のクエリの答えを出力せよ。

入力例 1

5 2
0 395 395 1 1
395 0 1 395 1
395 1 0 395 1
1 395 395 0 1
1 1 1 1 0
3
3 4
3 5
4 5

出力例 1

4
3
3

i 番目の頂点と j 番目の頂点を結ぶ辺を辺 i-j と表記します。

1 番目のクエリについて、以下の頂点と辺を残しそれ以外を消すのが最適で、このときのグラフのコストは 4 です。

頂点 1,2,3,4,5
辺 1-4,2-3,3-5,4-5

2 番目のクエリについて、以下の頂点と辺を残しそれ以外を消すのが最適で、このときのグラフのコストは 3 です。

頂点 1,2,3,5
辺 1-5,2-3,3-5

入力例 2

9 5
0 344670307 744280520 967824729 322288793 152036485 628902494 596982638 853214705
344670307 0 249168130 769431650 532405020 981520310 755031424 86416231 284114341
744280520 249168130 0 80707350 256358888 620411718 713892371 272961036 836365490
967824729 769431650 80707350 0 45539861 298766521 722757772 623807668 366719378
322288793 532405020 256358888 45539861 0 361324668 69837030 222135106 935147464
152036485 981520310 620411718 298766521 361324668 0 486834509 225447688 859904884
628902494 755031424 713892371 722757772 69837030 486834509 0 434140395 490910900
596982638 86416231 272961036 623807668 222135106 225447688 434140395 0 22078599
853214705 284114341 836365490 366719378 935147464 859904884 490910900 22078599 0
20
9 7
8 9
9 8
7 6
9 8
8 9
9 7
7 8
7 8
6 9
9 8
9 6
8 6
8 9
6 8
8 7
7 6
8 9
7 6
9 6

出力例 2

Score : 625 points

Problem Statement

You are given positive integers N, K, and an N \times N matrix C=(C_{i,j}) (1\leq i,j\leq N). It is guaranteed that C_{i,i} = 0 and C_{i,j} = C_{j,i}.

There is a weighted complete graph with N vertices labeled 1,2,\dots,N. For each pair of vertices i and j with i\lt j, the weight of the edge connecting vertices i and j is C_{i,j}.

You have Q queries. In the i-th query, you are given a pair of distinct integers s_i and t_i (both between K+1 and N, inclusive), for which you must solve the following problem.

A good graph is a connected graph containing all of the vertices 1,2,\dots,K,s_i,t_i obtained by removing any number of edges and vertices (possibly zero) from the graph above.

The cost of a good graph is the sum of the weights of its edges.

Find the minimum possible cost of a good graph.

Constraints

3 \leq N \leq 80
1\leq K\leq \min(N-2,\textcolor{red}{8})
0 \leq C_{i,j} \leq 10^9 \ (1 \leq i,j \leq N, i \ne j)
C_{i,j} = C_{j,i} \ (1 \leq i,j \leq N, i \ne j)
C_{i,i} = 0 \ (1 \leq i \leq N)
1 \leq Q \leq 5000
K+1 \leq s_i, t_i \leq N \ (1 \leq i \leq Q)
s_i \ne t_i \ (1 \leq i \leq Q)
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} \dots C_{1,N}
C_{2,1} C_{2,2} \dots C_{2,N}
\vdots
C_{N,1} C_{N,2} \dots C_{N,N}
Q
s_1 t_1
s_2 t_2
\vdots
s_Q t_Q

Output

Print Q lines.

The i-th line should contain the answer for the i-th query.

Sample Input 1

5 2
0 395 395 1 1
395 0 1 395 1
395 1 0 395 1
1 395 395 0 1
1 1 1 1 0
3
3 4
3 5
4 5

Sample Output 1

4
3
3

Let “edge i-j” denote the edge connecting vertices i and j.

For the first query, it is optimal to keep the following vertices and edges, and remove all others. The cost is 4.

Vertices 1,2,3,4,5
Edges 1-4,2-3,3-5,4-5

For the second query, it is optimal to keep the following vertices and edges, and remove all others. The cost is 3.

Vertices 1,2,3,5
Edges 1-5,2-3,3-5

Sample Input 2

9 5
0 344670307 744280520 967824729 322288793 152036485 628902494 596982638 853214705
344670307 0 249168130 769431650 532405020 981520310 755031424 86416231 284114341
744280520 249168130 0 80707350 256358888 620411718 713892371 272961036 836365490
967824729 769431650 80707350 0 45539861 298766521 722757772 623807668 366719378
322288793 532405020 256358888 45539861 0 361324668 69837030 222135106 935147464
152036485 981520310 620411718 298766521 361324668 0 486834509 225447688 859904884
628902494 755031424 713892371 722757772 69837030 486834509 0 434140395 490910900
596982638 86416231 272961036 623807668 222135106 225447688 434140395 0 22078599
853214705 284114341 836365490 366719378 935147464 859904884 490910900 22078599 0
20
9 7
8 9
9 8
7 6
9 8
8 9
9 7
7 8
7 8
6 9
9 8
9 6
8 6
8 9
6 8
8 7
7 6
8 9
7 6
9 6

Sample Output 2