#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define rep(i,n) repi(i,0,n)
#define repi(i,a,n) for(ll i=a;i<(ll)n;++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define Show(val) cout<<(val)<<" "
#define Showln(val) cout<<(val)<<endl

using namespace std;
using ll = long long;
using P = pair<ll, ll>;
// using P = pair<int, int>;
void YN(bool a) { cout << (a ? "Yes" : "No"); }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

class UnionFind{
public:
  vector<int> p;		// 親
  vector<int> rank;	// サイズ・各集合の根のみ有効
  UnionFind(int n){
    p.resize(n, -1);
    rank.resize(n, 1);
  }
  int root(int x){
    if(p[x] == -1) return x;
    else return p[x] = root(p[x]); // 深さを 1 にしている
  }
  void unite(int x, int y){
    x = root(x); y = root(y);
    if(x == y)return;
    if(rank[x] > rank[y]) swap(x, y); // rankの小さいものを下につける
    // -> x <= y
    rank[y] += rank[x];
    p[x] = y;
  }
  // グループの数
  ll root_num() {
    ll num = 0;
    for(ll x : p) if (x < 0) num++;
    return num;
  }
  // グループごとに頂点をまとめる: O(N log N)
  map<int, vector<int>> groups(){
    map<int, vector<int>> ret;
    rep(i, p.size()) ret[root(i)].emplace_back(i);
    return ret;
  }
  //xが属すグループのサイズ
  int size(int x){ return rank[root(x)]; }
  bool same(int x, int y){ return (root(x) == root(y)); }
};

void solve()
{
  ll n, q, t, q1, q2;
  cin >> n >> q;

  vector<ll> cls(n);
  vector< map<ll, ll> > score(n, map<ll, ll>());

  rep(i, n) cin >> cls[i];
  rep(i, n) score[i][--cls[i]] = 1;

  UnionFind uf(n);
  rep(qi, q)
  {
    cin >> t >> q1 >> q2;
    q1--; q2--;
    if (t == 1)
    {
      if (uf.same(q1, q2)) continue;
      if (uf.size(q1) > uf.size(q2)) swap(q1, q2);

      // q1をq2にくっつける
      ll root1 = uf.root(q1);
      ll root2 = uf.root(q2);
      for(const auto& mp : score[root1])
      {
        score[root2][mp.first] += mp.second;
      }

      uf.unite(q1, q2);
    }
    else if (t == 2)
    {
      cout << score[uf.root(q1)][q2] << endl;
    }
  }  
}

int main()
{
  fastio;
  solve();

  return 0;
}
#include<bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define ll long long
#define maxheap priority_queue<int>
#define minheap priority_queue<int,vector<int>,greater<int>>
#define all(v) (v).begin(),(v).end()
const  double pi = acos(-1.0);
const  double eps = 1e-12;
using namespace std;

const int N = 20;
const ll INF = 1e18;
int n, m;
ll pref[N][N];
ll dp[(1 << N)][2];
bool ok(int mask, int idPref){
    int kol = 0;
    for (int i = 0; i < n; i++){
        if (mask & (1 << i)){
            kol++;
        }
        if (pref[idPref][i + 1] < kol){
            return false;
        }
    }       
    return true;
}
void solve(){ 
    cin >> n >> m;

    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            pref[i][j] = INF;
        }
    }
    
    for (int i = 1; i <= m; i++){
        int x, y, z;
        cin >> x >> y >> z;
        for (int j = 1; j <= x; j++){
            pref[j][y] = min((ll)z, pref[j][y]);
        }
    }
    dp[0][0] = 1;
    int now = 1;
    for (int pos = 0; pos < n; pos++){
        now = (now ^ 1);
        int nxt = (now ^ 1);
        
        for (int mask = 0; mask < (1 << n); mask++){
            dp[mask][nxt] = 0;
        }
        for (int mask = 0; mask < (1 << n); mask++){
        
            if (dp[mask][now] == 0){
                continue;
            }
            assert(__builtin_popcount(mask) == pos);
            for (int put = 0; put < n; put++){
                if (mask & (1 << put)){
                    continue;
                }
                int newMask = (mask | (1 << put));
                if (ok(newMask, pos + 1)){
                    dp[newMask][nxt] += dp[mask][now];
                    //cout << pos + 1 << " " << put + 1 << " " << mask << " " << newMask << " " << dp[mask][now] << " " << dp[newMask][nxt] << endl;
                }
            }
        }
        
            if (pos == n - 1){
                cout << dp[(1 << n) - 1][nxt] << endl;
                return;
            }
    }
} 


int main(){
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(6);
    //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout);
    //freopen("exercise.in","r",stdin); freopen("exercise.out", "w", stdout);
    int step;
    step = 1;
    //cin >> step;
    for (int i = 1; i <= step; i++){
        solve(); 
    }
}