Pracsiu Dan (dnprx) Se dă un șir a1, a2, …, an de numere întregi și m operații, fiecare operație fiind dată printr-o pereche de numere op și k: dacă op = 1 atunci primele k elemente din șir se ordonează crescător, iar dacă op = 2 atunci primele k elemente din șir se ordonează descrescător.
Cerința
Să se afișeze elementele șirului după efectuarea tuturor celor m operații.
Date de intrare
Fișierul de intrare report.in conține pe prima linie numerele n și m, iar pe a doua linie, separate prin câte un spațiu, sunt elementele șirului a1, a2, …, an. Pe următoarele m linii se află câte două numere op k reprezentând câte o operație. Dacă op = 1, atunci primele k elemente din șir se ordonează crescător, iar dacă op = 2 atunci primele k elemente din șir se ordonează descrescător.
Date de ieșire
Fișierul de ieșire report.out va conține pe prima linie, separate prin câte un spațiu, elementele șirului după efectuarea celor m operații.
Restricții și precizări
1 ≤ n, m ≤ 200.000-1.000.000.000 ≤ a[i] ≤ 1.000.000.000
Exemplu:
report.in
4 2 1 2 4 3 2 3 1 2
report.out
2 4 1 3
Explicație
Șirul inițial este 1 2 4 3. Prima operație este 2 3, adică primele trei elemente se ordonează descrescător, deci șirul devine 4 2 1 3. A doua operație este 1 2, adică primele două elemente se ordonează crescător, deci șirul devine 2 4 1 3.