Fişierul intrare/ieşire:	kth.in, kth.out	Sursă	Algoritmiada 2017, Runda Finala, Juniors
Autor	Eugenie Daniel Posdarascu	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	0.5 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Kth

Se da un vector V cu N elemente. Asupra acestui vector aplicam M operatii de 2 tipuri:

• Operatia de tip 0: se da un interval [A, B] si un numar K. Sortam elementele din interval in ordine crescatoare dupa valoare, dupa care le inlocuim cu cea de a K-a valoare din acest interval.
• Operatia de tip 1: se da un interval [A, B] si un numar K. Toate elementele din acest interval sunt inlocuite cu valoarea K

Sa se afiseze vectorul de N elemente la finalul celor M operatii.

Date de intrare

Fişierul de intrare kth.in va contine pe prima linie 2 numere naturale N si M. Pe a 2-a linie vor fi N numere naturale, reprezentand vectorul initial. Urmatoarele M linii descriu update-urile. Un update consta din 4 numere: tip_update, A, B si K

Date de ieşire

Fişierul de ieşire kth.out va contine N numere naturale aflate pe o singura linie, reprezentand vectorul V in urma celor M update-uri.

Restricţii

• 1 ≤ N, M ≤ 100.000
• 1 ≤ K ≤ B - A + 1 pentru operatiile de tip 0
• Valorile initiale din vector, precum si valorile K de la operatiile de tip 1 vor fi cuprinse in intervalul [1, 100.000]

Exemplu

Cum se trimit solutii?