Problem Description
Mr oops will be killed by lasers if he's in the same column or row as the laser. Thus, he would like to avoid the lasers, by making a sequence of moves to adjacent squares. (4 possible moves) Mr oops is currently at square (x,y), where x can range from 0 to c-1, y can range from 0 to r-1. Note that Mr oops is limited to the boundaries of the grid, he cannot move outside of the grid.
However, the player's fingers are too slow! He can only make m moves before the lasers are deployed.
In a grid with r rows (labelled from 0 to r-1) and c columns (labelled from 0 to c-1), can Mr Oops survive the lasers? If so, output the minimum number of moves required to survive. Otherwise output "-1". Your code must be able to handle multiple test cases (the position of Mr Oops).
Input
The first line will contain 4 integers: r , c, m, tc (rows, columns, maximum number of moves, number of test cases)
The next line will contain 2 integers, h, v, indicating the number of ranges of horizontal and vertical lasers.
The next h lines will contain 2 integers, a and b, indicating that there are horizontal lasers from a to b inclusive.
The next v lines will contain 2 integers, a and b , indicating that there are vertical lasers from a to b inclusive.
The next tc lines will contain 2 integers, x and y, the position of Mr Oops.
Output
tc lines containing an integer, the minimum number of moves required to survive, or -1 if Mr Oops will not survive.
Subtasks
Subtask 1 (12 points): h=1 , v=1 , 100000 ≤ r,c ≤ 1000000 , 1 ≤ tc ≤ 1000000
Subtask 2 (17 points): h ≤ r and v ≤ c, 100000≤ r,c ≤ 1000000, tc = 1
Subtask 3 (32 points): h ≤ r and v ≤ c, 10000 ≤ r,c ≤ 100000 , 1000 ≤ tc ≤ 10000
Subtask 4 (39 points): h ≤ r and v ≤ c, 100000≤ r,c ≤ 1000000 , 100000 ≤ tc ≤ 1000000
Sample Input
6 6 2 3
2 2
0 0
3 3
4 4
5 5
2 3
4 3
5 3
Sample Output
1
2
-1