D. Resto
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of size $$$n$$$, we consider

$$$$$$f(x) = (x \% a_1) + ((x \% a_1) \% a_2) + (((x \% a_1) \% a_2) \% a_3) + \ldots + ((\ldots (x \% a_1) \ldots) \% a_n)$$$$$$.

Where we define $$$x \% y$$$ as the remainder of the integer division of $$$x$$$ by $$$y$$$.

We also have $$$Q$$$ questions of two types.

  1. If the $$$i$$$-th question is of type 1, we will receive the integer $$$q_i$$$ and we must respond with $$$f(q_i)$$$.
  2. If the $$$i$$$-th question is of type 2, we will receive the integer $$$p$$$ and the integer $$$x$$$ and we will have to update the value of the $$$p$$$-th element to $$$x$$$ ($$$a_p = x$$$).
Input

The first line contains $$$T$$$, the number of cases.

Each case begins with two integers, $$$n$$$ and $$$Q$$$.

The next line of each case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

The following $$$Q$$$ lines of each case contain the questions. Each line begins with an integer representing the type of the question (1 or 2), followed by an integer $$$q_i$$$ if the question is of type 1 or two integers $$$p$$$, $$$x$$$ if it is of type 2.

Output

For each question of type 1, we must respond with a single line with $$$f(q_i)$$$.

Scoring
  1. (5 points) The sum of $$$n$$$ and the sum of $$$Q$$$ over all cases is less than or equal to $$$10^3$$$.
  2. (33 points) The sum of $$$a_i$$$ over all cases is less than or equal to $$$10^6$$$ and all questions are of type 1.
  3. (27 points) All questions are of type 1.
  4. (35 points) No additional restrictions.
Example
Input
2
3 2
2 1 1
1 3
1 4
3 3
6 4 2
1 5
2 2 5
1 5
Output
1 
0
7 
5
Note

$$$1 \le T \le 10^5$$$.

$$$1 \le n, Q \le 10^5$$$.

The sum of $$$n$$$ for all cases is at most $$$10^5$$$.

The sum of $$$Q$$$ for all cases is at most $$$10^5$$$.

$$$1 \le a_i, q_i \le 10^{11}$$$.

For each question of type 2, $$$1 \le p \le n$$$, $$$1 \le x \le 10^{11}$$$.