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 stores of store-types that had opened, has opened, or will open on the street. The -th store can be described with four integers: , , , , 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 location-year pairs. The -th pair can be described with two integers: , , 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 is defined as the distance from the location to the nearest type- store that is open in the year. We say the -th store is open in the year if . Note that in some years, Wu-Fu Street may not have all the store-types on it. In that case, the inconvenience index is defined as .
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 , , and : number of stores, number of types and number of queries (, ). Next lines contain descriptions of stores. Each description is four integers: , , , and (, , ). Next lines contain the queries. Each query is two integers: , and ().
Output integers: for each query output its the inconvenience index.
Subtask 1 (points: 5)
Subtask 2 (points: 7) ,
Subtask 3 (points: 10) , , for all stores.
Subtask 4 (points: 23) , for all stores.
Subtask 5 (points: 35)
Subtask 6 (points: 20)
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:
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.