题目描述

文艺平衡树是一种数据结构，用于维护一个有序序列。其中需要提供以下操作：翻转一个区间，例如原有序列是$\{5,4,3,2,1\}$，翻转区间是 $[2,4]$ ，结果为 $\{5,2,3,4,1\}$；原有序列是$\{5,4,3,2,1\}$，翻转区间是 $[1,5]$ ，结果为 $\{1,2,3,4,5\}$。

小 Z 在考场上飞速打出了文艺平衡树的模板，但是他一不小心把原数列弄丢了，现在只有操作后的数列，请你帮他还原出原数列吧。

输入格式

第一行包含两个正整数 $n,m$ 分别表示数列的长度和操作次数。

第二行包含 $n$ 个正整数，表示小 Z 操作后的数列。

接下来 $m$ 行，每行包含两个正整数 $l,r$ ，代表小 Z 翻转区间了 $[l,r]$。

输出格式

共一行，包含 $n$ 个正整数，表示原始数列。

样例

5 1
5 2 3 4 1
2 4

5 4 3 2 1

样例 1 解释

$\{5,4,3,2,1\}$ $[2,4]$ -> $\{5,2,3,4,1\}$

5 2
5 2 3 4 1
2 4
1 3

3 4 5 2 1

样例 2 解释

$\{3,4,5,2,1\}$ $[2,4]$ -> $\{3,2,5,4,1\}$ $[1,3]$ -> $\{5,2,3,4,1\}$

数据范围

对于全部数据保证：$1 \le n,m \le 100,1 \le a_i \le 10000$ 且保证 $l < r$ 。