Thám hiểm hầm ngục

Một hầm ngục mới vừa xuất hiện. Hầm ngục có dạng ma trận vuông gồm \(n\) × \(n\) phòng chứa rất nhiều quái vật. Phòng ở hàng \(i\) và cột \(j\) được gọi là phòng \((i, j)\). Khi tiến vào hầm ngục, người chơi sẽ được dịch chuyển đến một phòng ngẫu nhiên. Người chơi phải tiêu diệt hết quái vật mới có thể di chuyển đến các phòng kề cạnh. Sau khi quét sạch được một phòng, người chơi sẽ nhận được một rương phần thưởng có giá trị \(a_{i, j}\). Trong hầm sẽ có một phòng dịch chuyển, sau khi dọn sạch phòng đó, người chơi sẽ nhận được rương ở phòng đó và cổng dịch chuyển sẽ xuất hiện để thoát khỏi hầm ngục.

Để hạn chế tổn thất, hệ thống đặt ra một lời nguyền đó là sau khi thoát khỏi hầm ngục, người chơi chỉ có thể giữ lại một rương có giá trị phần thưởng nhỏ nhất trong tất cả các rương nhận được.

Jung, một người chơi giàu kinh nghiệm, đã nhanh chóng tìm được bản đồ chi tiết giá trị phần thưởng ở các phòng và cách xác định hai phòng xuất phát và dịch chuyển khi vào hầm ngục. Vì đang bận rộn với đống công việc của công hội nên anh đã liệt kê ra danh sách các khả năng và nhờ bạn lên kế hoạch tấn công.

Yêu cầu: Cho \(q\) truy vấn có dạng \(x\) \(y\) \(u\) \(v\) \((1 ≤ x, y, u, v ≤ n)\), hãy tính toán nếu xuất phát ở phòng \((x, y)\) và phòng dịch chuyển là phòng \((u, v)\) thì khi ra khỏi hầm ngục, giá trị phần thưởng được giữ lại lớn nhất là bao nhiêu.

Input

Dòng đầu tiên chứa hai số nguyên \(n\), \(q\) \((1 ≤ n ≤ 500; 1 ≤ q ≤ 4·10^5)\).

\(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên \(a_{i, j}\) \((1 ≤ a_{i, j} ≤ 10^5)\).

\(q\) dòng cuối dùng, mỗi dòng chứa bốn số nguyên \(x, y, u, v\) \((1 ≤ x, y, u, v ≤ n)\). Dữ liệu đảm bảo \((x + u)^2 + (y + v)^2 > 4xu + 4yv\).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

In ra \(q\) dòng, mỗi dòng in ra giá trị phần thưởng lớn nhất tương ứng với từng khả năng trong dữ liệu vào.

Example

5 3
8 4 1 2 4
2 3 5 6 5
1 2 1 5 2
9 5 8 4 7
4 5 1 3 9
1 1 4 1
1 4 3 2
5 3 2 5

3
2
1

Scoring

(\(10\) điểm) \(n ≤ 100\) và \(q ≤ 100\)

(\(20\) điểm) \(n ≤ 100\) và \(q ≤ 2000\)

(\(50\) điểm) \(n ≤ 300\) và \(q ≤ 10^5\)

(\(20\) điểm) \(n ≤ 500\) và \(q ≤ 4·10^5\)