stergeri

Stergeri

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

Poveste si cerinta...

Magicianul Dino a scris pe o foaie in ordine numerele naturale de la $1$ la $N$ (adica $1 2 3 .. N$). Frasinel a ales doi indici $x$ si $y$ $(x ≤ y)$ si Dino a sters toate elementele aflate intre pozitiile $x$ si $y$. Apoi Dino ii spune lui Frasinel sa aleaga alti doi inidici si va realiza acelasi lucru pentru elementele ramase scrise pe foaie. Dupa $M$ operatii de acest tip, Frasinel ar vrea sa stie ce element se afla pe pozitia $K$ pe foaie.

h2. Date de intrare

Fisierul de intrare $stergeri.in$ ...

Fisierul de intrare $stergeri.in$ contine pe prima linie numerele $N M K$ avand semnificatia din enunt. Urmeaza $M$ linii ce contin doua numere intregi $x y$ reprezentand indicii din operatia efectuata de Frasinel.

h2. Date de iesire

In fisierul de iesire $stergeri.out$ ...

In fisierul de iesire $stergeri.out$ se afla pe prima linie un numar $SOL$, reprezentand numarul care se afla pe foaie la pozitia $K$ dupa efectuarea tuturor operatiilor.

h2. Restrictii

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

* $1 ≤ N ≤ 2 000 000 000$
* $1 ≤ M ≤ 100 000$
* $K$ va fi cel mult numarul de elemente ramase la sfarsit pe foaie

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

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

| 12 2 3
  4 7
  2 6
| 12

|
h3. Explicatie

...

Dupa prima operatie foaia arata asa: $1 2 3 8 9 10 11 12$. Dupa cea de-a doua operatie: $1 11 12$. Deci pe pozitia $3$ se afla numarul $12$.

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

2606