Bán hàng qua mạng là một hình thức kinh doanh ngày càng phổ biến. Để thực hiện được việc bán hàng qua mạng, nhà sản xuất thông qua một phần mềm giới thiệu các sản phẩm, khách hàng sử dụng phần mềm này để lựa chọn sản phẩm cần mua. Phần mềm giới thiệu có nhiều loại sản phẩm, mỗi sản phẩm có nhiều thông số, trong đó hai thông số cơ bản là giá bán và số khách hàng đã mua.

Khách hàng lựa chọn loại sản phẩm cần mua và cung cấp hai số nguyên ~x,\ y~ ~(x \le y)~ là khoảng giá cần mua của loại sản phẩm đó. Trong mỗi khoảng giá, phần mềm sẽ đưa ra sản phẩm có nhiều khách hàng mua nhất.

Yêu cầu

Cho ~n~ sản phẩm và ~Q~ yêu cầu của khách hàng. Với mỗi yêu cầu hãy đưa ra sản phẩm và số khách hàng đã mua nhiều nhất.

Dữ liệu đầu vào

Gồm ~n + Q + 2~ dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~;
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo ~(1 \le i \le n)~ mỗi dòng có hai số nguyên dương ~v_i~ và ~s_i~ ~(1 \le v_i, s_i \le 10^9)~ cách nhau một dấu cách. Trong đó: ~v_i~ là giá bán và ~s_i~ là số khách hàng đã mua sản phẩm thứ ~i~;
• Dòng thứ ~n + 2~ chứa số nguyên dương ~Q~ ~(1 \le Q \le 10^5)~;
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~x,\ y~ ~(1 \le x \le y \le 10^9)~ là khoảng giá mà khách hàng đưa ra.

Dữ liệu đầu ra

Gồm ~Q~ dòng, mỗi dòng tương ứng với một yêu cầu, chỉ cần ghi ra một số nguyên là số khách hàng đã mua nhiều nhất của sản phẩm tìm được. Nếu không có sản phẩm nào trong khoảng giá thì in ra ~0~.

Ràng buộc dữ liệu

• Có 70% số test ứng với 70% số điểm của bài thỏa mãn điều kiện: ~Q, n \le 10^3~;
• 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

2
2 3
5 8
3
6 8
1 3
1 6

OUTPUT

0
3
8

Câu lạc bộ khiêu vũ nhà trường sau thành lập có ~m~ bạn nam được đánh số từ ~1~ đến ~m~ và ~n~ bạn nữ đánh số từ ~1~ đến ~n~ đăng ký tham gia. Bạn nam thứ ~i~ có chiều cao ~a_i~ ~(i = 1, 2, ..., m)~, bạn nữ thứ ~j~ có chiều cao ~b_j~ ~(j = 1, 2, ..., n)~.

Việc bố trí cặp nhảy trong các rất quan trọng, câu lạc bộ cần chọn một đội hình gồm ~k~ cặp bạn nhảy. Mỗi cặp nhảy có đúng một bạn nam và một bạn nữ. Chỉ số phù hợp của một cặp bạn nhảy là chênh lệch chiều cao của hai người, chỉ số phù hợp của cả đội hình bằng chỉ số phù hợp của cặp bạn nhảy lớn nhất.

Yêu cầu

Hãy chọn một đội hình gồm ~k~ cặp bạn nhảy sao cho chỉ số phù hợp của đội hình là nhỏ nhất.

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng đầu tiên chứa ba số nguyên dương ~m, n, k \le 10^5~ ~(k \le min(m, n))~;
• Dòng 2 chứa ~m~ số nguyên dương ~a_1, a_2, ..., a_m~ ~(a_i \le 10^9)~;
• Dòng 3 chứa ~n~ số nguyên dương ~b_1, b_2, ..., b_n~ ~(b_i \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên dương duy nhất là chỉ số phù hợp của đội hình theo phương án được chọn.

Ràng buộc dữ liệu

• Có 30% số test ứng với 30% số điểm thỏa mãn: ~m, n \le 10^3,\ k = 1~;
• 30% số test ứng với 30% số điểm thỏa mãn: ~m, n \le 10^5,\ k = 1~;
• 40% số test còn lại ứng với 40% số không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

4 5 3
1 2 3 4
2 2 1 4 5

OUTPUT

0

Ví dụ 2

INPUT

4 5 4
1 2 3 4
2 2 1 4 5

OUTPUT

1

Bản đồ mê cung có dạng hình chữ nhật được chia bởi các đường song song với các cạnh tạo thành lưới ô vuông đơn vị gồm ~m~ hàng và ~n~ cột. Ô vuông nằm ở hàng ~i~ và cột ~j~ gọi là ô ~(i, j)~. Mỗi ô của mê cung có hai loại là ô tự do hoặc ô có câu hỏi. Trong mê cung có ~k~ ô có câu hỏi, người chơi đang ở một ô tự do ~(x, y)~ trong mê cung và bắt đầu di chuyển ra khỏi mê cung bằng cách đi qua các ô lân cận cạnh để đến một ô nào đó nằm ở biên của mê cung. Các câu hỏi có độ khó tăng dần được đánh số từ ~1~ đến ~k~. Trò chơi cho phép bạn mở khóa tối đa ~1~ câu hỏi và đi qua ô đó. Để đi hết một ô cần ~3~ đơn vị thời gian, để mở khóa một ô có câu hỏi cần ~1~ đơn vị thời gian. Như vậy thời gian đi hết một ô có câu hỏi cần ~4~ đơn vị thời gian. Thời gian bạn thoát khỏi mê cung là tổng thời gian đi hết ô ~(x, y)~, thời gian đi qua các ô trung gian và thời gian đi hết ô nằm ở biên.

Yêu cầu

Bạn hãy tìm hành trình thoát khỏi mê cung với tổng thời gian nhỏ nhất? Nếu có nhiều hành trình thì đưa ra hành trình mở khóa ô có câu hỏi dễ nhất.

Dữ liệu đầu vào

Gồm ~k + 1~ dòng:

• Dòng ~1~ chứa ~5~ số nguyên ~m,\ n,\ k,\ x,\ y~ ~(m, n \le 10^3,\ 0 \le k < m \times n,\ 1 < x < m,\ 1 < y < n)~;
• Trong ~k~ dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên dương ~u,\ v~ với ý nghĩa ở ở hàng ~u~, cột ~v~ có câu hỏi mức độ khó ~i~ ~(1 \le u \le m,\ 1 \le v \le n,\ 1 \le i \le k)~.

Dữ liệu đầu ra

• Dòng đầu tiên ghi tổng thời gian nhỏ nhất tìm được, nếu không thể thoát khỏi mê cung ghi ~-1~;
• Trong trường hợp có thể thoát khỏi mê cung, dòng hai ghi mức độ khó của câu hỏi đã sử dụng. Nếu có hành trình di chuyển không đi qua ô có câu hỏi mà vẫn đảm bảo thời gian nhỏ nhất thì ghi số ~0~.

Ràng buộc dữ liệu

• Có 30% số test ứng với 30% số điểm thỏa mãn: ~k = 0~.
• 30% số test khác ứng với 30% số điểm thỏa mãn: ~k = 1~.
• 40% số test còn lại ứng với 40% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

8 8 4 6 5
8 5
7 5
6 6
7 4

OUTPUT

13
2

Giải thích: Có ~4~ hành trình có thời gian ~13~ là:

1. ~(6, 5) \rightarrow (7, 5) \rightarrow (7, 6) \rightarrow (8, 6)~
2. ~(6, 5) \rightarrow (6, 6) \rightarrow (7, 6) \rightarrow (8, 6)~
3. ~(6, 5) \rightarrow (6, 6) \rightarrow (6, 7) \rightarrow (6, 8)~
4. ~(6, 5) \rightarrow (6, 4) \rightarrow (7, 4) \rightarrow (8, 4)~

Hành trình ~(6, 5) \rightarrow (7, 5) \rightarrow (7, 0) \rightarrow (8, 6)~ có câu hỏi mức độ ~2~ là nhỏ nhất.