INFOMANIA 2023 round 1, educational edition | John Miex

ATENȚIE: Această problema are un enunț similar cu John Mex, dar este fundamental diferită. Citiți cu atenție enunțul! (nu și povestea)

John Pork era un porc humanoid singuratic, marginalizat de societate și fără prieteni. În speranța de a face noi cunoștințe, a organizat o petrecere, dar nimeni nu a venit. Simțindu-se izolat și neînțeles, John a încercat să îi sune pe puținii prieteni pe care îi avea, dar nimeni nu a răspuns. Printre aceștia se afla și cea mai bună prietenă a sa, un alt porc humanoid numit Betty.
John a început să se retragă tot mai mult, izolându-se în apartamentul său și refuzând orice conexiune cu lumea exterioară. Singura sa alinare era telefonul, pe care îl ținea strâns, sperând ca cineva, oricine, să îl sune.
Dar telefonul a rămas tăcut, un amar amintitor al singurătății și izolării lui John. În cele din urmă, s-a întâmplat ceva ciudat. O voce cunoscută i-a răspuns la telefon, era Betty, cea mai bună prietenă a sa. John a fost uimit și fericit să audă vocea ei, dar în același timp, era și confuz. Cum a aflat ea că îl căuta?
Betty i-a explicat că nu a putut să vină la petrecerea sa deoarece era ocupată cu o altă activitate, dar că îl aprecia mult și era mereu acolo pentru el. John a fost emoționat și recunoscător, simțindu-se mai puțin singur decât înainte.
-chat gpt

Cerință

Se dă o matrice $N$ x $M$.
Se dau $Q$ query-uri de forma:

$query(x1, y1, x2, y2) =$ $MIEX^1$-ul dreptunghiului $(x1, y1, x2, y2)$.
$x1$ și $x2$ sunt linii, iar $y1$ si $y2$ sunt coloane, $x1 \le x2$ și $y1 \le y2$

Date de intrare

Pe prima linie a fișierului miex.in se află $N$ și $M$.
Pe următoarele $N$ linii se află câte $M$ numere, reprezentant matricea.
Pe următoarea linie se află $Q$, numărul de query-uri.
Pe următoarele $Q$ linii se află tuplete de numere de formă: x1 y1 x2 y2, reprezentând query-urile.

Date de ieșire

În fișierul miex.out printați $Q$ linii, reprezentând răspunsurile la query-uri, în ordine.

Restricții și precizări

• $N, M \le 500$
• $Q \le 2 \times 10^4$
• $1 \le$ valorile $\le N \times M$
• o valoare poate apărea de mai multe ori în matrice!!!
• $^1MIEX$-ul unui set de valori este definit în această problema drept valoarea naturală nenulă minimă care are frecvența pară.
• Pentru $20$ din punctaj: $N, M \le 50$ și $Q \le 1000$

Exemplu

miex.in

5 5
1 3 2 5 4
4 4 6 9 10
3 2 8 1 10
1 2 3 4 5
12 12 3 4 5
4
1 1 2 3
4 1 4 5
1 1 5 5
3 2 4 3

miex.out

4
6
3
1