Nhân dịp sang Singapore tham dự vòng Chung kết ICPC Asia Pacific Championship 2025, Thắng cùng đội NEU_gugugaga của mình được tham gia một loạt trò chơi trí tuệ do ban tổ chức tạo ra trước khi tham gia kỳ thi. Thắng tham gia nhiều trò chơi rất hấp dẫn trong đó có trò chơi “Thám hiểm mê cung”. Mê cung có dạng ma trận vuông gồm ~n \times n~ phòng, phòng ở hàng ~i~ và cột ~j~ được gọi là phòng ~(i, j)~. Tại phòng ~(i, j)~ có giấu phần thưởng có giá trị ~a_{ij}~. Khi tiến vào mê cung, người chơi được đưa đến phòng xuất phát. Nhiệm vụ của người chơi là đi từ phòng xuất phát đến phòng thoát hiểm thông qua các phòng kề cạnh và không được quay lại những phòng đã đi qua. Khi đi qua mỗi phòng ~(i, j)~, người chơi sẽ tìm được phần thưởng có giá trị ~a_{ij}~. Khi đến phòng thoát hiểm người chơi sẽ thoát khỏi mê cung. Để hạn chế trả thưởng cho người chơi, hệ thống quy định sau khi thoát khỏi mê cung, người chơi nhận được một phần thưởng có giá trị nhỏ nhất trong tất cả các phần thưởng đã tìm được.

Yêu cầu: Cho ~q~ truy vấn, với mỗi truy vấn cho biết phòng xuất phát ~(x, y)~ và phòng thoát hiểm ~(u, v)~ là hai phòng phân biệt. Hãy lập trình tìm giá trị phần thưởng lớn nhất mà Thắng có thể nhận được.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, q~ (~1 \le n \le 500, 1 \le q \le 4 \times 10^5~);
• ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên ~a_{ij}~ (~1 \le a_{ij} \le 10^5, 1 \le i, j \le n~);
• ~q~ dòng cuối cùng, mỗi dòng chứa bốn số nguyên ~x, y, u, v~ (~1 \le x, y, u, v \le n~).

Output

• Ghi 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 mỗi truy vấn.

Sample Input 1

5 2
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

Sample Output 1

3
2