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

By Matrix.code · 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 xx in the array with yy
  • 2 idx, output the value A[idx]A[idx]

Input

Input starts with an integer TT (1T101 \le T \le 10), denoting the number of test cases.

The first line of each case contains two integers nn and qq (1n,q1000001 \le n, q \le 100000). The next line contains nn space separated integers A1A_1, A2A_2, A3A_3, ..., AnA_n (1Ai1000001 \le A_i ≤ 100000) forming the initial array.

Each of the next qq lines contains the described operations:

  • 1 x y: 1x,y1000001 \le x, y \le 100000
  • 2 idx: 1idxn1 \le idx \le n

Output

For each test case, print Case t:\texttt{Case t:} (t\texttt{t} is the test case number) in the first line. Then for each 2nd type of operation, output the answer.

Sample

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

Statistics


52% Solution Ratio

ThunderingHerdEarliest, May '18

user.705840Fastest, 0.1s

KhaledFarhatLightest, 2.8 MB

abid1729Shortest, 752B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.