Ramazan bestämde sig för att ge sig in i en seriös verksamhet: att odla kål.
Fältet där kålen odlas är ett oändligt rutnät. Ett kålhuvud kan planteras i varje ruta.
Ramazan planterade bara en del av fältet. Han planerade att använda flera rektangulära områden, och det visade sig att vissa av dem kunde överlappa varandra. En ruta tillhör odlingen om den ligger i minst en av rektanglarna.
Formellt valde Ramazan $n$ rektangulära områden $(x_i^L,y_i^L,x_i^R,y_i^R)$ ($x_i^L\le x_i^R$, $y_i^L\le y_i^R$, $1\le i\le n$). Rutan $(x,y)$ innehåller kål om det finns minst en vald rektangel $i$ ($1\le i\le n$) sådan att $x_i^L\le x\le x_i^R$ och $y_i^L\le y\le y_i^R$.
Tidigare var Ramazan programmerare (och vinnare), så han bestämde sig för att använda robotar med artificiell intelligens för att regelbundet sköta odlingen. En robot kan sköta ett godtyckligt horisontellt avsnitt av rutor $(x_1^{robot},x_2^{robot},y^{robot})$, det vill säga alla rutor $(x,y)$ sådana att $x_1^{robot}\le x\le x_2^{robot}$ och $y=y^{robot}$.
Det är viktigt att robotarna bara kör över odlade områden. Han insåg att man för att minimera antalet robotar måste använda horisontella avsnitt som inte kan utökas. Ramazan använder en robot för avsnittet $(x_1^{robot},x_2^{robot},y^{robot})$ om:
- Alla rutor $(x,y)$ sådana att $x_1^{robot}\le x\le x_2^{robot}$ och $y=y^{robot}$ tillhör odlingen.
- Rutan $(x_1^{robot}-1,y^{robot})$ inte tillhör odlingen.
- Rutan $(x_2^{robot}+1,y^{robot})$ inte tillhör odlingen.
Din uppgift är att samla viktig statistik om robotarna som ska arbeta på odlingen. Vi säger att paret $(x_1,x_2)$ betjänas på rad $y$ om det finns en robot som arbetar på exakt avsnittet $(x_1,x_2,y)$.
- Hitta alla par $(x_1,x_2)$ som betjänas på någon rad.
- För varje sådant par $(x_1,x_2)$, hitta antalet rader där det betjänas.
- För varje sådant par $(x_1,x_2)$, hitta det största antalet på varandra följande rader där det betjänas. Med andra ord, hitta det största talet $k$ sådant att det finns ett avsnitt av $k$ på varandra följande rader $[y_1,y_2]$ ($y_2-y_1+1=k$), där paret $(x_1,x_2)$ betjänas på varje rad $y_1\le y\le y_2$.
Indata
Varje test består av flera testfall. Den första raden innehåller ett heltal $t$ ($1\le t\le200\,000$), antalet testfall. Därefter följer beskrivningarna av testfallen.
Den första raden i varje testfall innehåller ett heltal $n$ ($1\le n\le200\,000$), antalet valda rektangulära områden.
De följande $n$ raderna innehåller vardera fyra heltal $x_i^L,y_i^L,x_i^R,y_i^R$ ($1\le x_i^L\le x_i^R\le10^9$, $1\le y_i^L\le y_i^R\le10^9$), beskrivningarna av de valda rektangulära områdena.
Låt $N$ beteckna summan av $n$ över alla testfall i ett test. Det garanteras att $N\le200\,000$.
Utdata
För varje testfall ska du först skriva ut ett heltal $p$ ($p\ge1$), antalet par $(x_1,x_2)$ som betjänas på någon rad.
På de följande $p$ raderna ska du skriva ut fyra heltal $x_1,x_2,cnt,k$ per rad ($1\le x_1\le x_2\le10^9$, $0\le cnt,k\le10^9$). Talet $cnt$ ska vara antalet rader där paret $(x_1,x_2)$ betjänas. Talet $k$ ska vara det största antalet på varandra följande rader där paret $(x_1,x_2)$ betjänas.
Alla par $(x_1,x_2)$ ska vara olika. Varje par som betjänas på någon rad ska skrivas ut exakt en gång. Paren får skrivas ut i valfri ordning.
Deluppgifter
För ett testfall låter vi $w$ beteckna fältets bredd, det vill säga $w=\max_{i=1}^n x_i^R$, och $h$ fältets höjd, det vill säga $h=\max_{i=1}^n y_i^R$.
| Deluppgift | Poäng | Begränsningar för $n,N$ | Begränsningar för $w,h$ | Ytterligare begränsningar | Nödvändiga deluppgifter |
|---|---|---|---|---|---|
| $1$ | $4$ | $n=1$ | |||
| $2$ | $8$ | $h=1$ | |||
| $3$ | $8$ | $n\le30,\ N\le3000$ | $w,h\le10$ | $t\le100$ | Exemplet |
| $4$ | $4$ | $w,h\le5000,\ \sum wh\le25\cdot10^6$ | Exemplet, $3$ | ||
| $5$ | $8$ | $N\le3000$ | Exemplet, $3$ | ||
| $6$ | $4$ | $N\le10\,000$ | Exemplet, $3,5$ | ||
| $7$ | $8$ | Alla $[x_i^L,x_i^R]$ överlappar | $1$ | ||
| $8$ | $8$ | $y_i^L=1$ | $2$ | ||
| $9$ | $8$ | Rektanglarna överlappar inte | $1$ | ||
| $10$ | $8$ | För alla $1\le i,j\le n$ och alla $y\in[y_i^L,y_i^R]\cap[y_j^L,y_j^R]$ gäller $[x_i^L,x_i^R]\nsubseteq[x_j^L,x_j^R]$ | $1,9$ | ||
| $11$ | $8$ | Alla intervall $[x_i^L,x_i^R+1]$ ligger antingen inuti varandra eller överlappar inte | $1$ | ||
| $12$ | $8$ | $N\le50\,000$ | Exemplet, $3$, $5$–$6$ | ||
| $13$ | $8$ | $N\le100\,000$ | Exemplet, $3$, $5$–$6$, $12$ | ||
| $14$ | $8$ | $N\le200\,000$ | Exemplet, $1$–$13$ |
- Om din lösning för ett test hittar fel mängd par $(x_1,x_2)$ som betjänas på någon rad får den bedömningen «Fel svar».
Om lösningen på alla tester i deluppgiften och dess nödvändiga deluppgifter:
- hittar rätt mängd men inte alla $cnt$ är korrekta får den $50\%$ av deluppgiftens poäng.
- hittar rätt mängd och alla $cnt$ är korrekta, men inte alla $k$ är korrekta, får den $75\%$ av deluppgiftens poäng.
- hittar rätt mängd och alla $cnt$ och $k$ är korrekta får den $100\%$ av deluppgiftens poäng.
Observera att du även för att få delpoäng måste skriva ut något värde på $cnt$ och $k$ för varje par $(x_1,x_2)$, men värdena behöver inte vara korrekta.
Exempel
Indata 1
4 2 2 2 3 3 3 3 4 4 2 2 1 2 3 1 2 3 2 4 2 2 4 5 3 4 9 7 2 9 9 10 7 1 9 7 7 2 1 2 9 5 1 6 8 4 5 7 6 1 8 4 10 1 6 3 6 1 2 7 3 4 1 7 1
Utdata 1
3 2 3 1 1 2 4 1 1 3 4 1 1 2 1 3 1 1 2 2 2 1 4 2 4 2 2 2 9 4 2 3 9 2 2 7 9 3 3 6 1 4 2 2 1 6 1 1 1 7 3 2 2 2 4 2 4 7 2 1 5 6 2 1
Förklaring
Det första och det andra testfallet i exemplet.
I det första testfallet används robotar på avsnitten $(2,3,2)$, $(2,4,3)$ och $(3,4,4)$. Alltså betjänas paren $(2,3)$, $(2,4)$ och $(3,4)$ på någon rad, och vart och ett betjänas på exakt en rad.
I det andra testfallet används robotar på avsnitten $(2,2,1)$, $(2,4,2)$ och $(2,2,3)$. Alltså betjänas paren $(2,2)$ och $(2,4)$ på någon rad. Paret $(2,2)$ betjänas på raderna $1,3$, och paret $(2,4)$ betjänas på rad $2$.
Det tredje och det fjärde testfallet i exemplet.