AT_abc476_e [ABC476E] Min-Max Swap

You are given a permutation $ P=(P_1,P_2,\ldots,P_N) $ of $ (1,2,\ldots,N) $ and length- $ M $ integer sequences $ L=(L_1,L_2,\ldots,L_M) $ and $ R=(R_1,R_2,\ldots,R_M) $ . For this permutation $ P $ , perform the following operation for $ i=1,2,\ldots,M $ in this order: - Among $ P_{L_i},P_{L_i+1},\ldots,P_{R_i} $ , swap the positions of the element with the minimum value and the element with the maximum value. Find each element of $ P $ after the $ M $ operations.

The input is given from Standard Input in the following format: > $ N $ $ M $ > $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $ > $ L_1 $ $ R_1 $ > $ L_2 $ $ R_2 $ > $ \vdots $ > $ L_M $ $ R_M $

Output each element of $ P $ after the $ M $ operations, in order from front to back, separated by spaces.

### Sample Explanation 1 Initially, $ P=(3,1,4,2,5) $ . - For $ i=1 $ : among $ P_1,P_2,P_3 $ , the minimum value is $ P_2 $ and the maximum value is $ P_3 $ . Swapping $ P_2 $ and $ P_3 $ gives $ P=(3,4,1,2,5) $ . - For $ i=2 $ : among $ P_1,P_2,P_3,P_4,P_5 $ , the minimum value is $ P_3 $ and the maximum value is $ P_5 $ . Swapping $ P_3 $ and $ P_5 $ gives $ P=(3,4,5,2,1) $ . - For $ i=3 $ : among $ P_1,P_2,P_3,P_4 $ , the minimum value is $ P_4 $ and the maximum value is $ P_3 $ . Swapping $ P_3 $ and $ P_4 $ gives $ P=(3,4,2,5,1) $ . After the three operations, $ P=(3,4,2,5,1) $ . ### Constraints - $ 2\le N\le 2\times 10^5 $ - $ 1\le M\le 2\times 10^5 $ - $ P $ is a permutation of $ (1,2,\ldots,N) $ . - $ 1\le L_i < R_i\le N $ - All input values are integers.