Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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:

  • 1 x y, for this operation, you should replace all the occurrences of element x in the array with y
  • 2 idx, output the value A[idx]

Input

Input starts with an integer T, denoting the number of test cases. The first line of each case contains two integers n and q. The next line contains n space separated integers A1, A2, A3, … , An forming the initial array.

Each of next q lines contains operations described above.

1 ≤ T ≤ 10
1 ≤ n, q ≤ 100000
1 ≤ Ai, x, y ≤ 100000
1 ≤ idx ≤ n

Output

For each test case, print “Case t:” (without quotes. t is the test case number) in the first line. Then for each 2nd type of operation, output the answer.

Samples

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

Discussion

ThunderingHerd Earliest, 2018-05-24 15:39:40.24 +0000 UTC

kissu_parina Fastest, 157704.5s

solaimanope Lightest, 3.1 MB

ShadowMe Shortest, 865B

Submit

Login to submit