Nhân dịp tham quan tại khu vui chơi, Lam 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×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 sẽ được đưa đến một phòng ngẫu nhiên. Người chơi sau khi tìm ra được phần thưởng mới có thể di chuyển đến các phòng bên cạnh. Trong mê cung, có một phòng thoát hiểm. Sau khi tìm ra được phần thưởng đã giấu ở 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à Lam có thể nhận được.

Dữ liệu: Vào từ tệp văn bản GAME.INP có cấu trúc như sau:

• 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 aij (1≤aij≤10^5,1≤i,j≤n);
• q dòng cuối cùng, mỗi dòng chứa bốn số nguyên x,y,u,v (1≤x,y,u,v≤n);
• Các số trên cùng một dòng cách nhau bởi dấu cách.

  Kết quả: Ghi ra tệp văn bản GAME.OUT gồm 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.

Ví dụ:

    GAME.INP            GAME.OUT    
    5 2                 3
    8 4 1 2 4           2
    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 
    Giải thích: Ở truy vấn đầu tiên, xuất phát từ phòng (1,1) thoát hiểm ở phòng (4,1) phần thưởng lớn nhất có giá trị 3 mà Lam nhận được mô tả như dưới đây:
    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

Ràng buộc:

• Có 20% số test ứng với 20% số điểm của bài thoả mãn: n≤100, q≤100;
• Có 20% số test ứng với 20% số điểm của bài thoả mãn: n≤100, q≤2000;
• Có 30% số test ứng với 30% số điểm của bài thoả mãn: n≤300, q≤10^5;
• Có 30% số test ứng với 30% số điểm của bài thoả mãn: n≤500, q≤4×10^5.