Codeforces Round 949 (Div. 2)


A. Turtle and Piggy Are Playing a Game
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2 4
3 6
2 15
6 22
114514 1919810
Output
2
2
3
4
20
----------------------------------------------------------------------------------------------------
B. Turtle and an Infinite Sequence
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
9
0 0
0 1
0 2
1 0
5 2
10 1
20 3
1145 14
19198 10
Output
0
1
3
1
7
11
23
1279
19455
----------------------------------------------------------------------------------------------------
C. Turtle and an Incomplete Sequence
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
9
8
-1 -1 -1 2 -1 -1 1 -1
4
-1 -1 -1 -1
6
3 -1 -1 -1 9 -1
4
-1 5 -1 6
4
2 -1 -1 3
4
1 2 3 4
2
4 2
5
-1 3 -1 3 6
13
-1 -1 3 -1 -1 -1 -1 7 -1 -1 3 -1 -1
Output
4 9 4 2 4 2 1 2
7 3 6 13
3 1 2 4 9 18
-1
-1
-1
4 2
6 3 1 3 6
3 1 3 1 3 7 3 7 3 1 3 1 3
----------------------------------------------------------------------------------------------------
D. Turtle and Multiplication
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
2
3
4
Output
114514 114514
1 2 2
3 3 4 4
----------------------------------------------------------------------------------------------------
E. Turtle and Intersected Segments
time limit per test: 5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
5
1 7 3
2 4 6
3 5 5
6 7 9
3 4 4
5
2 7 3
1 3 6
4 5 5
6 7 9
1 1 4
4
1 4 3
1 2 1
3 4 5
1 4 4
3
1 3 1
2 3 3
4 5 8
Output
9
13
4
-1
----------------------------------------------------------------------------------------------------
F. Turtle and Paths on a Tree
time limit per test: 4 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

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