Living on Wufu Street

Wufu Street is a perfectly straight road and can be regarded as a number line. Every building on the street is given by an integer coordinate. In the past, present, and future, there are n shops that appear along the street. The i-th shop is described by four integers \(x_i, t_i, a_i, b_i\), where:

• \(x_i\) is the coordinate of the shop,
• \(t_i\) is its type,
• \(a_i\) is the opening year, and
• \(b_i\) is the closing year.

Xiaoming, a time traveler, is considering living at some point on Wufu Street at a particular time. He has a list of q queries, each represented by a pair \((l_i, y_i)\) where \(l_i\) is the location he might live at and \(y_i\) is the year he would reside in.

The inconvenience index of living at \((l, y)\) is defined as follows: For each shop type \(t\), consider all shops of that type that are operating in year \(y\) (i.e., those satisfying \(a_i \le y \le b_i\)). For each type \(t\), define its distance as the minimum distance from \(l\) to any shop of that type, i.e.,

[ D_t(l, y) = \min{ |x_i - l| : \text{shop } i \text{ with type } t \text{ satisfies } a_i \le y \le b_i }. ]

The inconvenience index is the maximum of these distances over all \(k\) shop types:

[ \text{Inconvenience}(l, y) = \max_{1 \le t \le k} D_t(l, y). ]

If in a particular year there exists at least one shop type for which no shop is operating, the inconvenience index is defined to be \(-1\).

inputFormat

The input begins with a line containing three integers \(n\), \(k\) and \(q\) — the number of shops, the total number of shop types, and the number of queries respectively.

The next \(n\) lines each contain four integers \(x_i\), \(t_i\), \(a_i\) and \(b_i\), describing a shop's coordinate, type, opening year, and closing year.

The following \(q\) lines each contain two integers \(l_i\) and \(y_i\), representing a query for a chosen location and year of residence.

outputFormat

For each query, output one line containing the inconvenience index. If there exists any shop type with no shop operating in the given year, output \(-1\) for that query.

sample

3 2 3
0 1 2000 2020
10 2 1990 2010
5 2 2005 2025
2 2000
2 2005
6 1995

8
3
-1