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

Сейчас как раз настал момент, когда сотрудники составляют очередной отчёт для Блейка. Вам известна изначальная последовательность длины n, а также дано описание каждого менеджера, то есть значение r_i и какой порядок сортировки он предпочитает. Вас попросили ускорить процесс и сразу определить итоговый вид отчёта.