Codeforces Round 932 (Div. 2)


A. Entertainment in MAC
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
4
cpm
2
grib
10
kupitimilablodarbuz
1000000000
capybara
6
abacaba
Output
cpm
birggrib
kupitimilablodarbuz
arabypaccapybara
abacaba
----------------------------------------------------------------------------------------------------
B. Informatics in MAC
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
0 0
5
0 1 2 3 4
8
0 1 7 1 0 1 0 3
3
2 2 2
4
0 1 2 0
Output
2
1 1
2 2
-1
3
1 3
4 5
6 8
3
1 1
2 2
3 3
-1
----------------------------------------------------------------------------------------------------
C. Messenger in MAC
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
5 8
4 3
1 5
2 4
4 3
2 3
1 6
4 10
3 12
4 8
2 1
2 12
5 26
24 7
8 28
30 22
3 8
17 17
5 14
15 3
1000000000 998244353
179 239
228 1337
993 1007
Output
3
1
2
1
0
----------------------------------------------------------------------------------------------------
D. Exam in MAC
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
3 3
1 2 3
1 179
57
4 6
0 3 5 6
1 1
1
5 10
0 2 4 8 10
5 10
1 3 5 7 9
4 10
2 4 6 7
3 1000000000
228 1337 998244353
Output
3
16139
10
2
33
36
35
499999998999122959
----------------------------------------------------------------------------------------------------
E. Distance Learning Courses in MAC
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
2
0 1
3 4
3
1 1
1 2
2 2
4
1 7
1 7
3 10
2 2
5
1 3
3 4
2 3
1 4
1 2
6
1 2
2 2
0 1
1 1
3 3
0 0
4
3 4
5 5
2 5
1 2
Output
1 5 4 
15 11 15 15 7 
1 3 3 3 
----------------------------------------------------------------------------------------------------
F. Andrey's Tree
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
5
1 3
1 4
4 5
3 2
5
4 2
4 3
3 5
5 1
5
2 1
1 5
1 4
1 3
Output
1 1
3 4
0 0
1 1
1 2
2 1
3 5
0 0
0 0
0 0
1 1
1 2
1 1
1 2
1 1
1 2
3 3
2 3
4 5
3 4
0 0
0 0
0 0
0 0
----------------------------------------------------------------------------------------------------
