You are required to maintain a sequence supporting the following two types of operations:

1.     Given m and x, you have to modify the m^th element to x.

2.     Given m and k, you have to output what the m^th element was after the k^th operation.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line consists of two integers N and M representing the length of sequence and the number of operations. The next line consists of N integers A_i indicating the i^th element in the sequence before any operations. Then M lines follow, each line starts with an integer o representing the type of the operation, if o is 1 then two integers m and x follow, if o is 2 then two integers m and k follow.

 Limits

·       1 ≤ N, M ≤ 10⁵.

·       -10⁹ ≤ A_i ≤ 10⁹.

·       1 ≤ o ≤ 2 for every operation.

·       1 ≤ m ≤ N for every operation.

·       -10⁹ ≤ x ≤ 10⁹ for every operation of type 1.

·       k is guaranteed to be valid for every operation of type 2.

·       1 ≤ T × (N + M) ≤ 4×10⁵.

For each test case, first output one line containing “Case #x:”, where x is the test case number.

Then for every operation of type 2, output one line consists of one integer, which is the m^th element after the k^th operation.

2
1 4
2
1 1 2
2 1 1
1 1 6
2 1 3
5 6
4 3 0 2 6
2 3 0
1 2 9
2 2 1
2 2 3
1 5 8
2 5 5

Case #1:
2
6
Case #2:
0
3
9
8