Educational Codeforces Round 10


A. Gabriel and Caterpillar
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10 30
2 1
Output
1
Input
10 13
1 1
Output
0
Input
10 19
1 2
Output
-1
Input
1 50
5 4
Output
1
----------------------------------------------------------------------------------------------------
B. z-sort
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1 2 2 1
Output
1 2 1 2
Input
5
1 3 2 2 5
Output
1 5 2 3 2
----------------------------------------------------------------------------------------------------
C. Foe Pairs
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 2
1 3 2 4
3 2
2 4
Output
5
Input
9 5
9 7 2 3 1 4 6 5 8
1 6
4 5
2 7
7 2
2 7
Output
20
----------------------------------------------------------------------------------------------------
D. Nested Segments
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1 8
2 3
4 7
5 6
Output
3
0
1
0
Input
3
3 4
1 5
2 6
Output
0
1
1
----------------------------------------------------------------------------------------------------
E. Pursuit For Artifacts
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
6 7
1 2 0
2 3 0
3 1 0
3 4 1
4 5 0
5 6 0
6 4 0
1 6
Output
YES
Input
5 4
1 2 0
2 3 0
3 4 0
2 5 1
1 4
Output
NO
Input
5 6
1 2 0
2 3 0
3 1 0
3 4 0
4 5 1
5 3 0
1 2
Output
YES
----------------------------------------------------------------------------------------------------
F. Ants on a Circle
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 4 8
1 R
3 L
Output
1 3
Input
4 8 6
6 R
5 L
1 R
8 L
Output
7 4 2 7
Input
4 8 2
1 R
5 L
6 L
8 R
Output
3 3 4 2
----------------------------------------------------------------------------------------------------
