Влад захотел потренероваться в сортировке. Владу дан массив из n целых чисел.
У Влада есть m запросов вида l r t, где числа l и r - начало и конец сортируемого подотрезка массива, а t - порядок сортировки (если t равен 1 - сортируем по неубыванию, если 2 - по невозрастанию).
Формат входных данных
В первой строке два натуральных числа меньших 300 - n и m.
Далее даны n целых чисел. Модуль каждого из чисел не больше 1000.
Следом в m строках описаны сами запросы в формате l r t, где (1 \leq l \leq r \leq n, 1 \leq t \leq 2).
Формат выходных данных
Требуется вывести массив после сортировки.
Примеры
| стандартный ввод | стандартный вывод |
|---|
| 6 2
1 6 3 4 2 5
1 3 1
4 6 2
| 1 3 6 5 4 2
|