Codeforces Round 149 (Div. 2)


A. Heads or Tails
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 2 1 1
Output
3
2 1
3 1
3 2
Input
2 4 2 2
Output
0
----------------------------------------------------------------------------------------------------
B. Big Segment
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
1 1
2 2
3 3
Output
-1
Input
6
1 5
2 3
1 10
7 10
7 7
10 10
Output
3
----------------------------------------------------------------------------------------------------
C. King's Path
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

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

Examples
Input
5 5
2 3
4 1
1 5
5 3
2 1
1 1 2 0 2
Output
2
1 2
Input
4 2
1 2
3 4
0 0 0 0
Output
3
1 3 4
----------------------------------------------------------------------------------------------------
E. XOR on Segment
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3
Output
26
22
0
34
11
Input
6
4 7 4 0 7 3
5
2 2 3 8
1 1 5
2 3 5 1
2 4 5 6
1 2 3
Output
38
28
----------------------------------------------------------------------------------------------------
