Codeforces Round 945 (Div. 2)


A. Chess For Three
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
0 0 0
0 1 1
1 1 1
1 1 2
3 3 3
3 4 5
1 1 10
Output
0
1
-1
2
-1
6
2
----------------------------------------------------------------------------------------------------
B. Cat, Fox and the Lonely Array
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
1
0
3
2 2 2
3
1 0 2
5
3 0 1 4 2
5
2 0 4 0 2
7
0 0 0 0 1 2 4
8
0 1 3 2 2 1 0 3
Output
1
1
3
4
4
7
3
----------------------------------------------------------------------------------------------------
C. Cat, Fox and Double Maximum
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
4
1 2 3 4
4
4 3 1 2
6
6 5 1 4 2 3
8
1 2 4 5 7 6 8 3
Output
2 4 1 3
3 1 4 2
2 5 1 4 3 6
5 4 8 2 7 1 6 3
----------------------------------------------------------------------------------------------------
D. Cat, Fox and Maximum Array Split
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
1 1
1
2 2
1
3
1
6 3
7
2
3
6
1
Output
! 1
? 1 1
? 2 1
! -1
? 1 9
? 1 6
? 3 6
? 4 6
! 6
----------------------------------------------------------------------------------------------------
E. Cat, Fox and Swaps
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
2
2 1
3
3 1 2
4
3 2 1 4
5
5 3 1 2 4
5
1 2 3 4 5
6
3 2 1 5 4 6
6
1 3 2 4 5 6
Output
6
11
23
29
55
46
58
----------------------------------------------------------------------------------------------------
F. Maximum GCD Sum Queries
time limit per test: 5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 4
1 2 3
4 5 6
1 1 1
0 1 2 3
Output
2 3 3 3 
Input
5 5
3 4 6 8 4
8 3 4 9 3
10 20 30 40 50
5 55 13 1000 113
Output
2 7 3 7 7 
Input
1 1
3
4
5
0
Output
7 
----------------------------------------------------------------------------------------------------
