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

Добили сте приступ бази података о распрострањености вируса у вашем граду, из које се може закључити пуно корисних података о ширењу болести. Град је подељен на поља која чине матрицу са \(N\) редова и \(M\) колона, и вредност \(A_{i,j}\) у бази представља број случајева вируса у пољу \((i, j)\).

Одлучили сте да пронађете број најздравијих поља, односно поља која садрже мањи или једнак број случајева од сваког поља у матрици. Да би учинили анализу занимљивијом, пало вам је на памет да је поновите \(Q\) пута, и да сваки пут одаберете неки правоугаони део града који ћете игнорисати.

Опис улаза

Прва линија стандардног улаза садржи три природна броја: број редова и колона у граду \(N\) и \(M\), као и број упита \(Q\).

Наредних \(N\) линија садрже по \(M\) бројева \(A_{i,j}\) који чине матрицу бројева случајева вируса.

Наредних \(Q\) линија садрже по четири броја \(i\), \(j\), \(h\) и \(w\), који описују део града који треба игнорисати када тражите најздравија поља у том упиту: горње лево поље је у \(i\)-тој врсти и \(j\)-тој колони (где \((1,1)\) одговара горњем левом углу града), \(h\) је висина дела (број врста) а \(w\) ширина (број колона).

Опис излаза

На стандардни излаз исписати \(Q\) линија са по једним природним бројем, где \(i\)-та линија садржи број најздравијих поља у граду без дела описаног у \(i\)-том упиту.

Пример 1

Улаз

3 3 3
1 2 3
1 1 2
3 3 3
1 1 1 1
1 1 2 2
2 2 1 1

Излаз

2
1
2

Пример 2

Улаз

3 3 1
1 2 3
2 1 3
1 9 1
2 2 1 1

Излаз

3

Објашњење примера

У првом примеру, у првом упиту посматрамо цео град осим горњег левог поља. Најздравија поља су у овом случају она која имају само један случај, и таквих има два (осим игнорисаног). У другом упиту посматрамо само крању десну колону и последњи ред, где је најздравије једино поље са два случаја. У последњем упиту игноришемо централно поље, и остају два са по једним случајем.

Напомене

Због великог улаза, није препоручљиво користити спорије методе учитавања података, као што су cin/cout без синхронизације у C++-у.

Ограничења

Тест примери су подељени у пет подзадатака: