Extraterestrii invadeaza Pamantul! Din fericire, avem la cine apela: eroul guitaitor al omenirii, Por Costel! El are un plan genial ce implica folie de aluminiu si multe capsatoare dar are nevoie si de ajutorul vostru.

Invazia extraterestrilor are loc in mai multe faze. Ea este concentrata asupra unei zone de N kilometri (ne imaginam kilometrii numerotati de la stanga la dreapta incepand cu 1). Invazia consta in evenimente de tipul urmator:

Invazia extraterestrilor are loc in mai multe faze. Ea este concentrata asupra unei zone de <tex>N</tex> kilometri (ne imaginam kilometrii numerotati de la stanga la dreapta incepand cu 1). Invazia consta in evenimente de tipul urmator:

* O nava extraterestra intra in atmosfera si stationeaza la distanta z de sol, intinzandu-se intre kilometrii x si y. Ultima nava extraterestra intrata in atmosfera paraseste atmosfera
* Tot ce are nevoie Por Costel de la voi este sa implementati un radar. El are nevoie ca radar-ul sa-i comunice la anumite momente de timp care este cea mai apropiata nava extraterestra de sol in dreptul kilometrului x.

* O nava extraterestra intra in atmosfera si stationeaza la distanta <tex>z</tex> de sol, intinzandu-se intre kilometrii <tex>x</tex> si <tex>y</tex>.
* Ultima nava extraterestra intrata in atmosfera paraseste atmosfera
 
Tot ce are nevoie Por Costel de la voi este sa implementati un radar. El are nevoie ca radar-ul sa-i comunice la anumite momente de timp inaltimea la care se afla cea mai apropiata nava extraterestra de sol in dreptul kilometrului <tex>x</tex>.

h2. Date de intrare

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

Fişierul de intrare $invazia.in$ va contine pe prima linie <tex>N</tex> si <tex>M</tex> (numarul de evenimente). Urmatoarele <tex>M</tex> linii descriu cate un eveniment:
 
* caracterul 'I' urmat de 3 numere intregi x y z - apare o noua nava extraterestra
* caracterul 'E'       - dispare o nava extraterestra
* caracterul 'R' urmat de un numar intreg x     - query de radar

h2. Date de ieşire

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

În fişierul de ieşire $invazia.out$ se vor afla <tex>r</tex> linii ce contin raspunsurile pentru fiecare query de radar. In cazul in care nu exista nici o nava in dreptul kilometrului <tex>x</tex> se va afisa mesajul "GUITZZZ!" (fara ghilimele).

h2. Restricţii

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

* <tex>1</tex> &le; N &le; <tex>3*10^5</tex>
* <tex>1</tex> &le; M &le; <tex>5*10^5</tex>
* <tex>1</tex> &le; <tex>x</tex> &le; <tex>y</tex> &le; <tex>N</tex> pentru orice operatie I
* <tex>1</tex> &le; <tex>z</tex> &le; <tex>10^9</tex> pentru orice operatie I
* <tex>1</tex> &le; <tex>x</tex> &le; <tex>N</tex> pentru orice operatie R
* Se garanteaza ca pentru orice operatie de tipul E exista cel putin o nava extraterestra in atmosfera

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

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

| 12 6
I 1 7 10
R 3
I 1 12 1
E
I 5 12 2
R 7
| 10
2

|
== include(page="template/taskfooter" task_id="invazia") ==

10326