Vào một ngày nắng đẹp, một vụ bắt cóc đã xảy ra tại một giao lộ trong thành phố. Những kẻ phạm tội bị nghi là Anna và Bruno, và họ đã trốn khỏi hiện trường bằng ô tô. Chiếc xe vẫn chưa được tìm thấy. Cảnh sát hiện vẫn đang tìm kiếm nó.

Khu vực đô thị nơi những kẻ phạm tội lái xe là một thành phố dạng lưới chữ nhật với $H$ đường chạy theo hướng đông–tây và $W$ đường chạy theo hướng nam–bắc. Khoảng cách giữa hai giao lộ kề nhau là 1 kilômét.

Mỗi đường có một số nguyên gọi là mức độ ùn tắc. Mức độ ùn tắc của đường đông–tây thứ $i$ ($1 \le i \le H$) tính từ phía bắc là $A_i$, và mức độ ùn tắc của đường nam–bắc thứ $j$ ($1 \le j \le W$) tính từ phía tây là $B_j$. Các giá trị trong số $H+W$ giá trị này đôi một khác nhau. Với mỗi đường, mức độ ùn tắc có cùng giá trị tại mọi điểm trên đường đó.

Cuộc điều tra của cảnh sát cho thấy những kẻ phạm tội di chuyển trong thành phố theo cách sau:

• Họ không ra khỏi thành phố và không rời khỏi các đường.
• Ban đầu, những kẻ phạm tội chọn một trong các hướng có thể di chuyển từ hiện trường vụ bắt cóc, rồi đi theo hướng đó.
• Khi tới một giao lộ, nếu mức độ ùn tắc của đường cắt ngang lớn hơn mức độ ùn tắc của đường hiện tại, họ rẽ tại giao lộ đó. Nếu có thể rẽ theo cả hai hướng, họ được chọn một trong hai hướng.
• Khi tới một giao lộ, nếu mức độ ùn tắc của đường hiện tại lớn hơn mức độ ùn tắc của đường cắt ngang, họ tiếp tục đi thẳng. Tuy nhiên, nếu đang ở ranh giới thành phố và không thể đi thẳng, họ dừng lại tại đó.

Có $Q$ giao lộ được xem là các vị trí có thể xảy ra vụ bắt cóc. Các vị trí này đôi một khác nhau. Để quyết định số lượng điều tra viên, với mỗi giao lộ ứng viên, cảnh sát muốn biết quãng đường di chuyển lớn nhất có thể của những kẻ phạm tội, giả sử vụ bắt cóc xảy ra tại đó.

Với mỗi trong số $Q$ truy vấn, hãy tính quãng đường di chuyển lớn nhất có thể từ giao lộ ứng viên được cho.

Yêu cầu

Cho mức độ ùn tắc của các đường trong thành phố và $Q$ giao lộ ứng viên cho hiện trường vụ bắt cóc, hãy viết chương trình tính quãng đường di chuyển lớn nhất có thể từ mỗi giao lộ ứng viên.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu chứa ba số nguyên $H,W,Q$ cách nhau bởi dấu cách. Điều này có nghĩa thành phố là một lưới chữ nhật với $H$ đường đông–tây và $W$ đường nam–bắc, và có $Q$ giao lộ ứng viên cho hiện trường vụ bắt cóc.
• Dòng thứ hai chứa $H$ số nguyên $A_1,A_2,\ldots,A_H$ cách nhau bởi dấu cách. Điều này có nghĩa mức độ ùn tắc của đường đông–tây thứ $i$ ($1 \le i \le H$) tính từ phía bắc là $A_i$.
• Dòng thứ ba chứa $W$ số nguyên $B_1,B_2,\ldots,B_W$ cách nhau bởi dấu cách. Điều này có nghĩa mức độ ùn tắc của đường nam–bắc thứ $j$ ($1 \le j \le W$) tính từ phía tây là $B_j$.
• Dòng thứ $k$ ($1 \le k \le Q$) trong $Q$ dòng tiếp theo chứa hai số nguyên $S_k,T_k$ cách nhau bởi dấu cách. Điều này có nghĩa giao lộ ứng viên thứ $k$ cho hiện trường vụ bắt cóc là giao điểm của đường đông–tây thứ $S_k$ tính từ phía bắc và đường nam–bắc thứ $T_k$ tính từ phía tây.

Dữ liệu ra

Ghi $Q$ dòng ra đầu ra chuẩn. Dòng thứ $k$ phải chứa một số nguyên, là quãng đường di chuyển lớn nhất có thể (tính bằng kilômét) từ giao lộ ứng viên thứ $k$ cho hiện trường vụ bắt cóc.

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau.

• $2 \le H \le 50\,000$.
• $2 \le W \le 50\,000$.
• $1 \le Q \le 100$.
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le H$).
• $1 \le B_j \le 1\,000\,000\,000$ ($1 \le j \le W$).
• $H+W$ số nguyên $A_1,A_2,\ldots,A_H,B_1,B_2,\ldots,B_W$ đôi một khác nhau.
• $1 \le S_k \le H$ ($1 \le k \le Q$).
• $1 \le T_k \le W$ ($1 \le k \le Q$).
• $(S_k,T_k) \ne (S_l,T_l)$ ($1 \le k < l \le Q$).

Nhiệm vụ con

Có 5 nhiệm vụ con. Điểm số và các giới hạn bổ sung của từng nhiệm vụ con như sau:

Nhiệm vụ con 1 [13 điểm]

• $H \le 8$.
• $W \le 8$.
• $Q=1$.

Nhiệm vụ con 2 [10 điểm]

• $H \le 2\,000$.
• $W \le 2\,000$.
• $Q=1$.

Nhiệm vụ con 3 [17 điểm]

• $Q=1$.

Nhiệm vụ con 4 [4 điểm]

• $H \le 2\,000$.
• $W \le 2\,000$.

Nhiệm vụ con 5 [56 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4
5
4
4
2

Ghi chú

Ví dụ, với truy vấn thứ ba, quãng đường di chuyển đạt giá trị lớn nhất nếu những kẻ phạm tội di chuyển như sau:

• Họ đi về phía đông 1 kilômét từ giao điểm của đường thứ hai tính từ phía bắc và đường thứ hai tính từ phía tây.
• Từ giao điểm của đường thứ hai tính từ phía bắc và đường thứ ba tính từ phía tây, họ có thể đi về phía nam hoặc phía bắc. Họ chọn đi về phía nam 1 kilômét.
• Từ giao điểm của đường thứ ba tính từ phía bắc và đường thứ ba tính từ phía tây, họ chỉ có thể đi về phía tây. Họ đi về phía tây 1 kilômét.
• Từ giao điểm của đường thứ ba tính từ phía bắc và đường thứ hai tính từ phía tây, họ chỉ có thể đi về phía tây. Họ đi về phía tây 1 kilômét.
• Họ không thể di chuyển từ giao điểm của đường thứ ba tính từ phía bắc và đường thứ nhất tính từ phía tây. Họ dừng lại tại đó.

Nếu di chuyển như trên, quãng đường là 4 kilômét.

Dữ liệu vào 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

Dữ liệu ra 2

7
6
9
4
6
9