2017年华中科技大学ACM招新赛

From: 2016-12-18 12:30:00 To: 2016-12-18 17:30:00 Now: 2017-09-24 21:45:18 Status: Public

I - Sequence

Time Limit: 2s Memory Limit: 256MB

Submissions: 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