Drevni programer Cep Lu Splus provodi dane mrzeći žalbe i mrzeći provođenje dana u mržnji. Povremeno mu dolaze sećanja na drevna vremena kada je bio član Komisije i odbijao žalbe najbolje od svih. Jednom, u ta vremena, dobio je izuzetno neosnovanu žalbu i dok je hodao drevnom planinom u potrazi za znakom da li da je prvo pročita ili prvo odbije -- žalba mu je ispala iz ranca i bi zauvek izgubljena. Od tada ga ovo mrsko sećanje neprestano progoni i zbog toga ne može da spava.

Ali sada ste došli vi, zaštitnici takmičara koji se žale, i odlučili da pronađete planinu na kojoj je izgubljena žalba. Poznato je da je Cep tog sudbonosnog dana bio u oblasti koja liči na kvadratnu matricu dimenzija ~N \times N~ čije svako polje predstavlja neku planinu određene visine. Kako Cep mrzi niske planine i kolone, planina na kojoj je on bio tog dana je strogo viša od svih ostalih planina iz svoje vrste. Analogno, kako Cep mrzi slanu plazmu i radne subote, ta planina je ujedno i strogo niža od svih ostalih planina iz svoje kolone.

Loša vest je što vi ne znate visine planina a još gora što Cep zna. No, njegova mržnja prema mrskim sećanjima i nesanici je blago jača od mržnje prema vama i on će vam iskreno odgovarati na pitanja oblika "kolika je visina planine koja se nalazi u ~i~-toj vrsti i ~j~-toj koloni?". Jasno, Cep mrzi drevni broj ~K~ i ne želite da znate šta će se desiti ukoliko mu postavite više od ~K~ pitanja.

Pronađite bar jednu planinu na kojoj je mogla biti izgubljena žalba ili konstatujte da takva planina ne postoji postavljajući ne više od ~K~ pitanja. Neka izgubljena žalba konačno bude i formalno odbijena...

Opisi funkcija

Potrebno je da implementirate funkciju

• ~Nadji(N, K)~

koja treba da odredi da li se u matrici planina sa ~N~ vrsta i ~N~ kolona nalazi planina koja je strogo veća od svih ostalih planina iz svoje vrste i strogo manja od svih ostalih planina iz svoje kolone. Ova funkcija mora da vrati niz (vektor) dužine 2 koji sadrži, redom, brojeve ~i~ i ~j~ koji označavaju da je tražena planina u preseku ~i~-te vrste i ~j~-te kolone. Vrste i kolone su indeksirane od 1. Ukoliko ima više rešenja, vratiti bilo koje; ukoliko nema rešenja vratiti niz sa dve nule.

Na raspolaganju imate funkciju

• ~Pitaj(i, j)~

koju smete pozvati najviše ~K~ puta. Ova funkcija vraća visinu planine u preseku ~i~-te vrste i ~j~-te kolone. Ukoliko su koordinate ~i~ i ~j~ van opsega, funkcija će vratiti ~-1~.

Primer

Neka je ~N = 3~, ~K = 9~ i neka su visine planina u matrici:

3 9 9
2 2 7
7 5 8

Za npr. upit ~Pitaj(2, 1)~, odgovor bi bio ~2~; za upit ~Pitaj(2, 3)~ odgovor bi bio ~7~; za upit ~Pitaj(3, 3)~ odgovor bi bio ~8~ itd. Jedino rešenje za ovaj primer je planina u preseku druge vrste i treće kolone (visina 7) i vaša funkcija mora da vrati niz ~(2, 3)~ koristeći ne više od ~9~ upita.

Ograničenja

• Visine svih planina su prirodni brojevi iz segmenta ~[1, 10^9]~.

Podzadaci

• Podzadatak 1 [4 poena]: ~N = 100~, ~K = 10.000~
• Podzadatak 2 [9 poena]: ~N = 1.000~, ~K = 1.000.000~
• Podzadatak 3 [12 poena]: ~N = 1.000~, ~K = 5.000~, visine planina su ~1~, ~2~ ili ~3~
• Podzadatak 4 [18 poena]: ~N = 1.000~, ~K = 501.500~
• Podzadatak 5 [19 poena]: ~N = 2.048~, ~K = 360.000~
• Podzadatak 6 [14 poena]: ~N = 3.000~, ~K = 12.000~
• Podzadatak 7 [24 poena]: ~N = 100.000~, ~K = 400.000~

Detalji implementacije

Potrebno je da pošaljete tačno jedan fajl planine.cpp koji implementira pomenutu funkciju. Osim tražene funkcije, vaš fajl može sadržati i dodatne globalne promenljive, pomoćne funkcije i dodatne biblioteke.

Vaša funkcija mora biti sledećeg oblika:

std::vector<int> Nadji(int N, int K);

Vaša funkcija može koristiti funkciju

int Pitaj(int i, int j);

Da bi funkcija Pitaj bila "vidljiva" vašoj funkciji Nadji, potrebno je dodati liniju #include "code.h" na početku fajla koji sadrži implementaciju funkcije Nadji.

Testiranje i eksperimentisanje

Uz zadatak, obezbeđen vam je "template" fajl code.cpp koji možete koristiti i menjati po potrebi. Takođe vam je obezbeđeni program grader.cpp koji služi da lakše testirate kodove. Ovaj program učitava sa standardnog ulaza sledeće podatke:

• U prvom redu brojeve ~N~ i ~K~
• U narednih ~N~ redova po ~N~ brojeva koji predstavljaju visine planina

a zatim poziva vašu funkciju sa učitanim parametrima ~N~ i ~K~. Na kraju, na standardni izlaz štampa, redom, brojeve ~x~, ~y~ i ~T~, gde su ~x~ i ~y~ redni broj vrste i kolone koje je vratila vaša funkcija a ~T~ broj poziva funkciji Pitaj. Kodove ovih programa možete menjati po potrebi. Ne garantuje se da će za testiranje biti korišćena baš ova verzija programa grader.cpp.