#include <bits/stdc++.h>

#define ll long long
#define map unordered_map
#define set unordered_set
#define l_l pair<ll, ll>
#define P pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>
#define mp make_pair
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rev(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define revs(i, n) for (int i = ((int)(n)); i > 0; --i)
// template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
// template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

// template <class T> void plus_mod(T &a, const T &b) {a = (a + b) % MOD;}

struct UnionFind {
  vector<ll> data;

  UnionFind(ll sz) { data.assign(sz, -1); }

  bool unite(ll x, ll y) {
    x = find(x), y = find(y);
    if (x == y) return (false);
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  ll find(ll k) {
    if (data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  ll size(ll k) { return (-data[find(k)]); }

  bool same(ll x, ll y) {
    int rx = find(x);
    int ry = find(y);
    return rx == ry;
  }
  // {1:[1,2,3], 4:[4,5]}
  map<ll, vll> groups() {
    map<ll, vll> m;
    rep(i, data.size()) {
      ll root = find(i);
      m[root].emplace_back(i);
    }
    return m;
  }

  map<ll, set<ll>> group_set() {
    map<ll, set<ll>> m;
    rep(i, data.size()) {
      ll root = find(i);
      m[root].insert(i);
    }
    return m;
  }
};

mll *classes[200050];

void merge_map(mll *m1, mll *m2) {
  auto ite = (*m2).begin();
  for (; ite != end(*m2); ite++) {
    ll key = (*ite).first;
    ll val = (*ite).second;
    // cout << key << ":" << val << endl;

    (*m1)[key] += (*m2)[key];
  }
}

int main() {
  // std::cout << std::fixed << std::setprecision(10);

  ll N, Q;
  scanf("%lld %lld", &N, &Q);

  UnionFind uf(N);

  rep(s, N) {
    ll v;
    scanf("%lld", &v);

    v--;

    classes[s] = new mll();
    (*classes[s])[v] = 1;
  }

  rep(i, Q) {
    ll type, a, b;
    scanf("%lld %lld %lld", &type, &a, &b);

    a--;
    b--;

    ll group_a = uf.find(a);

    if (type == 1) {
      if (uf.same(a, b)) continue;

      ll group_b = uf.find(b);

      uf.unite(a, b);

      mll *m1 = classes[group_a];
      mll *m2 = classes[group_b];

      mll *src;
      mll *dest;

      if (m1->size() > m2->size()) {
        dest = m1;
        src = m2;
      } else {
        dest = m2;
        src = m1;
      }

      merge_map(dest, src);

      classes[group_a] = dest;
      classes[group_b] = dest;
    }

    if (type == 2) {
      //
      cout << ((*classes[group_a])[b]) << endl;
    }
  }

  ll ans = 0;

  // cout << ans << endl;
}


//Bismillahir Rahmanir Raheem
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
#define sf(x) scanf("%d",&x)
#define sfl(x) scanf("%lld",&x)
#define lli long long int
#define ll64 int64_t
#define pb push_back
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define frr(i,a) for(int i=0;i<a;i++)
#define frl(i,a) for(lli i=0;i<a;i++)
#define fr1(i,a) for(int i=1;i<=a;i++)
#define iter(x)  x.begin(),x.end()
#define Memset(a,x,n) for(int i=0;i<n;i++)a[i]=x;
#define fi first
#define si second
//std::string s=std::bitset<M>(n).to_string();  //number to binary string
//lower_bound returns an iterator pointing to the first element in the range [first,last) which has a value not less than ‘val’.
//upper_bound returns an iterator pointing to the first element in the range [first,last) which has a value greater than ‘val’.
//if mod is prime modInv(a,mod)==binExp(a,mod-2);
typedef pair<lli,lli>pll;
void solve()
{

}
int main()
{
    lli n,q;
    cin>>n>>q;
    vector<lli>a(n+1);
    a[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    lli p=0;
    vector<lli>l,r,e;
    for(int i=0;i<=n;i++)
    {
        if(i!=n and a[i+1]!=a[i]+1)
        {
            l.pb(p+1);
            p+=(a[i+1]-a[i]-1);
            r.pb(p);
            e.pb(a[i]+1);
        }
    }
    l.pb(p+1);
    r.pb(1e18+10);
    e.pb(a[n]+1);
    lli s;
//    frr(i,l.size())
//    {
//        cout<<l[i]<<" "<<r[i]<<" "<<e[i]<<endl;
//    }
    for(int i=0;i<q;i++)
    {
        cin>>s;
        lli x=lower_bound(l.begin(),l.end(),s)-l.begin();
        lli y=lower_bound(r.begin(),r.end(),s)-r.begin();
        if(x>y)
        {
            x--;
        }
        cout<<e[x]+(s-l[x])<<endl;
    }
}

