В далекие времена, о которых никто не помнит, проходил турнир горцев. Турнир этот был не на жизнь, а на смерть, но за жизнь! В турнире принимали участие n горцев, выстроившихся в шеренгу. Каждый боец был наделен силой, сила i-го горца определялась величиной pi, при этом отметим, что не было горцев с одинаковой силой. Сам турнир проводился в m этапов. До начала каждого сражения великий вождь Гыда выбирал несколько подряд выстроившихся горцев из шеренги. Выбранная группа начинала сражение, где каждый сражался сам за себя, побеждал сильнейший. После битвы победитель вставал на свое место в шеренге, затем шеренга смыкалась и бойцы опять стояли плечо к плечу. Вам требуется вывести силы бойцов в шеренге после окончания турнира.
Первая строка содержит два целых числа n и m. n — количество сражающихся горцев в турнире (1 ≤ n ≤ 2·105). m — количество проводимых сражений (1 ≤ m ≤ 105).
Следующая строка содержит показатели силы pi каждого горца (1 ≤ pi ≤ 109).
Следующие m строк содержат пары чисел l и r (l ≤ r), которые задают диапазон номеров горцев, сражающихся в шеренге.
Выведите силы бойцов в шеренге после окончания турнира.
7 4
48 1 57 25 69 26 88
1 2
2 3
2 5
1 2
88
10 3
8 27 4 1 9 2 10 66 43 13
1 4
1 2
2 4
27 66 43 13
