题目描述

序列a有n个元素，第i个元素为a[i],对序列a做如下m次操作,每次操作给定x和y,当x为1时,则将序列a的前y个数按照从小到大排序;当x为2时,则将序列a的前y个数按照从大到小排列。请输出经过m次操作后的序列a。

输入格式

第一行两个整数n和m，分别表示序列a的长度和操作次数。

第二行n个数表示序列a的每个元素。

接下来m行，每行两个数x和y，如题目描述。

输出格式

经过m次操作后的序列a。

输入数据 1

3 1

1 2 3

2 2

输出数据 1

2 1 3

数据范围

1≤n,m≤200000,1≤a[i]≤10^9