Каждый месяц Блейк получает отчёт об основных показателях деятельности компании «Blake Technologies». Компания производит n продуктов, поэтому в отчёте указано n целых чисел — выручка по каждому из этих продуктов. Однако перед тем, как этот отчёт попадёт в руки Блейка, он проходит нелёгкий путь через m менеджеров. Каждый из менеджеров, прежде чем передать отчёт следующему менеджеру (или Блейку), может переставить некоторые числа по своему усмотрению. А именно: i-й менеджер сортирует первые ri чисел в порядке неубывания или невозрастания, после чего передаёт отчёт менеджеру с номером i + 1, если i < m, или Блейку, если i = m.
Сейчас как раз настал момент, когда сотрудники составляют очередной отчёт для Блейка. Вам известна изначальная последовательность длины n, а также дано описание каждого менеджера, то есть значение ri и какой порядок сортировки он предпочитает. Вас попросили ускорить процесс и сразу определить итоговый вид отчёта.
Выходные данные
В единственной строке выведите n целых чисел — итоговый отчёт, который попадёт к Блейку.
Примечание
В первом примере изначально отчёт выглядел так: 1 2 3. После первого менеджера были переставлены первые два числа: 2 1 3. В таком виде отчёт попал к Блейку.
Во втором примере первоначально отчёт был таким: 1 2 4 3. После первого менеджера отчёт стал таким: 4 2 1 3. После второго менеджера отчёт стал выглядеть так: 2 4 1 3. Такой отчёт был передан Блейку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
1 2 3
2 2
|
2 1 3
|
|
2
|
4 2
1 2 4 3
2 3
1 2
|
2 4 1 3
|