Khu đô thị là một lưới chữ nhật có \(H\) đường phố chạy đông-tây và \(W\) đường phố chạy bắc-nam. Khoảng cách giữa hai giao lộ kề nhau là \(1\) km. Đường đông-tây thứ \(i\) từ phía bắc có độ ùn tắc \(A_i\); đường bắc-nam thứ \(j\) từ phía tây có độ ùn tắc \(B_j\). Tất cả \(H+W\) giá trị này đôi một khác nhau và không đổi dọc theo mỗi đường.

Những kẻ bắt cóc di chuyển như sau:

• Chúng luôn ở trong thành phố và trên các đường phố.
• Ban đầu, chúng chọn một hướng có thể đi từ hiện trường.
• Tại một giao lộ, nếu độ ùn tắc của đường cắt ngang lớn hơn đường hiện tại, chúng rẽ. Nếu có thể rẽ theo cả hai phía, chúng chọn tùy ý.
• Nếu độ ùn tắc của đường hiện tại lớn hơn đường cắt ngang, chúng đi thẳng. Nếu đang ở biên thành phố và không thể đi thẳng, chúng dừng lại.

Có \(Q\) giao lộ ứng viên đôi một khác nhau. Với mỗi ứng viên, hãy tính quãng đường lớn nhất mà chúng có thể đi.

Dữ liệu vào

• Dòng đầu chứa \(H,W,Q\).
• Dòng thứ hai chứa \(A_1,\ldots,A_H\).
• Dòng thứ ba chứa \(B_1,\ldots,B_W\).
• \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa \(S_k,T_k\), chỉ giao lộ giữa đường đông-tây thứ \(S_k\) và đường bắc-nam thứ \(T_k\).

Dữ liệu ra

In \(Q\) dòng; dòng thứ \(k\) là quãng đường lớn nhất, tính bằng km, từ ứng viên thứ \(k\).

Ràng buộc

• \(2\le H,W\le 50\,000\).
• \(1\le Q\le 100\).
• \(1\le A_i,B_j\le 10^9\).
• Tất cả \(H+W\) độ ùn tắc đôi một khác nhau.
• \(1\le S_k\le H\), \(1\le T_k\le W\).
• Các cặp \((S_k,T_k)\) đôi một khác nhau.

Phân nhóm

1. \(13\) điểm: \(H,W\le 8\), \(Q=1\)
2. \(10\) điểm: \(H,W\le 2\,000\), \(Q=1\)
3. \(17\) điểm: \(Q=1\)
4. \(4\) điểm: \(H,W\le 2\,000\)
5. \(56\) điểm: Không có

Giới hạn

• Thời gian: 5 giây.
• Bộ nhớ: 512 MB.

Ví dụ

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

4
5
4
4
2

4 5 6
30 10 40 20
15 55 25 35 45
1 3
4 3
2 2
4 1
2 5
3 3

7
6
9
4
6
9

Nguồn

JOI 2016/2017 Spring Training Camp, ngày thi 4, bài Abduction 2.