CODECHEF Dish Owner

1-
                        CODECHEF

                              Dish Owner

This summer, there is a worldwide competition being held in Chef Town and some of the best chefs of the world are participating. The rules of this competition are quite simple.

Each participant needs to bring his or her best dish. The judges will initially assign a score to each of the dishes. Now, several rounds will follow. In each round, any two chefs will be called up on the stage. Each of the chefs can then choose any one dish to battle against the other chef and the one having the dish with the higher score will win this round. The winner of the round will also obtain all the dishes of the loser who will then be eliminated. In case both the dishes have equal scores, this round will be considered as a tie and nothing else will happen. Note that initially each chef will have only one dish and all the chefs play the rounds optimally.

Your task is to simulate and answer some queries related to this. You will be given N dishes numbered from 1 to N with the i^th dish belonging to the i^th chef initially. You will also be given an array S whereS[i] denotes the score given by the judges to the i^th dish before starting the rounds. You will have to answer Q queries, each of which can be of the following types : 

1. 0 x y : This denotes that the chef containing dish number x competes with the chef containing dish number y currently in this round. If a single chef is the owner of both the dishes, print "Invalid query!"(without quotes), otherwise execute and store the result of this round as described by the rules above. 

2. 1 x : You need to output the index of the chef containing dish x at this point.

Input

First line of input contains an integer T denoting the number of test cases. For each test case, the first line contains an integer N denoting the number of chefs in the contest. The next line contains N space separated integers where the i^th integer represents S[i]. The next line contains an integer Q denoting the number of queries. Q lines follow where each line can be of the format 0 x y or 1 x as described in the problem statement.

Output

For each test, print in each line the answer for the queries as described in the problem statement .

Constraints

• 1 ≤ T ≤ 25
• 1 ≤ N ≤ 10000(10⁴)
• 0 ≤ S[i] ≤ 1000000(10⁶)
• 1 ≤ Q ≤ 10000(10⁴)
• 1 ≤ x, y ≤ N

Example

Input:
1
2
1 2
2
0 1 2
1 1
Output:
2

Explanation

There are two chefs with scores of dishes 1 and 2 respectively. After the first query, chef 2 acquires dish1 since S[2] > S[1] . Hence, the answer for the second query, i.e owner of the first dish is chef 2.

****************************************************EDITORIAL*****************************************************************

PROBLEM:

N chef's are there. Each chef has a dish which is given a value (denoted by S[i]). You need to answer 2 queries :
1. 0 x y : Chef containing dish x competes with chef containing dish y. If both dishes belong to same chef print "Invalid Query!" , otherwise the winner of the round will obtain all the dishes of the loser which will then be eliminated.
2. 1 x : Output the chef which contains the dish x.

Explanation

This problem can be solved using Disjoint set data structures.

Union Find or Disjoint Set Data structures allow you to merge two sets of items together dynamically and maintain for each item - to which set set does it belong.

This is exactly what we need in the problem , i.e. dynamically merging two sets and querying which set does an element belong.

We will be using Disjoint Set Data Structure that supports the following :

1. find(A) : Get the id of the disjoint set to which A belongs(i.e. the chef id which contains that dish).
2. union(A,B) : Merge the two disjoint sets in which A and B belong respectively.

Initially, we will create N disjoint set , each set contains 1 dish and it's owner.
Let dish x be in setA and dish y be in setB.
If the dish contained by the owner of setA has score higher than the dish contained by the owner of setB , then we will merge setA and setB and set the owner of setA as the overall owner of the merged set.
If the dish contained by the owner of setB has score higher than the dish contained by the owner of setA , then we will merge setA and setB and set the owner of setB as the overall owner of the merged set.

Note : You can easily prove from this that the owner of the set has dish whose score is higher than all other dish of the set.
We will be using only Path Compression heuristics to solve the problem.

/*****************************************************CODE****************************************************

#include<iostream>

using namespace std;

typedef long long int lli;

#include<bits/stdc++.h>

lli par[1000000];

lli  maxi[1000000];

lli find(lli a)// PATH COMPRESSED FIND 

  {

    if(par[a]!=par[par[a]])

     {

      par[a]=find(par[a]);

     }

     return par[a];

  }

  

lli unioni(lli a,lli b,lli k,lli s)

 {

    //int  k=find(a);

    //int  s=find(b);

      if(maxi[k]>maxi[s])// MAX[K]>MAX[S]  ADD SET S TO SET SET K BY JUST CHANGING THERE PARENT 

       {

       

        maxi[s]=0;

        par[s]=par[k];

       }

       else

       {

        maxi[k]=0;

        par[k]=par[s];

       }

 }

 int main ()

{

int  t;

  //cin>>t;

  scanf("%d",&t);

     while(t--)

      {

        lli n;

  cin>>n;

  lli arr[n+10];

    for(int i=1;i<=n;i++)

 {

  //cin>>arr[i];

  scanf("%lld",&arr[i]);

   maxi[i]=arr[i];

//   rank[i]=0;

   par[i]=i;

 }

 lli q;

//  cin>>q;

scanf("%lld",&q);

  while(q--)

   {

       lli type;

        //cin>>type;

        scanf("%lld",&type);

         lli a,b;

          

           //cout<<"type "<<type<<" "<<a<<" "<<b<<endl;

          if(type==0)

           {

            //cin>>a>>b;

            scanf("%lld %lld",&a,&b);

           

            lli s=find(a);

            lli d=find(b);

           

            if(s==d)

             {

              cout<<"Invalid query!"<<endl;

             

             }

              if(maxi[s]==maxi[d])

             {

              continue;

             }

             else

            unioni(a,b,s,d);

           }

           else

            {

              //cin>>b;

              scanf("%lld",&b);

              cout<<par[find(b)]<<endl;

            }

         

      

   }

  

      }

      return 0;

}

/*********************************************

END************************************************************