Stelele Informaticii 2024 - Mirror Day 2 | Castaniade

Ai văzut că lucrurile rele se întâmplă ușor.
Sigur e economic. Ca atunci când pui etichete; pun etichete: Cerul este senin în fiecare zi a anului că așa m-a învățat la școală.
Poate nu e senin în fiecare zi a anului.
--- Ion Durduroiu, Dialogurile Puterii

Ți-ai cumpărat un joc de la Noriel. În acesta sunt $N$ pioni. Se spune că fiecare pion deține o mulțime de jetoane $S_i$ și are o înălțime $H_i$. $S_i$ va fi mereu o mulțime $\{L_i, L_i + 1, \dots, R_i\}$.

Magia acestor pioni e că ei se joacă singuri. Adică, îi cumperi și doar te uiți la ei, ca la televizor.

Într-o tură, doi pioni $i$ și $j$ sunt desemnați să se întâlnească. Apoi, dacă $card(\Delta(S_i, S_j)) = |card(S_i) - card(S_j)|^1$, oricare din $i$ și $j$ poate să își modifice înălțimea cât să fie egală cu cea de-a celuilalt. Dacă nu se îndeplinește condiția, nimic nu se va întâmpla.

Instructiunile de pe cutie spun că jocul poate fi oprit oricând. Cu toate acestea, ai observat că în momentul în care oprești tabla de joc, pionii încep să se revolte, făcând un turn punându-se unul peste celălalt, creând un Mega-Pion care are înălțimea egală cu suma tuturor pioniilor componenti.

$^1$: Se notează cu $\Delta(A, B)$ mulțimea tuturor elementelor care aparțin exact unuia din $A$ și $B$. Se notează de asemenea cu $card(S)$ numărul de elemente din mulțimea respectivă.

Cerință

Cu astea în minte, știi că există cineva foarte malefic care a cumpărat acest joc și l-a lăsat să ruleze într-o cămară, cu intenția de a-l opri când vede că Mega-Pionul rezultant ar avea înălțimea maximă. Astfel, vrei să alertezi autoritățile responsabile cu înălțimea maximă pe care o poate lua un Mega-Pion pentru a putea apăra țara de această foarte reală amenințare. Cu toate acestea, acest joc vine în multiple ediții, astfel trebuind să afli care este cazul maximal pentru fiecare.

Date de intrare

În prima linie a fișierului de intrare se dă $T$, numărul de ediții diferite în care vine acest joc. Urmează $T$ descrieri ale unui joc, în prima linie a unei asemenea descrieri aflându-se $N$, numărul de pioni cu care vine jocul respectiv. Urmează apoi $N$ linii, descrierile fiecărui pion din joc prin $L_i$, $R_i$ și $H_i$.

Date de ieșire

Se va afișa o singură linie pentru fiecare ediție, anume înălțimea maximă a unui Mega-Pion ce poate fi format conform regulilor turelor jocului.

Restricții și precizări

• $1 \le T \le 5 \ 000$;
• $1 \le N \le 200 \ 000$;
• $\sum{N} \le 200 \ 000$, unde cu $\sum{N}$ s-a notat suma tuturor $N$-urilor în cadrul unui singur test;
• $1 \le H_i \le 1 \ 000 \ 000 \ 000$;
• $1 \le L_i \le R_i \le 1 \ 000 \ 000 \ 000$.

S-a notat cu $\sum{\max{R_i}^2}$ suma pătratului valorii maxime a unui $R_i$ din cadrul unei ediții peste toate edițiile date într-un test.

Exemplu

stdin

3
8
6 14 1
11 13 8
3 8 4
1 7 9
5 16 8
4 12 8
2 9 9
10 15 5
3
1 2 1
2 3 3
2 2 2
3
1 1 1
2 2 1
3 3 2

stdout

67
9
4

Explicație

În prima ediție posibilă a jocului, pionii pot face următoarele mutări pentru a obține maximalitatea înălțimii Mega-Pionului:

1. Al $3$-lea se întâlnește cu al $7$-lea pion, apropriindu-i înălțimea.
2. Al $8$-lea se întâlnește cu al $2$-lea pion, apropriindu-i înălțimea.
3. Al $1$-lea se întâlnește cu al $5$-lea pion, apropriindu-i înălțimea.

Ilustrație