问题描述

给定 $n$ 个整数 $a_1,a_2,\dots,a_n$，然后你有 $m$ 次操作，每次操作为将 $a_l\sim a_r$ 进行升序排序，操作结束后，输出序列 $a$。

输入格式

第一行输入两个正整数 $n,m$。 $(1\le n\le 100,1\le m\le 100)$

第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$。 $(1\le a_i\le 100)$

接下来 $m$ 行，每行输入两个正整数 $l,r$，表示将 $a_l\sim a_r$ 进行排序。$(1\le l\le r\le n)$

输出格式

输出一行，共 $n$ 个整数，表示序列 $a$。

样例输入

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

样例输出

3 2 4 1 5