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 Time Traveler 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 \le y \le 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.

Input

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

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

Next ~q~ lines contain the queries. Each query is two integers: ~l_i~, and ~y_i~ (~1 \le l_i, y_i \le 10^8~).

Output

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

Scoring

Subtask 1 (points: 5)

~n, q \le 400~

Subtask 2 (points: 7)

~n, q \le 6 \times 10^4~, ~k \le 400~

Subtask 3 (points: 10)

~n, q \le 3 \times 10^5~, ~a_i = 1~, ~b_i = 10^8~ for all stores.

Subtask 4 (points: 23)

~n, q \le 3 \times 10^5~, ~a_i = 1~ for all stores.

Subtask 5 (points: 35)

~n, q \le 6 \times 10^4~

Subtask 6 (points: 20)

~n, q \le 3 \times 10^5~

Sample Input 1

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

Sample Output 1

4
2
-1
-1

Sample Input 2

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

Sample Output 2

0
0
-1

Sample Input 3

1 1 1
100000000 1 1 1
1 1

Sample Output 3

99999999

Explanation

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.