#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 12 | 10 | 2s | 32MB | Minimum |

2 | 17 | 50 | 2s | 32MB | Minimum |

3 | 32 | 13 | 2s | 32MB | Minimum |

4 | 39 | 15 | 2s | 32MB | Minimum |

5 | 0 | 1 | 2s | 32MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o mroops -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512