h2. Restricţii

* $0 ≤ N ≤ 2.000$

* $0 ≤ N ≤ 1.000$
* $0 ≤ Q ≤ 2.000$

* $1 ≤ L{~i~} ≤ R{~i~} ≤ N$

* Rick nu este obligat să folosească la programarea device-ului său doar stări cuprinse între 1 şi N + Q, el se poate folosi de stări intermediare oricât de diverse, atâta vreme cât în final este respectată condiţia din enunţ$
* Daca rezolvati cu maxim $2N + 2QlogN$ muchii atunci veti primi 70% din punctaj, daca rezolvati cu maxim $4N + 2Q$ muchii veti primi 100% din punctaj.

* Rick poate să folosească la programarea device-ului său doar stări cuprinse între $1$ şi $10.000$.
* Dacă rezolvaţi cu maxim $2N + 2QlogN$ muchii atunci veţi primi 40% din punctaj, dacă rezolvaţi cu maxim $4N + 2Q$ muchii veţi primi 100% din punctaj.

h2. Subtaskuri
* *$Subtaskul 1 (25 de puncte):$* Toate intervalele sunt fie prefixe fie sufixe.

* *$Subtaskul 2 (25 de puncte):$* Toate intervalele au cel o pozitie comuna.
* *$Subtaskul 3 (50 de puncte):$* Fara restrictii suplimentare.

* *$Subtaskul 2 (25 de puncte):$* Toate intervalele au cel o poziţie comună.
* *$Subtaskul 3 (50 de puncte):$* Fără restricţii suplimentare.

h3. Explicaţie

...

În exemplul pe care Rick vi-l arată, el se foloseşte de starea 8, pentru a reduce complexitatea device-ului. Într-adevăr, pentru fiecare stare din cele Q se poate ajunge strict la intervalul de stări specificat în fişierul de intrare. Device-ul fiind creat de el, acesta este evident bine făcut.

== include(page="template/taskfooter" task_id="transform3") ==