Rezolvare PBinfo #4285

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.