Phố Wu-Fu là một phố cực kỳ thẳng có thể được mô tả như là một dải số một chiều, và mỗi vị trí của tòa nhà trên đường phố có thể được biểu diễn bằng một số. Nhà du hành xuyên thời gian Xiao-Ming biết rằng có \(n\) cửa hàng thuộc \(k\) loại cửa hàng đã từng mở cửa, đã mở cửa, hoặc sẽ mở cửa trên phố. Cửa hàng thứ \(i\) có thể được mô tả bằng bốn số nguyên: \(x_i, t_i, a_i, b_i\), tương ứng là vị trí của cửa hàng, loại cửa hàng, năm bắt đầu kinh doanh và năm cửa hàng đóng cửa.

Nhà du hành xuyên thời gian Xiao-Ming muốn chọn một năm nhất định và một vị trí nhất định trên Phố Wu-Fu để sinh sống. Ông đã thu hẹp danh sách sở thích của mình xuống \(q\) cặp vị trí/năm. Cặp thứ \(i\) có thể được mô tả bằng hai số nguyên: \(l_i, y_i\), biểu diễn vị trí và năm của cặp đó. Bây giờ ông ta muốn đánh giá chất lượng cuộc sống của các cặp này. Ông xác định chỉ số bất tiện của cặp vị trí/năm là mức độ khó tiếp cận của loại cửa hàng có mức độ khó tiếp cận lớn nhất của cặp đó. Mức độ khó tiếp cập của một cặp vị trí/năm đối với loại cửa hàng \(t\) được định nghĩa là khoảng cách từ vị trí đó đến cửa hàng loại \(t\) gần nhất mà được mở trong năm đó. Chúng ta nói rằng cửa hàng thứ \(i\) được mở trong năm \(y\) nếu \(a_i \le y \le b_i\). Lưu ý rằng trong một vài năm, phố Wu-Fu có thể không có tất cả \(k\) loại cửa hàng trên phố. Trong trường hợp đó, chỉ số bất tiện được định nghĩa là \(-1\).

Nhiệm vụ của bạn là giúp Xiao-Ming tìm ra chỉ số bất tiện của từng cặp vị trí/năm.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(n\), \(k\) và \(q\): số lượng cửa hàng, số loại và số truy vấn (\(1 \le n, q \le 3 \cdot 10^5\), \(1 \le k \le n\)).

\(n\) dòng tiếp theo chứa các mô tả của các cửa hàng. Mỗi mô tả bao gồm bốn số nguyên: \(x_i\), \(t_i\), \(a_i\) và \(b_i\) (\(1 \le x_i, a_i, b_i \le 10^8\), \(1 \le t_i \le k\), \(a_i \le b_i\)).

\(q\) dòng tiếp theo chứa các truy vấn. Mỗi truy vấn bao gồm hai số nguyên: \(l_i\) và \(y_i\) (\(1 \le l_i, y_i \le 10^8\)).

Dữ liệu ra

Ghi \(q\) số nguyên: với mỗi truy vấn ghi ra chỉ số bất tiện của nó.

Phân nhóm

Ví dụ

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

4
2
-1
-1

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

0
0
-1

1 1 1
100000000 1 1 1
1 1

99999999

Giải thích

Trong ví dụ đầu tiên có bốn cửa hàng, hai loại và bốn truy vấn.

• Truy vấn đầu tiên: Xiao-Ming sống ở vị trí 5 trong năm 3. Trong năm này, các cửa hàng 1 và 2 đang mở, khoảng cách đến cửa hàng 1 là 2, khoảng cách đến cửa hàng 2 là 4. Vậy tối đa là 4.

• Truy vấn thứ hai: Xiao-Ming sống ở vị trí 5 trong năm 6. Trong năm này, các cửa hàng 1 và 3 đang mở, khoảng cách đến cửa hàng 1 là 2, khoảng cách đến cửa hàng 3 là 2. Vậy tối đa là 2.

• Truy vấn thứ ba: Xiao-Ming sống ở vị trí 5 trong năm 9. Trong năm này, các cửa hàng 1 và 4 đang mở, cả hai đều có loại 1, vì vậy không có cửa hàng loại 2, chỉ số bất tiện là \(-1\).

• Tình huống tương tự trong truy vấn thứ tư.

Trong ví dụ thứ hai có hai cửa hàng, một loại và ba truy vấn. Cả hai cửa hàng đều có vị trí 1 và trong tất cả các truy vấn, Xiao-Ming sống ở vị trí 1. Trong hai truy vấn đầu tiên, ít nhất một cửa hàng đang mở, vì vậy câu trả lời là 0, ở truy vấn thứ ba cả hai cửa hàng đều đóng cửa, vì vậy câu trả lời là \(-1\).

Trong ví dụ thứ ba có một cửa hàng và một truy vấn. Khoảng cách giữa các địa điểm là 99999999.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2018, được lưu trong kho đề APIO.