Problem: Yash loves playing with trees and gets especially excited when they have something to do with prime numbers. On his 20th birthday he was granted with a rooted tree of n nodes to answer queries on. Hearing of prime numbers on trees, Yash gets too intoxicated with excitement and asks you to help out and answer queries on trees for him. Tree is rooted at node 1. Each node i has some value ai associated with it. Also, integer m is given.

There are queries of two types:

  1. for given node v and integer value x, increase all ai in the subtree of node v by value x
  2. for given node v, find the number of prime numbers p less than m, for which there exists a node u in the subtree of v and a non-negative integer value k, such that au = p + m·k.

Input

The first of the input contains two integers n and m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 1000) — the number of nodes in the tree and value m from the problem statement, respectively.

The second line consists of n integers ai (0 ≤ ai ≤ 109) — initial values of the nodes.

Then follow n - 1 lines that describe the tree. Each of them contains two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of nodes connected by the i-th edge.

Next line contains a single integer q (1 ≤ q ≤ 100 000) — the number of queries to proceed.

Each of the last q lines is either 1 v x or 2 v (1 ≤ v ≤ n, 0 ≤ x ≤ 109), giving the query of the first or the second type, respectively. It's guaranteed that there will be at least one query of the second type.

Output

For each of the queries of the second type print the number of suitable prime numbers.

Examples

Input

8 20
3 7 9 8 4 11 7 3
1 2
1 3
3 4
4 5
4 6
4 7
5 8
4
2 1
1 1 1
2 5
2 4


Output

3
1
1


Input

5 10
8 7 5 1 0
1 2
2 3
1 5
2 4
3
1 1 0
1 1 2
2 2


Output

2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long int N = 1e5 + 5;
const long long int M = 1e3;
const long long int mod = 1e7 + 7;
const long long int m1 = 1e9 + 7;
const long long int m2 = 1e9 + 9;
const long long int p1 = 402653189;
const long long int p2 = 1610612741;
const int LN = 32;
long long int powermodm(long long int x, long long int n, long long int M) {
  long long int result = 1;
  while (n > 0) {
    if (n % 2 == 1) result = (result * x) % M;
    x = (x * x) % M;
    n = n / 2;
  }
  return result;
}
long long int power(long long int _a, long long int _b) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a);
    _b /= 2;
    _a = (_a * _a);
  }
  return _r;
}
long long int gcd(long long int a, long long int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long int lcm(long long int a, long long int b) {
  return (max(a, b) / gcd(a, b)) * min(a, b);
}
long long int dx[4] = {-1, 1, 0, 0};
long long int dy[4] = {0, 0, 1, -1};
long long int pw[LN], fact[N], invfact[N];
void pre() {
  fact[0] = 1;
  for (int i = 0; i < LN; i++) pw[i] = power(2, i);
  for (int i = 1; i < N; i++) fact[i] = (i * fact[i - 1]) % mod;
  for (int i = 0; i < N; i++) invfact[i] = powermodm(fact[i], mod - 2, mod);
}
long long int n, m, a[N], st[N], en[N], tme[N], curr, lazy[4 * N];
vector<long long int> adj[N];
bitset<M> B[4 * N], fin, bset;
void dfs(long long int node, long long int par) {
  st[node] = ++curr;
  tme[curr] = node;
  for (auto it : adj[node]) {
    if (it == par) continue;
    dfs(it, node);
  }
  en[node] = curr;
}
void build(long long int pos, long long int left, long long int right) {
  if (left == right) {
    B[pos].set(a[tme[left]] % m);
    return;
  }
  long long int mid = (left + right) >> 1;
  build(2 * pos + 1, left, mid);
  build(2 * pos + 2, mid + 1, right);
  B[pos] = B[2 * pos + 1] | B[2 * pos + 2];
}
void apply(bitset<M> &tmp, long long int shift) {
  tmp = (tmp << shift) | (tmp >> (m - shift));
}
void update(long long int pos, long long int left, long long int right,
            long long int start, long long int end, long long int val) {
  if (lazy[pos] != 0) {
    apply(B[pos], lazy[pos]);
    if (left != right) {
      lazy[2 * pos + 1] = (lazy[2 * pos + 1] + lazy[pos]) % m;
      lazy[2 * pos + 2] = (lazy[2 * pos + 2] + lazy[pos]) % m;
    }
    lazy[pos] = 0;
  }
  if (left > end || right < start)
    return;
  else if (start <= left && right <= end) {
    apply(B[pos], val);
    if (left != right) {
      lazy[2 * pos + 1] = (lazy[2 * pos + 1] + val) % m;
      lazy[2 * pos + 2] = (lazy[2 * pos + 2] + val) % m;
    }
    return;
  }
  long long int mid = (left + right) >> 1;
  update(2 * pos + 1, left, mid, start, end, val);
  update(2 * pos + 2, mid + 1, right, start, end, val);
  B[pos] = B[2 * pos + 1] | B[2 * pos + 2];
}
void query(long long int pos, long long int left, long long int right,
           long long int start, long long int end) {
  if (lazy[pos] != 0) {
    apply(B[pos], lazy[pos]);
    if (left != right) {
      lazy[2 * pos + 1] = (lazy[2 * pos + 1] + lazy[pos]) % m;
      lazy[2 * pos + 2] = (lazy[2 * pos + 2] + lazy[pos]) % m;
    }
    lazy[pos] = 0;
  }
  if (left > end || right < start)
    return;
  else if (start <= left && right <= end) {
    bset |= B[pos];
    return;
  }
  long long int mid = (left + right) >> 1;
  query(2 * pos + 1, left, mid, start, end);
  query(2 * pos + 2, mid + 1, right, start, end);
}
bool pri[1005];
vector<long long int> prm;
void fun() {
  for (long long int i = 2; i < m; i++) pri[i] = true;
  for (long long int i = 2; i < m; i++) {
    if (pri[i]) {
      prm.push_back(i);
      for (long long int j = 2 * i; j < m; j += i) pri[j] = false;
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long int i, j;
  fin.set();
  cin >> n >> m;
  fun();
  for (i = 1; i <= n; i++) cin >> a[i];
  for (i = 1; i < n; i++) {
    long long int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1, 0);
  build(0, 1, n);
  long long int q;
  cin >> q;
  while (q--) {
    long long int x;
    cin >> x;
    if (x == 1) {
      long long int node, val;
      cin >> node >> val;
      update(0, 1, n, st[node], en[node], val % m);
    } else {
      bset.reset();
      long long int node;
      cin >> node;
      query(0, 1, n, st[node], en[node]);
      long long int ans = 0;
      for (i = 0; i < prm.size(); i++) {
        if (bset[prm[i]]) ans++;
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}