== 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 <tex> $({x}_{i}, {y}_{i})$ </tex>, dacă se respectă condiţia <tex> ${x}_{i}$ $<$ t $<$ ${y}_{i}$ </tex>, 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") ==