7. Nevítaný hosť s chlpatým kožuchom

Bzučiakov zdanlivo jednoduchý plán sa nakoniec nečakane skomplikoval. Ó nie nie, celú krádež a únik zvládol triviálne! Hoci sa mu podarilo infiltrovať diskrétny banket, ukradnúť identitu a dokonca prejsť cez pasovú kontrolu na Vesmírnom Belize so zabudntým pasom, jeho fatálnou chybou bolo nechať si kúpu zvlhčovača vzduchu na poslednú chvíľu.

Na Vesmírnom Belize sa zvlhčovače vzduchu zháňajú ťažšie než identita samotnej Jednotky. A o jeho preferovanej luxusnej značke môže Bzučiak len snívať. Jediné, čo sa mu podarilo získať, bol zjavne použitý zvlhčovač od pofidérneho predajcu vedľa smetiakov za benzínkou – a to ešte za premrštenú cenu!

S ťažkým srdcom sa Bzučiak vrátil do hotelovej izby, odhodlaný tešiť sa aspoň z toho mála, čo má. Jeho tešba však trvala len krátko. Ešte predtým, ako stihol zvlhčovač zapnúť, si všimol, že s ním niečo nie je v poriadku. Po otvorení zistil, že vnútro prístroja je celé zelené a ochlpatené – vesmírna pleseň!

Bzučiak stál pred dilemou. Zohnať náhradný zvlhčovač by bolo takmer také náročné ako vykonať celú predchádzajúcu lúpež. Na druhej strane, používať plesnivý zvlhčovač by bolo mimoriadne zdraviu škodlivé. Po chvíli váhania sa rozhodol pre kompromis – postaví zvlhčovač na balkón, nechá naň svietiť žeravé slnká trojhviezdneho systému Belize a fúkať slaný morský vzduch a hádam tá pleseň skape. V takýchto nepriaznivých podmienkach predsa nemôže dlho prežiť…

Úloha

Povrch zvlhčovača vzduchu predstavuje (z pohľadu plesňe nekonečnú) mriežku. Na niektorých políčkach mriežky sa na začiatku nachádza pleseň. Zhora na mriežku praží horúce slnko, zľava fúka vysušujúci vietor. Kvôli týmto nepriaznivým podmienkam pleseň postupne vymiera, no predtým, než úplne zanikne, sa pokúsi o posledný akt sebazáchovy.

Kolónia plesne sa správa podľa nasledujúcich pravidiel:

1. Ak na plesnivé políčko priamo pôsobí aj slnko aj vietor (t.j. nemá plesnivých susedov ani zhora, ani zľava), život je pre ňu príliš ťažký a pleseň na tomto políčku v nasledujúcej sekunde zahynie.
2. Ak na prázdne políčko priamo nepôsobí ani slnko, ani vietor (t.j. má plesnivých susedov zhora aj zľava), vznikajú na ňom ideálne podmienky a v nasledujúcej sekunde sa tam pleseň rozšíri.
3. Všetky ostatné políčka zostávajú v nasledujúcej sekunde nezmenené.
4. Všetky zmeny v rámci jednej sekundy sa dejú súčasne.

Kolóniu plesne vieme reprezentovať ako množinu obdĺžnikových plôch. Plesnivá oblasť so súradnicami \((x_1, y_1, x_2, y_2)\) obsahuje všetky políčka súradníc \((x, y)\) takých, že \(x_1 \leq x \leq x_2\) a \(y_1 \leq y \leq y_2\). Plesnivé plochy sa môžu prekrývať, avšak v tom prípade je na danom políčku pleseň len raz.

Otázkou teda zostáva, pri počiatočnej konfigurácii plesne, koľko sekúnd potrvá kým všetka pleseň zahynie a Bzučiak bude môcť konečne začať používať svoj zvlhčovač?

Formát vstupu

Na prvom riadku vstupe je číslo \(T\) (\(1 \leq T \leq 100\)) udávajúce počet testovacích prípadov. Nasleduje \(T\) testovacích prípadov, pričom každý z nich je zadaný nasledovne:

Na prvom riadku je číslo \(N\) (\(1 \leq N \leq 50\,000\)) udávajúce počet plesnivých plôch. Nasleduje \(N\) riadkov, v každom z nich sú štyri celé čísla \(x_1\), \(y_1\), \(x_2\) a \(y_2\) (\(1 \leq x_1 \leq x_2 \leq 10^9\), \(1 \leq y_1 \leq y_2 \leq 10^9\)) udávajúce súradnice plesnivej obdĺžnikovej plochy.

Súradnice rastú smerom dole a doprava.

Nech \(\sum N\) je súčet \(N\) pre všetky testovacie prípady v jednom vstupe. Vstupy úlohy budú rozdelené do 5 sád, v ktorých platia nasledujúce obmedzenia:

1. \(T \leq 20\), \(N \leq 10\), \(x_2, y_2 \leq 100\)
2. \(\sum N \leq 1\,000\), \(x_2, y_2 \leq 10^6\), súčet plôch všetkých obdĺžnikov \(\leq 4*10^6\)
3. \(N \leq 2\,500\), \(\sum N \leq 5\,000\)
4. \(\sum N \leq 50\,000\), plochy sa neprekrývajú
5. \(\sum N \leq 50\,000\)

Formát výstupu

Pre každý testovací prípad vypíšte jedno číslo – počet sekúnd, ktoré potrvá, kým všetka pleseň zahynie.

Príklady

Input:

3
1
1 1 5 1
1
1 1 1 5
1
1 1 3 3

Output:

5
5
5

Input:

1
3
4 1 4 1
2 2 3 2
1 2 1 4

Output:

6

Nech A, B, C sú plesnivé oblasti súradníc (4, 1, 4, 1), (2, 2, 3, 2) a (1, 2, 1, 4). Nech P je pleseň ktorá voči minulej sekunde prežila a n je pleseň ktorá sa narodila. V nasledujúcich sekundách bude pleseň vyzerať takto:

...A  1s  ....  2s  ....  3s  ....  4s  ....  5s  ....  6s  ....
CBB.  -\  .PPn  -\  ..PP  -\  ...P  -\  ....  -\  ....  -\  ....
C...  -/  Pn..  -/  .Pn.  -/  ..Pn  -/  ...P  -/  ....  -/  ....
C...      P...      Pn..      .Pn.      ..Pn      ...P      ....

Input:

1
4
49 8 66 93
62 4 67 99
38 61 58 81
58 2 60 66

Output:

110

Keď sa pekne spýtate ChatGPT-4o, tak vám tento vstup nakreslí. Na takéto veci je AI veľmi fajn, avšak nepoužívajte ju priamo na riešenie a programovanie úloh.

Poznámka

Bol by som rád keby ste túto úlohu skúsili vyriešiť a naprogramovať (na čo najviac bodov). Aj keď je to sedmička, nie je mimoriadne ťažké získať viac ako polovicu bodov. Ak sa úlohu pokúšate riešiť na plný počet bodov, tak odporúčame programovať v C++ a popis napísať poriadne a zrozumiteľne.