elimin

Se consideră un şir de $n$ numere naturale $x_1, x_2, ..., x_n$ asupra căruia se execută succesiv $m$ operaţii de eliminare. O operaţie de eliminare constă din alegerea a doi indici $i, j$ ($1 \leq i \leq j \leq$ numărul de elemente din şir) şi eliminarea din şir a celui mai mare element din subsecvenţa $x_i, x_{i+1}, ..., x_j$. Dacă sunt mai multe elemente de valoare maximă se va elimina cel cu indicele cel mai mic. După fiecare eliminare se renumerotează termenii şirului (indicii elementelor de după cel eliminat vor fi decrementaţi cu $1$).

Cerinţă

Determinaţi subşirul rămas după cele $m$ operaţii de eliminare.

Date de intrare

Pe prima linie a fişierului de intrare elimin.in sunt scrise două numere naturale separate printr-un spaţiu $n \ m$, reprezentând numărul de elemente din şirul iniţial şi respectiv numărul de operaţii de eliminare. Pe următoarele $n$ linii sunt scrise numerele şirului iniţial, câte unul pe linie. Fiecare dintre ultimele $m$ linii conţin două numere naturale separate printr-un spaţiu $i \ j$ reprezentând indicii între care se execută o operaţie de eliminare. Mai exact, pe linia $1+n+k$ ($1 \leq k \leq m$) este scris intervalul corespunzător celei de-a $k$-a eliminări ($1 \leq i \leq j \leq n-k+1$).

Date de ieșire

În fişierul de ieşire elimin.out se vor scrie cele $n-m$ numere rămase, respectând ordinea iniţială, câte un număr pe o linie.

Restricții și precizări

• $2 \leq n \leq 1 \ 000 \ 000$
• $1 \leq m \leq \min(n-1, 500 \ 000 )$
• Termenii şirului sunt numere naturale din intervalul $[1, 300 \ 000 ]$

Exemplul 1

elimin.in

8 5
3
7
2
5
8
5
9
4
2 5
6 6
3 6
2 5
1 2

elimin.out

2
5
4