AT_abc425_c [ABC425C] Rotate and Sum Query

You are given an integer sequence $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ . Process $ Q $ queries in order. There are two types of queries, given in the following formats: - `1 c`: Perform the operation of moving the first element of $ A $ to the end $ c $ times. - `2 l r`: Output the value of $ \displaystyle \sum_{i=l}^r A_i $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ Each query $ \text{query}_i $ is given in one of the following two formats: > $ 1 $ $ c $ > $ 2 $ $ l $ $ r $

Following the instructions in the problem statement, output the answers to the second type queries, separated by newlines.

### Sample Explanation 1 Each query is processed as follows: - First query: $ A_1+A_2+A_3=3+1+4=8 $ , so output $ 8 $ . - Second query: $ A=(3,1,4,5) $ changes to $ A=(1,4,5,3) $ . - Third query: $ A_2+A_3=4+5=9 $ , so output $ 9 $ . ### Constraints - $ 1\le N\le 2\times 10^5 $ - $ 1\le Q\le 2\times 10^5 $ - $ 1\le A_i \le 10^9 $ - $ 1\le c\le N $ - $ 1\le l\le r \le N $ - At least one query of the second type exists. - All input values are integers.