New Home

Wu-Fu Street is a perfectly straight street. It is described as a one-dimensional number line, so every building on it sits at a single number. Xiao-Ming the time traveler knows every store that opened, is open, or will open on the street: there are $n$ stores of $k$ types. Store $i$ is given by four integers $x_i$, $t_i$, $a_i$, $b_i$, meaning the location of the store, the type of the store, the year its business starts, and the year its business ends. Store $i$ is open in year $y$ when $a_i \le y \le b_i$.

Xiao-Ming wants to pick a year and a location on Wu-Fu Street to live in, and he narrowed his preference list to $q$ pairs of a location and a year. Pair $i$ is given by two integers $l_i$, $y_i$. He rates a pair by its inconvenience index, the inaccessibility of the store type that is hardest to reach. The inaccessibility of type $t$ for a pair is the distance from the location to the nearest type-$t$ store that is open in that year, so the inconvenience index is the largest of those distances over all $k$ types. In some years Wu-Fu Street does not carry all $k$ types. The inconvenience index of such a pair is $-1$.

Find the inconvenience index of every pair.

The first line contains three integers $n$, $k$, $q$: the number of stores, the number of types, and the number of queries ($1 \le n, q \le 3 \times 10^5$, $1 \le k \le n$).

Each of the next $n$ lines describes one store with four integers $x_i$, $t_i$, $a_i$, $b_i$ ($1 \le x_i, a_i, b_i \le 10^8$, $1 \le t_i \le k$, $a_i \le b_i$).

Each of the next $q$ lines contains one query, two integers $l_i$ and $y_i$ ($1 \le l_i, y_i \le 10^8$).

Print $q$ integers, one per line, in the order the queries are given. The $i$-th of them is the inconvenience index of the $i$-th query.

The first sample has four stores, two types, and four queries.

• First query: Xiao-Ming lives at location 5 in year 3. Stores 1 and 2 are open that year, the distance to store 1 is 2, and the distance to store 2 is 4. The answer is 4.
• Second query: he lives at location 5 in year 6. Stores 1 and 3 are open and both are at distance 2. The answer is 2.
• Third query: he lives at location 5 in year 9. Stores 1 and 4 are open and both have type 1, so no store of type 2 is open. The answer is $-1$.
• Fourth query: the same situation, so the answer is $-1$.

The second sample has two stores, one type, and three queries. Both stores are at location 1, and every query asks about location 1. At least one store is open in the first two queries, so the answer is 0. Both stores are closed in the third query, so the answer is $-1$.

The third sample has one store and one query. The distance between the two locations is 99999999.