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

Pe prima linie se găsesc două numere $N$ şi $Q$. Pe următoarele $N$ linii se găsesc câte două numere, <tex> ${x}_{i}, {y}_{i}$ </tex> 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 <tex> ${a}_{i}$ </tex> şi <tex> ${t}_{i}$ </tex>. Dacă <tex> ${a}_{i}$ </tex> este $1$, atunci este descrisă o operaţie de tip split folosind valoarea <tex> ${t}_{i}$ </tex>. Dacă <tex> ${a}_{i}$ </tex> este $2$, atunci este descrisă o operaţie de tip skip unde este folosită valoarea <tex> ${t}_{i}$ </tex>.

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

h2. Restricţii
* $1 ≤ N, Q ≤ 500 000$

* $1 &le;$ <tex> ${x}_{i}, {y}_{i}, {t}_{i}$ </tex> $&le; 1 000 000$, oricare ar fi $1 &le; i &le; Q$.
* $1 &le;$ <tex> ${a}_{i}$ </tex> $&le; 2$, oricare ar fi $1 &le; i &le; Q$.

* $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$

| $1 ≤ N, Q ≤ 200$
$N = 1$
$N, Q ≤ 1000$

<tex> ${x}_{i} $\leq$ {x}_{i+1}, {y}_{i} $\leq$ {y}_{i+1}$ </tex> pentru $1 &le; i &lt; N$.
$1 &le; N &le; 50 000$ şi <tex> ${x}_{i}, {y}_{i}, {t}_{i}$ </tex> $&le; 50 000$.

$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.
|