Giải bài trực tuyến

Mua đất

Sau nhiều năm, Lisa đã tích cóp được số tiền và muốn mua 1 mảnh đất ở khu đất phía ngoại ô thành phố. Để đơn giản, ta coi khu đất này là một hình vuông kích thước n * n, đã được chia thành các ô vuông nhỏ kích thước 1 * 1. Do mỗi ô đất có địa thế khác nhau, nên giá trị của chúng cũng rất khác nhau. Giá trị của một mảnh đất, được tính là tổng của tất cả các ô đất trong đó.

Ban đầu, Lisa có k đồng. Được bạn bè hỗ trợ, Lisa vay được thêm k đồng nữa. Chính vì vậy, cô mới đặt ra 1 yêu cầu mua đất rất oái oăm như sau: Mảnh đất phải có dạng hình chữ nhật

Các cạnh của mảnh đất song song với các cạnh của khu đất n * n

Giá của mảnh đất này ít nhất là k, và không vượt quá 2k (Lisa không muốn vay quá nhiều)

Bạn hãy viết chương trình giúp Lisa mua được mảnh đất ưng ý

Input

Dòng đầu tiên ghi 2 số nguyên dương k và n: số tiền ban đầu của Lisa và kích thước của khu đất (1 <= k <= 10^9, 1 <= n <= 2000).

N dòng sau, mỗi dòng gồm n số nguyên dương mô tả giá của các ô đất. a_ij (1 <= a­_ij <= 2.10^9) là giá của ô đất nằm ở vị trí (i,j) (các ô được đánh số từ 1 -> n theo chiều từ trái qua phải và từ trên xuống dưới). Các số được cách nhau bởi khoảng trắng

Output

Nếu không tồn tại mảnh đất thỏa mãn yêu cầu của Lisa, in “NIE” (không có dấu ngoặc kép)

Ngược lại, in ra 4 số nguyên dương là tọa độ ô trái trên và ô phải dưới của mảnh đất chọn được (lưu ý ghi theo thứ tự cột trước, hàng sau). Nếu có nhiều kết quả, bạn chỉ cần in ra 1 kết quả tùy ý

Ví dụ

Input
4 3
1 1 1
1 9 1
1 1 1

Output
NIE

Input
8 4
1 2 1 3
25 1 2 1
4 20 3 3
3 30 12 2

Output
2 1 4 2