Array Query Processor

You are given one or more test cases. In each test case, you are provided with an array of integers and a sequence of queries to perform on this array. There are three types of queries:

1. Query type 1: "1 i k" – Add k to the element at index i. In mathematical notation: $$A_i \leftarrow A_i + k$$.
2. Query type 2: "2 i" – Output the value of the element at index i.
3. Query type 3: "3 i j" – Output the sum of the elements from index i to j (inclusive). In notation: $$\sum_{k=i}^{j} A_k$$.

Note that the indices are 0-indexed. Process the queries in order for each test case and output the results for every query that requires output (types 2 and 3).

inputFormat

The first line of input contains an integer T, the number of test cases. For each test case, the first line contains two integers N and Q, where N is the number of elements in the array and Q is the number of queries. The second line contains N space-separated integers, the initial elements of the array. Each of the following Q lines represents a query in one of the following formats:

• For a type 1 query: 1 i k
• For a type 2 query: 2 i
• For a type 3 query: 3 i j

All input is read from standard input (stdin).

outputFormat

For each query that requires an output (query types 2 and 3), print the result on a new line. The outputs should be printed to standard output (stdout) in the order of processing the queries.## sample

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

13
19