Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Ена ради у познатом супермаркету који је добио име по једној комутативној бинарној операцији на скупу реалних бројева. Недавно је супермаркет обијен па је потребно извршити попис робе. Супермаркет се може представити као матрица са \(N\) редова и \(M\) колона. Редови и колоне су индексирани од \(1\). У супермаркету се продаје \(V\) врста робе, које означавамо бројевима од \(1\) до \(V\). Ена је добила задатак да током неких од наредних \(Q\) дана попише неку правоугаону подматрицу. Њој је шеф дао списак \(B\) од \(V\) бројева, где \(B_i\) означава да артикал под редним бројем \(i\) треба у подматрици да се нађе тачно \(B_i\) пута. Енин задатак је да за неку подматрицу одреди колико врста артикала постоји тако да се тај артикал налази у тој подматрици тачно \(B_i\) пута, односно, колико различитих вредности \(i\) постоји тако да се број \(i\) појављује тачно \(B_i\) пута у подматрици. Међутим, ту није крај Ениним мукама! Зли духови с времена на време ваде артикле са неких места у матрици и стављају неке друге артикле (током тих дана Ена не мора да пописује робу). Ена има пуно обавеза па је овај задатак поверила вама.

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

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

која треба да обради све упите и да смести решења упита у низ \(O\). Матрица \(A\) садржи бројеве од \(1\) до \(V\) и описује почетно стање супермаркета. Низови \(X1, Y1, X2, Y2\) описују упите. Уколико је \(Y2[i] = -1\), тог дана је зли дух ушао у супермаркет и променио артикал на позицији \((X1[i], Y1[i])\) у артикал са редним бројем \(X2[i]\). У супротном, ако је \(Y2[i] \neq -1\), тог дана Ена треба да попише робу. Ако постоји \(T\) упита који означавају да се роба пописује, одговоре на ове упите упишите у истом редоследу у низ \(O\) на позицијама од \(1\) до \(T\). Сви низови су индексирани од 1.

Пример

Нека је \(N = 3, M = 4, Q = 3, V = 4\), низ \(B = [1, 2, 3, 4]\), а матрица \(A\) је: ~~~ 1 2 3 2 2 3 1 3 3 1 1 4 ~~~

Првог дана, Ена треба да попише подматрицу од поља \((1,2)\) до поља \((3,4)\), односно, подматрицу која се састоји од последње три колоне. Ена види да се артикал \(1\) налази три пута, артикал \(2\) се налази два пута, артикал \(3\) се налази \(3\) пута и артикал \(4\) се налази једном у овој подматрици. Од свих њих артикли \(2, 3\) се налазе исправан број пута - артикал \(2\) треба да се јави \(B_2 = 2\) пута, а артикал \(3\) треба \(B_3 = 3\) пута, па је одговор \(2\). Другог дана, зли дух мења артикал у доњем десном углу матрице у артикал \(2\), па ће следећег дана само један артикал (са редним бројем \(3\)) да се нађе исправан број пута.

Ограничења

Подзадаци

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

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

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

Језик Декларација функције
C++ void Resi(int N, int M, int Q, int V, int** A, int* B, int* X1, int* Y1, int* X2, int* Y2, int* O);
Pascal procedure Resi(N, M, Q, V : Longint; var A : Matrica; var B, X1, Y1, X2, Y2, O : Array of Longint);

За Pascal, Matrica је тип који је дефинисан као Array[1..1000, 1..1000] of Longint. Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.

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

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

Затим овај програм зове вашу функцију и штампа бројеве \(O[1], \ldots, O[T]\), сваки у посебном реду, где је \(T\) број “попис” упита. Кодове ових програма можете мењати по потреби.