ZOJ Problem Set - 4009
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.
For each query, output one line containing one integer, indicating the answer.
1 5 3 1 2 3 4 5 2 1 5 1 1 3 2 1 3
Author: CHEN, Jingbang
Source: ZOJ Monthly, March 2018