Петар има огроман воћњак шљива који је идеално организовао тако да су шљиве поређане у \(N\) редова (врста) и \(N\) колона. Висине свих стабала су позитивни цели бројеви. Не постоје два стабла исте висине. При томе је стабла тако обликовао тако да за сваку врсту важи да висине стабала слева надесно образују растући или опадајући низ (могу постојати врсте поређане у растућем, али исто тако и врсте поређане у опадајућем поретку, на потпуно случајан начин поређане). Слично за сваку колону важи да висине стабала од првог према последњем образују растући или опадајући низ (могу постојати колоне у којима су поређане у растућем поретку и колоне у којима су поређане у опадајућем поретку, али поредак вама није познат). Врсте су нумерисане бројевима од \(1\) до \(N\), а колоне бројевима од \(1\) до \(N\). На располагању имате функцију (касније ће бити детаљно описана) којом можете добити висину стабла које се налази у одређеној врсти и колони (зваћемо ту функцију упит). Потребно је да са што мање упита одредите да ли у воћњаку постоји стабло задате висине и позицију тог стабла, ако постоји (редни број врсте и редни број колоне). Зато ће бити задат природан број \(К\). Ако ваш програм у не више од \(К\) упита одговори тачно сматра се да је ваш програм коректно решио тај тест пример, у супротном, сматра се да је решење примера нетачно.

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

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

• \(Resi(N, K, V, I, J)\)

која треба да одреди да ли се у воћњаку са \(N\) врста и \(N\) колона налази стабло висине \(V\) и ако се налази одреди редни број врсте и редни број колоне у коме се налази стабло висине \(V\). Ако стабло не постоји, онда вредности за редни број врсте и редни број колоне треба да буду 0. \(K\) је предвиђени број упита.

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

• \(DajVisinu(I, J)\)

која треба да врати висину стабла које се налази у врсти \(I\) и коони \(J\). Ако координате \(I\) и \(J\) нису у дозвољеним границама, функција враћа вредност \(-1\).

Пример

Нека је \(N = 4, K = 16, V = 9\), а матрица са висинама стабала:

3 6 10 15
5 9 13 18
31 27 23 20
45 28 32 25

Ако је први упит био за поље \((2, 4)\) одговор би био \(18\). Ако је други упит за поље \((2,1)\) одговор би био \(5\). Коначно, ако је трећи упит за поље \((2,2)\) одговор би био 9, па би ваша функција могла да врати решење \(I=2\), \(J=2\).

Ограничења

• \(N \leq 1000\)
• \(К \leq 10000\)
• Висине стабала си између \(1\) и \(100.000.000\)

Подзадаци

• Подзадатак 1 [8 поена]: \(N \leq 100\), \(К = N \times N\).
• Подзадатак 2 [14 поена]: \(N \leq 1.000\), \(K = 10.000\).
• Подзадатак 3 [24 поена]: \(N \leq 1.000\), \(K = 6.000\).
• Подзадатак 4 [54 поена]: \(N \leq 1.000\), \(К = 4.000\).

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

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

У зависности од програмског језика који користите, ваша функција/процедура мора бити следећег облика:

У зависности од програмског језика који користите, ваша функција/процедура може користити фукнцију:

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

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

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

Затим овај програм зове вашу функцију и штампа бројеве \(I\), \(J\) и \(T\). \(I, J\) су редни број врсте и колоне које је вратила ваша функција, а \(T\) је број позива функције \(DajVisinu\). Кодове ових програма можете мењати по потреби, али ће за тестирање бити коришћена оригинална верзија ових програма.