#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define all(x) begin(x), end(x)
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair <int,int> P;
const int INF=1e9;
const int MAX_N=200005;

int par[MAX_N];
int rnk[MAX_N];
map<int,int> cnt[MAX_N];
int c[MAX_N];

void init(int n) {
  for (int i=0; i<n; i++) {
    par[i]=i;
    rnk[i]=0;
    cnt[i][c[i]]=1;
  }
}
int find(int x) {
  if (par[x]==x) {
    return x;
  }
  else {
    return par[x]=find(par[x]);
  }
}

void unite(int x,int y) {
  x=find(x);
  y=find(y);
  if (x==y) return;
  if (rnk[x]<rnk[y]) {
    par[x]=y;
    for (auto p:cnt[x]) {
      cnt[y][p.first]+=p.second;
    }
  }
  else {
    par[y]=x;
    if (rnk[x]==rnk[y]) rnk[x]++;
    for (auto p:cnt[y]) {
      cnt[x][p.first]+=p.second;
    }
  }
}

bool same(int x, int y) {
  return find(x)==find(y);
}

int main(){
  int n,q;
  cin>>n>>q;
  rep(i,n) cin>>c[i];
  init(n);

  while(q--){
    int t,a,b;
    cin>>t>>a>>b;

    if(t==1){
      a--; b--;
      unite(a,b);
    }
    else{
      a--;
      int x=find(a);
      cout<<cnt[x][b]<<endl;
    }
  }
  return 0;
}


#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2E5;
int par[MAXN];
int sz[MAXN];
int rep[MAXN];
pair<long long, int> a[MAXN];
pair<long long, int> f[MAXN];
long long ans[MAXN];

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

void mge(int x, int y)
{
    x = getRoot(x);
    y = getRoot(y);
    if (x == y)
        return;
    int r = rep[y];
    if (sz[x] > sz[y])
        swap(x, y);
    par[x] = y;
    sz[y] += sz[x];
    rep[y] = r;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> f[i].first >> f[i].second;
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        cin >> a[i].first;
        a[i].second = i;
        par[i] = i;
        sz[i] = 1;
        rep[i] = i;
    }
    sort(a, a + q);
    int left = 0;
    int right = q - 1;
    long long delta = 0;
    for (int i = 0; i < n; i++)
    {
        if (f[i].second == 1)
        {
            delta += f[i].first;
        }
        else if (f[i].second == 2)
        {
            f[i].first -= delta;
            if (a[left].first < f[i].first)
            {
                while (left + 1 <= right && a[left + 1].first < f[i].first)
                {
                    mge(left, left + 1);
                    left++;
                }
                a[left].first = f[i].first;
            }
        }
        else if (f[i].second == 3)
        {
            f[i].first -= delta;
            if (a[right].first > f[i].first)
            {
                while (right - 1 >= left && a[right - 1].first > f[i].first)
                {
                    mge(right, right - 1);
                    right--;
                }
                a[right].first = f[i].first;
            }
        }
    }
    //cout << "left " << left << endl;
    //cout << "right " << right << endl;
    for (int i = 0; i < q; i++)
    {
        ans[a[i].second] = a[rep[getRoot(i)]].first + delta;
        //cout << "setting " << a[i].second << endl;
    }
    for (int i = 0; i < q; i++)
        cout << ans[i] << "\n";
    return 0;
}
