Древни програмер Цеп Лу Сплус проводи дане мрзећи жалбе и мрзећи провођење дана у мржњи. Повремено му долазе сећања на древна времена када је био члан Комисије и одбијао жалбе најбоље од свих. Једном, у та времена, добио је изузетно неосновану жалбу и док је ходао древном планином у потрази за знаком да ли да је прво прочита или прво одбије – жалба му је испала из ранца и би заувек изгубљена. Од тада га ово мрско сећање непрестано прогони и због тога не може да спава.

Али сада сте дошли ви, заштитници такмичара који се жале, и одлучили да пронађете планину на којој је изгубљена жалба. Познато је да је Цеп тог судбоносног дана био у области која личи на квадратну матрицу димензија \(N \times N\) чије свако поље представља неку планину одређене висине. Како Цеп мрзи ниске планине и колоне, планина на којој је он био тог дана је строго виша од свих осталих планина из своје врсте. Аналогно, како Цеп мрзи слану плазму и радне суботе, та планина је уједно и строго нижа од свих осталих планина из своје колоне.

Лоша вест је што ви не знате висине планина а још гора што Цеп зна. Но, његова мржња према мрским сећањима и несаници је благо јача од мржње према вама и он ће вам искрено одговарати на питања облика “колика је висина планине која се налази у \(i\)-тој врсти и \(j\)-тој колони?”. Јасно, Цеп мрзи древни број \(K\) и не желите да знате шта ће се десити уколико му поставите више од \(K\) питања.

Пронађите бар једну планину на којој је могла бити изгубљена жалба или констатујте да таква планина не постоји постављајући не више од \(K\) питања. Нека изгубљена жалба коначно буде и формално одбијена…

Описи функција

Потребно је да имплементирате функцију

• \(Nadji(N, K)\)

која треба да одреди да ли се у матрици планина са \(N\) врста и \(N\) колона налази планина која је строго већа од свих осталих планина из своје врсте и строго мања од свих осталих планина из своје колоне. Ова функција мора да врати низ (вектор) дужине 2 који садржи, редом, бројеве \(i\) и \(j\) који означавају да је тражена планина у пресеку \(i\)-те врсте и \(j\)-те колоне. Врсте и колоне су индексиране од 1. Уколико има више решења, вратити било које; уколико нема решења вратити низ са две нуле.

На располагању имате функцију

• \(Pitaj(i, j)\)

коју смете позвати највише \(K\) пута. Ова функција враћа висину планине у пресеку \(i\)-те врсте и \(j\)-те колоне. Уколико су координате \(i\) и \(j\) ван опсега, функција ће вратити \(-1\).

Пример

Нека је \(N = 3\), \(K = 9\) и нека су висине планина у матрици:

3 9 9
2 2 7
7 5 8

За нпр. упит \(Pitaj(2, 1)\), одговор би био \(2\); за упит \(Pitaj(2, 3)\) одговор би био \(7\); за упит \(Pitaj(3, 3)\) одговор би био \(8\) итд. Једино решење за овај пример је планина у пресеку друге врсте и треће колоне (висина 7) и ваша функција мора да врати низ \((2, 3)\) користећи не више од \(9\) упита.

Ограничења

• Висине свих планина су природни бројеви из сегмента \([1, 10^9]\).

Подзадаци

• Подзадатак 1 [4 поена]: \(N = 100\), \(K = 10.000\)
• Подзадатак 2 [9 поена]: \(N = 1.000\), \(K = 1.000.000\)
• Подзадатак 3 [12 поена]: \(N = 1.000\), \(K = 5.000\), висине планина су \(1\), \(2\) ili \(3\)
• Подзадатак 4 [18 поена]: \(N = 1.000\), \(K = 501.500\)
• Подзадатак 5 [19 поена]: \(N = 2.048\), \(K = 360.000\)
• Подзадатак 6 [14 поена]: \(N = 3.000\), \(K = 12.000\)
• Подзадатак 7 [24 поена]: \(N = 100.000\), \(K = 400.000\)

Детаљи имплементације

Потребно је да пошаљете тачно један фајл planine.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

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

Ваша функција може користити функцију

int Pitaj(int i, int j);

Да би функција Pitaj била “видљива” вашој функцији Nadji, потребно је додати линију #include "code.h" на почетку фајла који садржи имплементацију функције Nadji.

Тестирање и експериментисање

Уз задатак, обезбеђен вам је “template” фајл code.cpp који можете користити и мењати по потреби. Такође вам је обезбеђени програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду бројеве \(N\) и \(K\)
• У наредних \(N\) редова по \(N\) бројева који представљају висине планина

а затим позива вашу функцију са учитаним параметрима \(N\) и \(K\). На крају, на стандардни излаз штампа, редом, бројеве \(x\), \(y\) и \(T\), где су \(x\) и \(y\) редни број врсте и колоне које је вратила ваша функција а \(T\) број позива функцији Pitaj. Кодове ових програма можете мењати по потреби. Не гарантује се да ће за тестирање бити коришћена баш ова верзија програма grader.cpp.