Problem : 90 - 買賣土地

Special Judge

Problem Statistics

Solved Member: 17　　Submission: 159　　User Tried: 28

Statement:

你決定搬家到宅心仁厚的瀚瀚國住。

你看上了一塊 N*N 的正方形土地，每塊土地依據兔子的環境負載力不同價錢有高有低。你擁有 2k 的瀚瀚幣，你想圈出一塊矩形的土地來當作明天找仲介的參考。當然，你不希望破費，但是你也不希望你買的土地價錢少於你所擁有的一半，這樣你會沒有敗家的感覺。

Task:

給定一塊 N*N 的土地和每一塊的價錢。
找出任意一塊價格在 k 與 2k 之間的矩形土地。

Input:Output:

第 1 行有兩個數字 k,N ，代表你擁有 2k 的瀚瀚幣以及土地的長寬。
接下來第 2 行到第 N+1 行，每一行有 N 個數字，第 Y+1 行的第 X 個數字代表座標為 (X,Y) 那塊土地的價錢(瀚瀚幣)。

n ≤ 2000
1 ≤ k ≤ 1000000000
0 ≤ 每一格的價錢 ≤ 2000000000

本題有多組解答，請輸出任意一組即可。

輸出一行 4 個整數， x1,y1,x2,y2 用空格區隔開來。代表一個以 (x1,y1) 和 (x2,y2) 為對角線的矩形。並且滿足 x1 ≤ x2, y1 ≤ y2
如果不存在價值介於[k,2k]之間的矩形土地，請輸出"NIE"。(不含括號)

Sample Input:Sample Output:

SAMPLE A:
4 3
1 1 1
1 9 1
1 1 1

SAMPLE B:
8 4
1 2 1 3
25 1 2 1
4 20 3 3
3 30 12 2

SAMPLE A:
NIE

SAMPLE B:
2 1 4 2

Source:

POI 15 Stage 3

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	1000ms	65536kb
0-2	1000ms	65536kb
1-ocen	1000ms	65536kb
1-1	1000ms	65536kb	10
1-2	1000ms	65536kb
1-3	1000ms	65536kb
2-ocen	1000ms	65536kb
2-1	1000ms	65536kb	10
2-2	1000ms	65536kb
3-ocen	1000ms	65536kb
3-1	1000ms	65536kb	10
3-2	1000ms	65536kb
4-ocen	5000ms	65536kb
4-1	1000ms	65536kb	10
4-2	1000ms	65536kb
5	2000ms	65536kb	10
6	10000ms	65536kb	10
7	10000ms	65536kb	10
8	10000ms	65536kb	10
9-1	10000ms	65536kb	10
9-2	10000ms	65536kb
10-1	10000ms	65536kb	10
10-2	10000ms	65536kb