Năng lượng mặt trời là một trong những nguồn năng lượng xanh mang lại vô số lợi ích cho cả nền kinh tế và môi trường. Tuy nhiên hiện nay năng lượng mặt trời vẫn chưa được áp dụng rộng rãi. Bạn là trưởng ban năng lượng của thành phố Mondstadt và được nhận nhiệm vụ thí điểm sử dụng năng lượng mặt trời ở một số hộ gia đình. Bản đồ thành phố Mondstadt có dạng hình chữ nhật gồm ~n~ hàng và ~m~ cột, mỗi ô đại diện cho một hộ gia đình. Sau khi thực hiện khảo sát dân số và nhu cầu sử dụng điện, bạn đã có được chi phí mà từng hộ gia đình sẽ phải chi trả nếu sử dụng năng lượng mặt trời. Cụ thể hộ gia đình ở hàng ~i~ cột ~j~ sẽ phải trả chi phí là ~a_{ij}~. Đợt thí điểm lần này sẽ có ~q~ khu vực trọng điểm có dạng hình chữ nhật (các khu vực có thể giao nhau). Mỗi khu vực sẽ có mức độ phủ năng lượng bằng với số lượng hộ gia đình sử dụng năng lượng mặt trời nằm trong khu vực này. Cấp trên yêu cầu bạn cần phải thiết kế kế hoạch sao cho tổng mức độ phủ năng lượng của ~q~ khu vực không bé hơn ~k~. Các hộ gia đình trong thành phố của bạn đều khá giả và không ngại chi số tiền lớn cho việc sử dụng năng lượng mặt trời. Tuy vậy, con người thì luôn tị nạnh nhau, và người dân nơi đây cũng không ngoại lệ. Họ sẽ không thấy hài lòng nếu số tiền họ chi ra chênh lệch quá nhiều so với các hộ gia đình khác. Vì thế, hãy tìm cách chọn một hoặc một số hộ gia đình để thí điểm sử dụng năng lượng mặt trời, sao cho tổng mức độ phủ năng lượng của ~q~ khu vực trọng điểm không bé hơn ~k~ và chênh lệch lớn nhất giữa hai hộ gia đình được chọn bất kỳ là nhỏ nhất. Trường hợp chỉ chọn một hộ gia đình, ta xem chênh lệch có giá trị bằng ~0~.

Input

• Dòng đầu tiên là một số nguyên dương ~T (T \leq 10)~ là số lượng bộ test.
• Dòng đầu tiên của mỗi bộ test là 3 số nguyên dương ~n, m, k~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ số nguyên dương ~a_{ij}~ ~(1 \leq a_{ij} \leq n * m)~, là chi phí hộ gia đình ở vị trí hàng ~i~ cột ~j~ phải trả nếu sử dụng năng lượng mặt trời.
• Dòng tiếp theo là ~q~, số lượng khu vực trọng điểm.
• ~q~ dòng tiếp theo, mỗi dòng gồm 4 số nguyên dương ~x_1, y_1, x_2, y_2~ ~(1 \leq x_1, x_2 \leq n, 1 \leq y_1, y_2 \leq m)~ lần lượt là vị trí của ô trái trên và ô phải dưới của các khu vực.

Output

• Gồm ~T~ dòng, mỗi dòng in ra một số duy nhất là chênh lệch bé nhất tìm được trong phương án tối ưu

Sample input

2
3 4 2
1 8 7 7
6 1 7 6
4 3 4 2
2
1 2 2 3
2 1 3 2
3 4 3
1 8 7 7
6 1 7 6
4 3 4 2
2
1 2 2 3
2 1 3 2

Sample output

0
1

Giải thích

• Ở ví dụ đầu tiên, chọn hộ gia đình ở ô ~(1,3)~ và ô ~(2, 3)~ là phương án tối ưu. Khi đó khu vực thứ nhất có mức độ phủ năng lượng là 2, khu vực thứ hai có mức độ phủ năng lượng là 0
• Ở ví dụ thứ hai, chọn hộ gia đình ở ô ~(1,2), (1,3)~ và ô ~(2,3)~ là phương án tối ưu. Khi đó khu vực thứ nhất có mức độ phủ năng lượng là 3, khu vực thứ hai có mức độ phủ năng lượng là 0

Tính điểm

• Subtask 1: 30% số test có ~n * m \leq 16~, ~q \leq 5~
• Subtask 2: 30% số test có ~n * m, q \leq 10^3~
• Subtask 3: 40% số test có ~n * m, q \leq 10^5~