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

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

Date de ieșire

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

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

Subtask 1 (9 puncte)

• 1 ≤ N, Q ≤ 200

Subtask 2 (12 puncte)

• N = 1

Subtask 3 (13 puncte)

• N, Q ≤ 1 000

Subtask 4 (12 puncte)

• $x_i ≤ x_{i+1}, y_i ≤ y_{i+1}$ pentru 1 ≤ i < N

Subtask 5 (11 puncte)

• 1 ≤ N ≤ 50 000 și $x_i, y_i, t_i ≤ 50 \ 000$

Subtask 6 (19 puncte)

• 1 ≤ N ≤ 100 000

Subtask 7 (24 puncte)

• Nu există alte restricții

Exemple

stdin

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

stdout

10

Explicații

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.