Codeforces Round 954 (Div. 3)


A. X Axis
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
1 1 1
1 5 9
8 2 8
10 9 3
2 1 1
2 4 1
7 3 5
1 9 4
Output
0
8
6
7
1
3
4
8
----------------------------------------------------------------------------------------------------
B. Matrix Stabilization
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
1 2
3 1
2 1
1
1
2 2
1 2
3 4
2 3
7 4 5
1 8 10
5 4
92 74 31 74
74 92 17 7
31 17 92 3
74 7 3 92
7 31 1 1
3 3
1000000000 1 1000000000
1 1000000000 1
1000000000 1 1000000000
Output
1 1 
1 
1 
1 2 
3 3 
4 4 5 
1 8 8 
74 74 31 31 
74 74 17 7 
31 17 17 3 
31 7 3 3 
7 7 1 1 
1 1 1 
1 1 1 
1 1 1 
----------------------------------------------------------------------------------------------------
C. Update Queries
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1 2
a
1 1
cb
4 4
meow
1 2 1 4
zcwz
7 4
abacaba
1 3 5 7
damn
7 10
traktor
7 6 5 4 3 2 1 6 4 2
codeforces
Output
b
cwoz
abdcmbn
ccdeefo
----------------------------------------------------------------------------------------------------
D. Mathematical Problem
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
18
2
10
2
74
2
00
2
01
3
901
3
101
5
23311
6
987009
7
1111111
20
99999999999999999999
20
00000000000000000000
4
0212
18
057235283621345395
4
1112
20
19811678487321784121
4
1121
4
2221
3
011
Output
10
74
0
1
9
1
19
0
11
261
0
0
0
12
93
12
24
0
----------------------------------------------------------------------------------------------------
E. Beautiful Array
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
11
1 1000000000
1
2 1
624323799 708290323
3 1
3 2 1
4 1
7 1 5 3
5 1
11 2 15 7 10
7 1
1 8 2 16 8 16 31
13 1
2 1 1 3 3 11 12 22 45 777 777 1500 74
10 2
1 2 1 2 1 2 1 2 1 2
11 2
1 2 1 2 1 2 1 2 1 2 1
13 3
2 3 9 14 17 10 22 20 18 30 1 4 28
5 1
2 3 5 3 5
Output
0
83966524
1
4
6
1
48
-1
0
14
0
----------------------------------------------------------------------------------------------------
F. Non-academic Problem
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
2 1
1 2
3 3
1 2
2 3
1 3
5 5
1 2
1 3
3 4
4 5
5 3
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6
5 5
1 2
1 3
2 3
2 4
3 5
10 12
1 2
1 3
2 3
2 4
4 5
5 6
6 7
7 4
3 8
8 9
9 10
10 8
Output
0
3
4
6
6
21
----------------------------------------------------------------------------------------------------
G1. Permutation Problem (Simple Version)
time limit per test: 3 seconds
memory limit per test: 128 megabytes
input: standard input
output: standard output

Examples
Input
6
1
1
2
1 2
3
2 3 1
5
2 4 1 3 5
12
8 9 7 12 1 10 6 3 2 4 11 5
15
1 2 4 6 8 10 12 14 3 9 15 5 7 11 13
Output
0
1
1
3
9
3
----------------------------------------------------------------------------------------------------
G2. Permutation Problem (Hard Version)
time limit per test: 3 seconds
memory limit per test: 128 megabytes
input: standard input
output: standard output

Examples
Input
6
1
1
2
1 2
3
2 3 1
5
2 4 1 3 5
12
8 9 7 12 1 10 6 3 2 4 11 5
15
1 2 4 6 8 10 12 14 3 9 15 5 7 11 13
Output
0
1
1
3
9
3
----------------------------------------------------------------------------------------------------
