Time Limit: 2s
Memory Limit: 256MB
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^{5}.
· -10^{9} ≤ A_{i} ≤ 10^{9}.
· 1 ≤ o ≤ 2 for every operation.
· 1 ≤ m ≤ N for every operation.
· -10^{9} ≤ x ≤ 10^{9} for every operation of type 1.
· k is guaranteed to be valid for every operation of type 2.
· 1 ≤ T × (N + M) ≤ 4×10^{5}.
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