INFOMANIA 2023 round 1, educational edition | John Mex

Odată, într-un tărâm îndepărtat, trăia un porc numit John Pork. El nu avea niciodată un telefon, dar dorea să vorbească cu oamenii și să aibă prieteni. John Pork și-a făcut multe planuri și a economisit bani pentru a-și cumpăra primul său telefon. După multe eforturi, a reușit să-și cumpere un telefon mobil. Era atât de emoționat încât nu putea să-și țină bucuria pentru el. A început să sune oamenii, dar nimeni nu i-a răspuns. Totuși, John Pork nu a renunțat.
-chat gpt

Cerință

Se dă o matrice $N$ x $M$ care conține toate valorile de la $1$ la $N$ x $M$.
Se dau $Q$ query-uri de forma:

$query(x1, y1, x2, y2) = {MEX}^1$-ul dreptunghiului $(x1, y1, x2, y2)$, unde $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 mex.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 mex.out printați $Q$ linii, reprezentând răspunsurile la query-uri, în ordine.

Restricții și precizări

• $N, M \le 1000$;
• $Q \le 2 \times 10^5$;
• $^1{MEX}$-ul unui set de valori este definit în această problema drept valoarea naturală nenulă minimă care nu se regăsește în acel set.
• Pentru $20$ din punctaj: $N, M \le 50$ și $Q \le 1000$.

Exemplu

mex.in

5 5
14 24 12 8 18 
22 10 17 9 19 
15  3  2 6  1 
20  7 25 11 4
13 23 16 21 5
3
1 1 5 5
3 2 3 5
4 4 5 5

mex.out

26
4
1