Time Limit: 7 Seconds
Memory Limit: 262144 KB
Given \(n\) integers \(a_1, a_2, \dots, a_n\). There are 2 types of operations:
For each query, please output the answer.
There are multiple test cases. The first line of the input is an integer \(T\) (about 5), indicating the number of test cases. For each test case:
The first line contains two integers \(n\) (\(1 \le n \le 10^5\)) and \(q\) (\(1 \le q \le 10^5\)), indicating the number of the given integers and the number of operations.
The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^9\)), indicating the given integers.
The first integer on each of the following \(Q\) lines will be \(op\) (\(1 \le op \le 2\)), indicating the type of operation.