#include<stdio.h>
#include<stdlib.h>

int search(long *arr, int left,int right, long num){
  int mid = (left+right)/2;
  if(left == right){
    return left;
  }
  if(arr[mid] == num){
    return mid;
  }else if(num < arr[mid]){
    return search(arr,left,mid,num);
  }else{
    return search(arr,mid+1,right,num);
  }
}

int main(){
  int n,q,i,j;
  long *a,k,*sum;

  scanf("%d %d",&n,&q);
  a = (long*)malloc(sizeof(long)*n);
  sum = (long*)malloc(sizeof(long)*n);
  for(i=0;i<n;i++){
    scanf("%ld",a+i);
    sum[i] = a[i]-i-1;
  }
  for(i=0;i<q;i++){
    scanf("%ld",&k);
    j = search(sum,0,n-1,k);
    if(j == 0){
      printf("%ld\n",k);
    }else if(j == n-1 && sum[n-1] < k){
      printf("%ld\n",a[n-1]+k-sum[n-1]);
    }else{
      while(j > 0 && sum[j] == sum[j-1]) j--;
      printf("%ld\n",a[j-1]+k-sum[j-1]);
    }
  }
  return 0;
}

#include <set>
#include <iostream>

using namespace std;

#define int long long

const int N = 2e5 + 10;

int par[N], c[N];
set<pair<int, int>> s[N];

void make_set(int x) {
  par[x] = x;
  s[x].insert({c[x], 1});
}

int find_set(int x) {
  if (x == par[x]) {
    return x;
  }
  return par[x] = find_set(par[x]);
}

void union_sets(int x, int y) {
  x = find_set(x);
  y = find_set(y);
  if (x != y) {
    if (s[x].size() > s[y].size()) {
      swap(x, y);
    }
    par[x] = y;
    for (auto z : s[x]) {
      auto it = s[y].lower_bound({z.first, -1});
      int cur = z.second;
      if (!(it == s[y].end() || it->first != z.first)) {
        cur += it->second;
        s[y].erase(it);
      }
      s[y].insert({z.first, cur});
    }
  }
}

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);    
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> c[i];
    make_set(i);
  }
  while (q--) {
    int x, y, z;
    cin >> x >> y >> z;
    if (x - 1) {
      int w = find_set(y);
      auto it = s[w].lower_bound({z, -1});
      if (it == s[w].end() || it->first != z) {
        cout << "0\n";
      } else {
        cout << it->second << '\n';
      }
    } else {
      union_sets(y, z);
    }
  }
  return 0;
}