== include(page="template/taskheader" task_id="gugustiuc") ==

Gimi Guguştiucul tocmai a ajuns intr-o situaţie destul de complicată. El are de participat la $N$ şedinţe, a $i$-a şedinţă desfaşurându-se în intervalul de timp deschis la capete <tex> $({x}_{i}, {y}_{i})$ </tex>. El poate participa la mai multe şedinţe simultan, fiind online.

Gimi Guguştiucul tocmai a ajuns intr-o situaţie destul de complicată. El are de participat la $N$ şedinţe, a $i$-a şedinţă desfaşurându-se în intervalul de timp deschis la capete $(x{~i~}, y{~i~})$. El poate participa la mai multe şedinţe simultan, fiind online.

Pentru a-şi simplica programul, Gimi a decis să ia nişte pauze şi să elimine cateva şedinţe (să nu mai participe deloc la ele). El a aplicat o listă de $Q$ operaţii, nu neapărat foarte inspirate:

* **split t**: Gimi va lua o pauză la momentul de timp $t$. Deci, pentru fiecare şedinţa din intervalul de timp <tex> $({x}_{i}, {y}_{i})$ </tex>, dacă se respectă condiţia <tex> ${x}_{i}$ $<$ t $<$ ${y}_{i}$ </tex>, atunci şedinţa respectivă este eliminată şi înlocuită cu două şedinţe noi în intervalele de timp deschise la capete <tex> $({x}_{i}, t)$ </tex> şi <tex> $(t, {y}_{i})$ </tex>
* **skip t**: Gimi nu va mai participa deloc la toate şedinţele care sunt în plină desfaşurare la momentul
de timp t. Cu alte cuvinte, pentru fiecare fiecare şedinţă din intervalul de timp (xi
, yi), dacă se
respectă condiţia xi < t < yi
, atunci Gimi va elimina şedinţa.

* **split $t$**: Gimi va lua o pauză la momentul de timp $t$. Deci, pentru fiecare şedinţa din intervalul de timp $(x{~i~}, y{~i~})$, dacă se respectă condiţia $x{~i~} < t < y{~i~}$, atunci şedinţa respectivă este eliminată şi înlocuită cu două şedinţe noi în intervalele de timp deschise la capete $(x{~i~}, t)$ şi $(t, y{~i~})$.
* **skip $t$**: Gimi nu va mai participa deloc la toate şedinţele care sunt în plină desfaşurare la momentul de timp $t$. Cu alte cuvinte, pentru fiecare fiecare şedinţă din intervalul de timp $(x{~i~}, y{~i~})$, dacă se respectă condiţia $x{~i~} < t < y{~i~}$, atunci Gimi va elimina şedinţa.
Gimi vrea să ştie dupa cele $Q$ operaţii care este suma duratelor tuturor şedinţelor ramase. Durata unei şedinţe din intervalul de timp $(x, y)$ se defineşte ca fiind $y − x$. Duratele şedinţelor se adună în întregime, chiar dacă există intervale de timp pe care acestea se suprapun.

h2. Date de intrare

Fişierul de intrare $gugustiuc.in$ ...

Pe prima linie se găsesc două numere $N$ şi $Q$. Pe următoarele $N$ linii se găsesc câte două numere, $x{~i~}, y{~i~}$ pe fiecare linie, acestea reprezentând câte un interval în care se desfăşoară o şedinţă. Pe următoarele $Q$ linii se găsesc câte două numere $a{~i~}$ şi $t{~i~}$. Dacă $a{~i~}$ este $1$, atunci este descrisă o operaţie de tip split folosind valoarea $t{~i~}$. Dacă $a{~i~}$ este $2$, atunci este descrisă o operaţie de tip skip unde este folosită valoarea $t{~i~}$.

h2. Date de ieşire

În fişierul de ieşire $gugustiuc.out$ ...

Se va afişa un singur număr reprezentând suma duratelor tuturor şedinţelor ramase, după aplicarea celor $Q$ operaţii.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, Q ≤ 500 000$
* $1 ≤ x{~i~}, y{~i~}, t{~i~} ≤ 1 000 000$, oricare ar fi $1 ≤ i ≤ Q$.
* $1 ≤ a{~i~} ≤ 2$, oricare ar fi $1 ≤ i ≤ Q$.
 
|_. # |_. Punctaj |_. Restricţii |
| $1$
$2$
$3$
$4$
$5$
$6$
$7$
| $9$
$12$
$13$
$12$
$11$
$19$
$24$
| $1 ≤ N, Q ≤ 200$
$N = 1$
$N, Q ≤ 1000$
$x{~i~} ≤ x{~i+1~}, y{~i~} ≤ y{~i+1~}$ pentru $1 ≤ i < N$.
$1 ≤ N ≤ 50 000$ şi $x{~i~}, y{~i~}, t{~i~} ≤ 50 000$.
$1 ≤ N ≤ 100 000$
Nu există alte restricţii.
|

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

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

| 2 3
1 10
4 10
1 3
1 6
2 5
| 10

|
h3. Explicaţie

...

Gimi are două şedinţe în intervalele de timp $(1, 10)$ şi $(4, 10)$.
 
După prima operaţie, el elimină şedinţa din intervalul $(1, 10)$ şi adăugă două şedinţe noi în intervalele de timp $(1, 3)$ şi $(3, 10)$. Acum are trei şedinţe la intervalele de timp $(1, 3), (3, 10)$ şi $(4, 10)$.
 
După a doua operaţie, Gimi elimină şedinţa din intervalul $(3, 10)$ şi adăugă două şedinţe noi în intervalele de timp $(3, 6)$ şi $(6, 10)$. De asemenea, Gimi elimină şedinţa din intervalul $(4, 10)$ şi se adaugă şedinţele $(4, 6)$ şi $(6, 10)$. Acum are cinci şedinţe la intervalele de timp $(1, 3), (3, 6)$ şi $(6, 10), (4, 6)$ şi $(6, 10)$.
 
După ultima operaţie, Gimi elimină şedinţa de la intervalul de timp $(3, 6)$ şi şedinţa de la intervalul de timp $(4, 6)$. Rămân şedinţele de la intervalele de timp $(1, 3), (6, 10)$ şi încă una tot la intervalul de timp $(6, 10)$.
 
Suma duratelor tuturor şedinţelor ramase va fi $(3 − 1) + (10 − 6) + (10 − 6) = 10$.

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