问题描述

⼩杨有⼀个包含n 个正整数的序列 。 ⼩杨计划对序列进⾏多次升序排序，每次升序排序⼩杨会选择⼀个区间 [l,r]（l<=r ）并对区间内所有数字，即 a1,a2,......an 进⾏升序排序。每次升序排序会在上⼀次升序排序的结果上进⾏。 ⼩杨想请你计算出多次升序排序后的序列。

输入

第⼀⾏包含⼀个正整数n ，含义如题⾯所⽰。 第⼆⾏包含n 个正整数a1,a2,......an ，代表序列。 第三⾏包含⼀个正整数q ，代表排序次数。 之后 ⾏，每⾏包含两个正整数 l,r,代表将区间[l,r] 内所有数字进⾏升序排序。

输出

输出⼀⾏包含 n个正整数，代表多次升序排序后的序列。

样例

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

1 3 4 5 2

Limitation

对于全部数据，保证有 。 1<=n,q,ai<=100