AT_past202303_o 区間ソートクエリ

There is a sequence of $ N $ integers between $ 0 $ and $ 10 $ , inclusive: $ A = (A_1, A_2, \dots, A_N) $ . Process $ Q $ queries described below in the order they are given. Each query has three integers $ C $ , $ L $ , and $ R $ . Do the following according to the value of $ C $ . - If $ C = 1 $ : sort $ A_L, A_{L+1}, \dots, A_R $ in ascending order. - If $ C = 2 $ : sort $ A_L, A_{L+1}, \dots, A_R $ in descending order. - If $ C = 3 $ : print $ \displaystyle \sum_{i=L}^R A_i $ .

The input is given from Standard Input in the following format, where $ \text{Query}_i $ denotes the $ i $ -th query: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ \text{Query}_1 $ $ \text{Query}_2 $ $ \vdots $ $ \text{Query}_Q $ Each query is in the following format: > $ C $ $ L $ $ R $

Print $ T $ lines, where $ T $ is the number of queries with $ C = 3 $ . The $ i $ -th line $ (1 \leq i \leq T) $ should contain the answer to the $ i $ -th query with $ C = 3 $ .

### Sample Explanation 1 Initially, $ A = (1, 0, 8, 2, 10) $ . For the first query, the answer is $ 0 + 8 + 2 = 10 $ . After the second query, $ A $ is $ (0, 1, 2, 8, 10) $ . For the third query, the answer is $ 1 + 2 + 8 = 11 $ . After the fourth query, $ A $ is $ (0, 1, 10, 8, 2) $ . For the fifth query, the answer is $ 1 + 10 + 8 = 19 $ . ### Constraints - $ 1 \leq N \leq 5 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^4 $ - $ 0 \leq A_i \leq 10 $ - $ 1 \leq C \leq 3 $ - $ 1 \leq L \leq R \leq N $ - All values in the input are integers.