1700 - Sequence

Time Limit : 2 Second

Memory Limit : 256 MB

Submission: 10

Solved: 6

Description

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


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


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


 


 

Input

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 Ai indicating the ith 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 ≤ 105.


·       -109 ≤ Ai ≤ 109.


·       1 ≤ o ≤ 2 for every operation.


·       1 ≤ m ≤ N for every operation.


·       -109 ≤ x ≤ 109 for every operation of type 1.


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


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

Output

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 mth element after the kth operation.

sample input
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
sample output
Case #1:
2
6
Case #2:
0
3
9
8
hint
source
Lalatina
© 2015 HUST ACMICPC TEAM. All Right Reserved.