Problem Background

Warning! Abusers will be banned! Do not submit repeatedly!

Problem Description

Wufu Street is a straight road, which can be considered as a number line where each building's location can be represented by an integer. Xiao Ming is a time traveler who knows that there are \( n \) stores on this street, past, present, and future. The \( i \)-th store can be described by four integers \( x_i, t_i, a_i, b_i \), which respectively represent: the store's coordinate, the store's type, the year it opens, and the year it closes.

Xiao Ming wants to choose an appropriate time to live at a certain location on Wufu Street through time travel. He has a list of \( q \) queries, each 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 calculate the quality of life at these times and locations. He defines the inconvenience index as the distance to the farthest store type from the residence in the given year. The distance from a store of type \( t \) to the residence is defined as the shortest distance from any open store of type \( t \) to the residence in the specified year. We say the \( i \)-th store is open in year \( y \) if and only if \( a_i \leq y \leq b_i \). Note that in some years, not all \( k \) types of stores may have at least one open on Wufu Street. In such cases, the inconvenience index is defined as \(-1\).

Your task is to help Xiao Ming calculate the inconvenience index for each pair (coordinate, time).

Input Format

The first line contains three integers \( n, k, \) and \( q \), representing the number of stores, the number of store types, and the number of (coordinate, time) pairs, respectively. \( (1 \leq n, q \leq 3 \times 10^5, 1 \leq k \leq n) \).

The next \( n \) lines each contain four integers \( x_i, t_i, a_i, \) and \( b_i \) to describe a store, as per the problem statement \( (1 \leq x_i, a_i, b_i \leq 10^8, 1 \leq t_i \leq k, a_i \leq b_i) \).

The next \( q \) lines each contain two integers \( l_i \) and \( y_i \), representing a (coordinate, time) query \( (1 \leq l_i, y_i \leq 10^8) \).

Output Format

Output a single line containing \( q \) integers, each representing the result for the corresponding (coordinate, time) query.

Sample Input and Output

Input Sample #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

Output Sample #1

4
2
-1
-1

Input Sample #2

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

Output Sample #2

0
0
-1

Input Sample #3

1 1 1
100000000 1 1 1
1 1

Output Sample #3

99999999

Notes

Hints

In the first sample, there are 4 stores of 2 types, and 4 queries.

• For the first query: Xiao Ming lives at coordinate 5 in year 3. In this year, stores 1 and 2 are open, the distance to store 1 is 2, and to store 2 is 4, so the maximum distance is 4.
• For the second query: Xiao Ming lives at coordinate 5 in year 6. In this year, stores 1 and 3 are open, the distance to store 1 is 2, and to store 3 is 2, so the maximum distance is 2.
• For the third query: Xiao Ming lives at coordinate 5 in year 9. In this year, stores 1 and 4 are open, both of type 1, and there is no type 2 store open, so the answer is -1.
• The same situation occurs in the fourth query.

In the second sample, there are 2 stores of 1 type, and 3 queries. Both stores are of type 1. In all queries, Xiao Ming lives at coordinate 1. In the first two queries, at least one store is open, so the answer is 0. In the third query, both stores are closed, so the answer is -1.

In the third sample, there is 1 store and 1 query, and the distance between them is 99999999.

Subtasks (Note: The subtasks provided here are for reference only and are not related to the final evaluation of this problem)

• 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 \), for all stores \( a_i = 1, b_i = 10^8 \)
• Subtask 4 (points: 23): \( n, q \leq 3 \times 10^5 \), for all stores \( 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 \)

见题面 Input 部分

见题面 Output 部分