Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LANDK - Mua đất

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/landk


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

Được gửi lên bởi:Jimmy
Ngày:2010-04-17
Thời gian chạy:0.600s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED
Nguồn bài:POI 2007, cảm ơn bạn Nguyễn Vương Linh

hide comments
2010-04-17 08:37:54 Nguyên
Giới hạn n là bao nhiêu vậy anh?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.