#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <ios>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>

using namespace std;

using i64 = int64_t;
using u64 = uint64_t;
using i32 = int32_t;
using pi64 = pair<i64, i64>;

constexpr i64 MAXN = 3*100*1000LL+5LL;
constexpr i64 MOD = 1000000007LL;
constexpr i64 INF64 = MOD * MOD;
#define vec vector
#define let const
#define DRi64(x) i64 x; cin >> x;
#define DRS(x) string x; cin >> x;
#define DRVi64(v, n) vec<i64> v(n); { for (i64 i = 0; i < n; ++i) { cin >> v[i]; }}

#ifdef DEBUG
#define P(x) cerr << x << "\n"
#else
#define P(x)
#endif

i64
find_(const i64 a, vec<i64>& parents)
{
    if (parents[a] != a)
    {
        parents[a] = find_(parents[a], parents);
    }
    return parents[a];
}

void
union_(const i64 a, const i64 b, vec<i64>& parents, vec<i64>& sizes,
        vec<map<i64, i64>>& class_hists)
{
    let i64 r_a = find_(a, parents);
    let i64 r_b = find_(b, parents);
    if (r_a == r_b)
    {
        return;
    }
    if (sizes[r_a] < sizes[r_b])
    {
        union_(r_b, r_a, parents, sizes, class_hists);
        return;
    }
    sizes[r_a] += sizes[r_b];
    parents[r_b] = r_a;
    // merge map of smaller vertex into that of larger vertex
    for (let auto& [cls, cnt] : class_hists[r_b])
    {
        class_hists[r_a][cls] += cnt;
    }
}

int
main()
{
    ios_base::sync_with_stdio(false);

    DRi64(N); DRi64(Q);
    DRVi64(C, N);

    // Ci \in [1, N]
    vec<i64> class_hist(N + 1, 0);
    for (let i64 c : C)
    {
        ++class_hist[c];
    }

    vec<i64> parents(N + 1);
    iota(parents.begin(), parents.end(), 0LL);
    vec<i64> sizes(N + 1, 1);
    vec<map<i64, i64>> class_hists(N + 1);
    for (i64 i = 1; i <= N; ++i)
    {
        class_hists[i][C[i - 1]] = 1;
    }

    for (; Q-->0;)
    {
        DRi64(typ);
        if (typ == 1)
        {
            DRi64(A); DRi64(B);
            union_(A, B, parents, sizes, class_hists);
        }
        else if (typ == 2)
        {
            DRi64(X); DRi64(Y);
            if (let i64 r_X = find_(X, parents); class_hists[r_X].count(Y))
            {
                cout << class_hists[r_X][Y] << "\n";
            }
            else
            {
                cout << "0\n";
            }
        }
        else
        {
            abort();
        }
    }

    return 0;
}

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr ll mod=1e9+7;

vector<int> st[200010];
vector<int> que[200010];

struct UnionFind{
	vector<int> par,num;
	UnionFind(int n):par(n),num(n,1){
		iota(par.begin(),par.end(),0);  //include<numeric>
	}
	int find(int v){
		return (par[v]==v)?v:(par[v]=find(par[v]));
	}
	void unite(int u,int v){
		u=find(u),v=find(v);
		if(u==v)return;
		if(num[u]<num[v])swap(u,v);
		if((int)que[u].size()+(int)que[v].size()<500){
			que[u].push_back(v);
			for(auto p:que[v]){
				que[u].push_back(p);
			}
		}
		else{
			vector<int> V=st[u];
			for(auto p:que[u]){
				for(int pp:st[p]){
					V.push_back(pp);
				}
			}
			que[v].push_back(v);
			for(auto p:que[v]){
				for(int pp:st[p]){
					V.push_back(pp);
				}
			}
			que[v].clear();
			que[u].clear();
			sort(V.begin(), V.end());
			st[u]=V;
		}
		num[u]+=num[v];
		par[v]=u;
	}
	bool same(int u,int v){
		return find(u) == find(v);
	}
	int size(int v){
		return num[find(v)];
	}
};

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,q; cin >> n >> q;
	vector<int> c(n);
	vector<int> cnt(n+1,0);
	vector<int> sum(n+1,0);
	for(int i=0;i<n;i++){
		cin >> c[i];
		cnt[c[i]]++;
	}
	sum=cnt;
	for(int i=0;i<n;i++){
		sum[i+1]+=sum[i];
	}
	vector<int> rem=cnt;
	for(int i=0;i<n;i++){
		int sm=sum[c[i]-1];
		rem[c[i]]--;
		c[i]=sm+rem[c[i]];
	}
	UnionFind uf(n);
	for(int i=0;i<n;i++){
		st[i].push_back(c[i]);
	}
	auto cal=[&](int x,vector<int> &v)->int{
		return v.end()-lower_bound(v.begin(), v.end(),x);
	};
	while(q--){
		int t; cin >> t;
		if(t==1){
			int a,b; cin >> a >> b;
			a--; b--;
			uf.unite(a,b);
		}
		else{
			int a,b; cin >> a >> b;
			a--;
			a=uf.find(a);
			int res=0;
			res+=cal(sum[b-1],st[a])-cal(sum[b],st[a]);
			for(auto p:que[a]){
				res+=cal(sum[b-1],st[p])-cal(sum[b],st[p]);
			}
			printf("%d\n",res);
		}
	}
}