AT_abc476_e [ABC476E] Min-Max Swap

$ (1,2,\ldots,N) $ の順列 $ P=(P_1,P_2,\ldots,P_N) $ と長さ $ M $ の整数列 $ L=(L_1,L_2,\ldots,L_M),\ R=(R_1,R_2,\ldots,R_M) $ が与えられます。 この順列 $ P $ に対し、 $ i=1,2,\ldots,M $ の順に以下の操作を行います： - $ P_{L_i},P_{L_i+1},\ldots,P_{R_i} $ のうち、最小の値をもつ要素と最大の値をもつ要素の位置を入れ替える。 $ M $ 回の操作が終わった後の $ P $ の各要素を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_M $ $ R_M $

$ M $ 回の操作が終わった後の $ P $ の各要素を先頭から順に空白区切りで出力せよ。

### Sample Explanation 1 はじめ $ P=(3,1,4,2,5) $ です。 - $ i=1 $ のとき： $ P_1,P_2,P_3 $ のうち、最小の値は $ P_2 $ で最大の値は $ P_3 $ です。 $ P_2 $ と $ P_3 $ を入れ替え、 $ P=(3,4,1,2,5) $ となります。 - $ i=2 $ のとき： $ P_1,P_2,P_3,P_4,P_5 $ のうち、最小の値は $ P_3 $ で最大の値は $ P_5 $ です。 $ P_3 $ と $ P_5 $ を入れ替え、 $ P=(3,4,5,2,1) $ となります。 - $ i=3 $ のとき： $ P_1,P_2,P_3,P_4 $ のうち、最小の値は $ P_4 $ で最大の値は $ P_3 $ です。 $ P_3 $ と $ P_4 $ を入れ替え、 $ P=(3,4,2,5,1) $ となります。 $ 3 $ 回の操作が終わったあと $ P=(3,4,2,5,1) $ となります。 ### Constraints - $ 2\le N\le 2\times 10^5 $ - $ 1\le M\le 2\times 10^5 $ - $ P $ は $ (1,2,\ldots,N) $ の順列 - $ 1\le L_i < R_i\le N $ - 入力される値は全て整数