题面描述 小杨有一个包含n个正整数的序列a。 小杨计划对序列进行多次升序排序，每次升序排序小杨会选择一个区间l,r 并对区间内所有数字，即$al,a{l+1},...,a_r$进行升序排序。每次升序排序会在上一次升序排序的结果上进行。 小杨想请你计算出多次升序排序后的序列。

输入格式 第一行包含一个正整数n，含义如题面所示。 第二行包含n个正整数 $a_1,a_2,...,a_n$，代表序列。 第三行包含一个正整数q，代表排序次数。 之后q行，每行包含两个正整数$l_i,r_i$，代表将区间$[l_i,r_i]$ 内所有数字进行升序排序。

输出格式 输出一行包含n个正整数，代表多次升序排序后的序列。

输入样例

5
3 4 5 2 1
3
4 5
3 4
1 3

输出样例

1 3 4 5 2

样例解释 第一次升序排序后，序列为[3,4,5,1,2]； 第二次升序排序后，序列为[3,4,1,5,2]； 第三次升序排序后，序列为[1,3,4,5,2]；

数据范围 对于全部数据，保证有$1\le n\le 100,1\le a_i\le 100,1\le q\le 100,1\le l_i\le r_i\le n$。