Aglomerație

You work as a courier in Alba Iulia. The city is represented as a matrix with $N$ rows and $M$ columns. Initially, the congestion level in each intersection (cell) of the matrix is $0$.

Today is City Day, and the city hall has approved $L$ street events. Each event partially blocks a rectangular area, defined by the top-left corner $(r_1, c_1)$ and the bottom-right corner $(r_2, c_2)$, adding a value $X$ to the congestion level of all cells in that area. If the areas overlap, the congestion level is cumulative.

The headquarters of the company where you pick up the packages is located at coordinates $(i_s, j_s)$. Your scooter has a maximum crowd navigation power equal to $K$. This means you cannot enter a cell where the congestion level is strictly greater than $K$.

Traversing from a valid cell to another valid adjacent cell (Up, Down, Left, Right) takes exactly 1 minute.

Task

You received a list of $C$ orders. For each order, you must leave the central headquarters $(i_s, j_s)$ and reach the client located at coordinates $(x, y)$. Calculate the minimum time (in minutes) needed to reach each of the $C$ clients. (Deliveries are independent, it is considered that for each order you always start from the headquarters).

Input data

The first line contains five integer numbers $N, M, L, C$ and $K$.
The second line contains two integer numbers $i_s$ and $j_s$, representing the coordinates of the headquarters.
The next $L$ lines contain five integer numbers each: $r_1, c_1, r_2, c_2$ and $X$, representing the coordinates of the areas where events take place and the added congestion level.
The next $C$ lines contain two integer numbers each $x$ and $y$, representing the coordinates where the clients are waiting.

Output data

You will print $C$ lines. The $i$-th line will contain a single integer number, representing the minimum time needed to reach the $i$-th client. If it is impossible to reach that client, it will print $-1$.

Constraints and clarifications

• $1 \leq N, M \leq 1\,000$
• $1 \leq L, C \leq 100\,000$
• $1 \leq X, K \leq 10^9$
• It is guaranteed that the headquarters $(i_s, j_s)$ has a final congestion level $\leq K$.
• For $30\%$ of the score: $N, M \leq 100$ and $L, C \leq 1\,000$

Example

aglomeratie.in

4 4 2 3 5
4 4
1 1 2 2 4
2 2 3 3 3
1 4
2 2
3 1

aglomeratie.out

3
-1
4

Explanation

The initial matrix has a dimension of $4 \times 4$. The scooter's power limit is $K = 5$. The headquarters is at $(4, 4)$.

After applying the $2$ street events, the congestion matrix looks like this:

4 4 0 0
4 7 3 0
0 3 3 0
0 0 0 0

We observe that cell $(2, 2)$ has a congestion of $7$, so it is completely forbidden because $7 > 5$.

• Client 1 is located at $(1, 4)$: The optimal path is $(4,4) \rightarrow (3,4) \rightarrow (2,4) \rightarrow (1,4)$. Time = $3$ minutes.
• Client 2 is located at $(2, 2)$: It is located in a completely blocked intersection. Time = $-1$.
• Client 3 is located at $(3, 1)$: The path bypasses the crowded center: $(4,4) \rightarrow (4,3) \rightarrow (4,2) \rightarrow (4,1) \rightarrow (3,1)$. Time = $4$ minutes.