P4632 [APIO2018] New Home

**Warning! Abusing the judge for this problem will result in your account being banned! Do not submit repeatedly many times!**

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.

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 one line containing $q$ integers, in order, representing the answers for the $q$ (coordinate, time) queries.

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