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ţ$
* Pentru teste în valoare $
* Pentru alte teste în valoare de$
* Pentru alte teste în valoare de$
* Pentru alte teste în valoare de  nu există restricţii suplimentare

* 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 poziţie comună.
* *$Subtaskul 3 (50 de puncte):$* Fără restricţii suplimentare.
 
 

h2. Exemplu
table(example). |_. transform3.in |_. transform3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 3
  1 3
  2 3
  3 4
| 7
  5 1
  5 8
  8 2
  8 3
  6 8
  7 3
  7 4

|
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") ==