Codeforces Round 706 (Div. 1)


A. Diamond Miner
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
2
0 1
1 0
0 -1
-2 0
4
1 0
3 0
-5 0
6 0
0 3
0 1
0 2
0 4
5
3 0
0 4
0 -3
4 0
2 0
1 0
-3 0
0 -10
0 -2
0 -10
Output
3.650281539872885
18.061819283610362
32.052255376143336
----------------------------------------------------------------------------------------------------
B. Let's Go Hiking
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
1 2 5 4 3
Output
1
Input
7
1 2 4 6 5 3 7
Output
0
----------------------------------------------------------------------------------------------------
C. Garden of the Sun
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
3 3
X.X
...
X.X
4 4
....
.X.X
....
.X.X
5 5
.X...
....X
.X...
.....
X.X.X
1 10
....X.X.X.
2 2
..
..
Output
XXX
..X
XXX
XXXX
.X.X
.X..
.XXX
.X...
.XXXX
.X...
.X...
XXXXX
XXXXXXXXXX
..
..
----------------------------------------------------------------------------------------------------
D. BFS Trees
time limit per test: 2.5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4 4
1 2
2 3
3 4
1 4
Output
2 1 0 1
1 2 1 0
0 1 2 1
1 0 1 2
Input
8 9
1 2
1 3
1 4
2 7
3 5
3 6
4 8
2 3
3 4
Output
1 0 0 0 0 0 0 0
0 2 0 0 0 0 2 0
0 0 1 0 1 1 0 0
0 0 0 2 0 0 0 2
0 0 1 0 1 1 0 0
0 0 1 0 1 1 0 0
0 2 0 0 0 0 2 0
0 0 0 2 0 0 0 2
----------------------------------------------------------------------------------------------------
E. Qingshan and Daniel
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
3
1 5 2 3
2 7 1 2
3 2 1 1
Output
100
Input
5000000
2
1919810 998244353 114514 19260817
5000000 233333333 623532 7175
Output
800210675
Input
1
1
1 1 0 0
Output
1
----------------------------------------------------------------------------------------------------
F. Squares
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 2
2 1 3
10 -5 4
3 -2 3
1
2
Output
6
8
Input
5 4
2 1 5 3 4
6 -5 3 -10 -1
0 3 2 7 2
1
2
3
2
Output
-8
-7
-7
-8
----------------------------------------------------------------------------------------------------
