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

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

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

• \(Resi(N, M, Q, V, А[\ldots][\ldots], B[\ldots], X1[\ldots], Y1[\ldots], X2[\ldots], Y2[\ldots], O[\ldots])\)

која треба да обради све упите и да смести решења упита у низ \(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\)) да се нађе исправан број пута.

Ограничења

• \(N, M \leq 840\)
• \(Q \leq 10000\)
• \(V \leq 100000\)
• \(1 \leq A_{i, j} \leq V\)
• \(0 \leq B_i \leq N \cdot M\)
• У упитима код којих је \(Y_2 = -1\) важи \(1 \leq X_1 \leq N, 1 \leq Y_1 \leq M, 1 \leq X_2 \leq V\)
• У осталим упитима важи \(1 \leq X_1 \leq X_2 \leq N, 1 \leq Y_1 \leq Y_2 \leq M\)

Подзадаци

• Подзадатак 1 [7 поена]: \(N, M, Q, V \leq 100\).
• Подзадатак 2 [12 поена]: \(V \leq 100\), нема злих духова.
• Подзадатак 3 [15 поена]: \(V \leq 50\).
• Подзадатак 4 [17 поена]: \(Q \leq 400\).
• Подзадатак 5 [21 поен]: \(N, M \leq 400\).
• Подзадатак 6 [28 поена]: Нема додатних ограничења.

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

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

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

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

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

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

• У првом реду бројеве \(N, M, Q, V\),
• У наредних \(N\) редова по \(M\) бројева, елементе матрице \(A\),
• У наредном реду \(V\) бројева, елементе низа \(B\),
• У наредних \(Q\) редова 4 или 5 бројева:
• • Први број је тип упита (1 - попис, 2 - зли дух)
• • У случају пописа преостала 4 броја су \(X1, Y1, X2, Y2\).
• • У случају злог духа 3 броја, \(X, Y, Z\), \((X, Y)\) је позиција у матрици а \(Z\) је нова вредност.

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