Description

Wufu Street is a straight road. It can be seen as a number line, and the coordinate of each building on the street can be represented by an integer. Xiaoming is a time traveler. He knows that on this street, there are $n$ shops that appear in the past, present, and future. The $i$-th shop can be described by four integers $x_i, t_i, a_i, b_i$, which represent: the shop’s coordinate, the shop’s type, the year it opens, and the year it closes.

Xiaoming wants to time travel to choose a suitable time and live somewhere on Wufu Street. He provides a list of possible choices containing $q$ queries, and each query is represented by a pair (coordinate, time). The $i$-th pair is described by two integers $l_i, y_i$, representing the chosen location $l_i$ and the year $y_i$.

Now, he wants to compute the quality of life for living at these times and locations. He defines the inconvenience index of living as: in the year of living, the distance from the living point to the shop type that is farthest away. The distance from shops of type $t$ to the living point is defined as: in the specified year, among all open shops of type $t$, the distance from the living point to the nearest one. We say shop $i$ is open in year $y$ if and only if $a_i \le y \le b_i$. Note that in some years, not all of the $k$ types of shops may have at least one shop open on Wufu Street. In this case, the inconvenience index is defined as $-1$.

Your task is to help Xiaoming compute the inconvenience index for each (coordinate, time) pair.

Input Format

The first line contains three integers $n, k, q$, representing the number of shops, the number of shop types, and the number of (coordinate, time) pairs. $(1 \leq n, q \le 3\times 10^5, 1 \le k \le n)$.

The next $n$ lines each contain four integers $x_i, t_i, a_i, b_i$ describing a shop, with meanings as stated above. $(1 \le x_i, a_i, b_i \le 10^8, 1 \le t_i \le k, a_i \le b_i)$.

The next $q$ lines each contain two integers $l_i, y_i$, representing a (coordinate, time) query. $(1 \le l_i, y_i \le 10^8)$.

Output Format

Output one line containing $q$ integers, in order, representing the answers for the $q$ (coordinate, time) queries.

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

4
2
-1
-1

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

0
0
-1

1 1 1
100000000 1 1 1
1 1

99999999

Hint

Hint

In the first sample, there are 4 shops, 2 types, and 4 queries.

• For the first query: Xiaoming lives at coordinate 5 in year 3. In this year, shops 1 and 2 are open. The distance to shop 1 is 2, and the distance to shop 2 is 4, so the maximum distance is $4$.
• For the second query: Xiaoming lives at coordinate 5 in year 6. In this year, shops 1 and 3 are open. The distance to shop 1 is 2, and the distance to shop 3 is 2, so the maximum distance is $2$.
• For the third query: Xiaoming lives at coordinate 5 in year 9. In this year, shops 1 and 4 are open. Both are type 1, and there is no open shop of type 2, so the answer is $-1$.
• The same situation occurs in the fourth query.

In the second sample, there are 2 shops, 1 type, and 3 queries. Both shops are type 1. In all queries, Xiaoming lives at coordinate 1. In the first two queries, at least one shop is open, so the answer is $0$. In the third query, neither shop is open, so the answer is $-1$.

In the third sample, there is 1 shop and 1 query, and the distance between them is $99999999$.

Subtasks

• Subtask 1 (points: $5$): $n, q \leq 400$.
• Subtask 2 (points: $7$): $n, q \leq 6 \times 10^4, k \leq 400$.
• Subtask 3 (points: $10$): $n, q \leq 3 \times 10^5$, and for all shops $a_i = 1, b_i = 10^8$.
• Subtask 4 (points: $23$): $n, q \leq 3 \times 10^5$, and for all shops $a_i = 1$.
• Subtask 5 (points: $35$): $n, q \leq 6 \times 10^4$.
• Subtask 6 (points: $20$): $n, q \leq 3 \times 10^5$.

Translated by ChatGPT 5