Unbelievable Array

Limits 1s, 512 MB

You will be given an array A of n integers and q operations. There are two types of operations:

Input

Input starts with an integer TT (1T101 \le T \le 10), denoting the number of test cases.

The first line of each case contains two integers nn and qq (1n,q1000001 \le n, q \le 100000). The next line contains nn space separated integers A1A_1, A2A_2, A3A_3, …, AnA_n (1Ai1000001 \le A_i ≤ 100000) forming the initial array.

Each of the next qq lines contains the described operations:

Output

For each test case, print Case t:\texttt{Case t:} (t\texttt{t} is the test case number) in the first line. Then for each 2nd type of operation, output the answer.

Sample

InputOutput
1
5 4
1 2 3 4 5
1 1 3
2 1
1 3 5
2 1
Case 1:
3
5

After the first update:

A = {3, 2, 3, 4, 5}
A[1] = 3

After the second update:

A = {5, 2, 5, 4, 5}
A[1] = 5