2585 [APIO 2018] New Home

Wu-Fu Street is an incredibly straight street that can be described as a one-dimensional number line, and each building’s location on the street can be represented with just one number. Xiao-Ming the TimeTraveler knows that there are n stores of k store-types that had opened, has opened, or will open on the street. The $i$-th store can be described with four integers: $x_i,$ $t_i,$ $a_i,$ $b_i,$ representing the store’s location, the store’s type, the year when it starts its business, and the year when it is closed.

Xiao-Ming the Time Traveler wants to choose a certain year and a certain location on Wu-Fu Street to live in. He has narrowed down his preference list to $q$ location-year pairs. The $i$-th pair can be described with two integers: $l_i,$ $y_i,$ representing the location and the year of the pair. Now he wants to evaluate the life quality of these pairs. He defines the inconvenience index of a location-year pair to be the inaccessibility of the most inaccessible store-type of that pair. The inaccessibility of a location-year pair to store-type $t$ is defined as the distance from the location to the nearest type-$t$ store that is open in the year. We say the $i$-th store is open in the year $y$ if $a_i ≤ y ≤ b_i.$ Note that in some years, Wu-Fu Street may not have all the $k$ store-types on it. In that case, the inconvenience index is defined as $−1$.

Your task is to help Xiao-Ming find out the inconvenience index of each location-year pair.

The first line of input contains integer numbers $n,$ $k,$ and $q$: number of stores, number of types and number of queries $(1 ≤ n, q ≤ 3\cdot 10^5, 1 ≤ k ≤ n)$.

Next $n$ lines contain descriptions of stores. Each description is four integers: $x_i,$ $t_i,$ $a_i,$ and $b_i$ $(1 ≤ x_i, a_i, b_i ≤ 10^8,$ $1 ≤ t_i ≤ k,$ $a_i ≤ b_i)$.

Next $q$ lines contain the queries. Each query is two integers: $l_i$, and $yi$ $(1 ≤ l_i,$ $y_i ≤ 10^8)$.

Output $q$ integers: for each query output its the inconvenience index.

In the first example there are four stores, two types, and four queries. - First query: Xiao-Ming lives in location 5 in year 3. In this year, stores 1 and 2 are open, distance to store 1 is 2, distance to store 2 is 4. Maximum is 4. - Second query: Xiao-Ming lives in location 5 in year 6. In this year, stores 1 and 3 are open, distance to store 1 is 2, distance to store 3 is 2. Maximum is 2. - Third query: Xiao-Ming lives in location 5 in year 9. In this year, stores 1 and 4 are open, they both have type 1, so there is no store of type 2, inconvenience index is −1. - Same situation in fourth query.

In the second example there are two stores, one type, and three queries. Both stores have location 1, and in all queries Xiao-Ming lives at location 1. In first two queries at least one of stores is open, so answer is 0, in third query both stores are closed, so answer is −1.

In the third example there is one store and one query. Distance between locations is 99999999.

Subtask 1 (5 points): $n,q\leq 400$

Subtask 2 (7 points): $n,q\leq 6\times 10^4,$ $k\leq 400$

Subtask 3 (10 points): $n,q\leq 3\times 10^5,$ $a_i=1,b_i=10^8$ for all stores.

Subtask 4 (23 points): $n,q\leq 3\times 10^5,$ $a_i=1$ for all stores.

Subtask 5 (35 points): $n,q\leq 6\times 10^4$

Subtask 6 (20 points): $n,q\leq 3\times 10^5$