Problem: Hanh is a famous biologist. He loves growing trees and doing experiments on his own garden.

One day, he got a tree consisting of n vertices. Vertices are numbered from 1 to n. A tree with n vertices is an undirected connected graph with n-1 edges. Initially, Hanh sets the value of every vertex to 0.

Now, Hanh performs q operations, each is either of the following types: 

  * Type 1: Hanh selects a vertex v and an integer d. Then he chooses some vertex r uniformly at random, lists all vertices u such that the path from r to u passes through v. Hanh then increases the value of all such vertices u by d. 
  * Type 2: Hanh selects a vertex v and calculates the expected value of v. 



Since Hanh is good at biology but not math, he needs your help on these operations.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 150 000) — the number of vertices on Hanh's tree and the number of operations he performs.

Each of the next n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n), denoting that there is an edge connecting two vertices u and v. It is guaranteed that these n - 1 edges form a tree.

Each of the last q lines describes an operation in either formats: 

  * 1 v d (1 ≤ v ≤ n, 0 ≤ d ≤ 10^7), representing a first-type operation. 
  * 2 v (1 ≤ v ≤ n), representing a second-type operation. 



It is guaranteed that there is at least one query of the second type.

Output

For each operation of the second type, write the expected value on a single line. 

Let M = 998244353, it can be shown that the expected value can be expressed as an irreducible fraction p/q, where p and q are integers and q not ≡ 0 \pmod{M}. Output the integer equal to p ⋅ q^{-1} mod M. In other words, output such an integer x that 0 ≤ x < M and x ⋅ q ≡ p \pmod{M}.

Example

Input


5 12
1 2
1 3
2 4
2 5
1 1 1
2 1
2 2
2 3
2 4
2 5
1 2 2
2 1
2 2
2 3
2 4
2 5


Output


1
199648871
399297742
199648871
199648871
598946614
199648873
2
2
2

Note

The image below shows the tree in the example:

<image>

For the first query, where v = 1 and d = 1: 

  * If r = 1, the values of all vertices get increased. 
  * If r = 2, the values of vertices 1 and 3 get increased. 
  * If r = 3, the values of vertices 1, 2, 4 and 5 get increased. 
  * If r = 4, the values of vertices 1 and 3 get increased. 
  * If r = 5, the values of vertices 1 and 3 get increased. 



Hence, the expected values of all vertices after this query are (1, 0.4, 0.8, 0.4, 0.4).

For the second query, where v = 2 and d = 2: 

  * If r = 1, the values of vertices 2, 4 and 5 get increased. 
  * If r = 2, the values of all vertices get increased. 
  * If r = 3, the values of vertices 2, 4 and 5 get increased. 
  * If r = 4, the values of vertices 1, 2, 3 and 5 get increased. 
  * If r = 5, the values of vertices 1, 2, 3 and 4 get increased. 



Hence, the expected values of all vertices after this query are (2.2, 2.4, 2, 2, 2).

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 212345;
vector<int> g[N];
long long ent[N], sai[N], sz[N], dfscnt;
long long acum[N], pai[N];
int mod = 998244353;
long long nxt[N];
long long fpow(long long b, long long e) {
  if (!e) return 1;
  long long r = fpow(b, e / 2);
  r = (r * r) % mod;
  return e % 2 ? (r * b) % mod : r;
}
long long inv(long long b) { return fpow(b, mod - 2); }
struct segtree {
  vector<int> seg, lazy;
  int n, k, a, b;
  segtree() {}
  segtree(int n) : n(n) {
    seg.resize(4 * n + 10, 0);
    lazy.resize(4 * n + 10, 0);
  }
  void prop(int r, int i, int j) {
    if (!lazy[r]) return;
    seg[r] += lazy[r] * (j - i + 1LL) % mod;
    seg[r] %= mod;
    if (i != j) {
      lazy[r * 2] = (lazy[r * 2] + lazy[r]) % mod;
      lazy[r * 2 + 1] = (lazy[r * 2 + 1] + lazy[r]) % mod;
    }
    lazy[r] = 0;
  }
  int query(int r, int i, int j) {
    prop(r, i, j);
    if (i > b or j < a) return 0;
    if (i >= a and j <= b) {
      lazy[r] += k;
      prop(r, i, j);
      return seg[r];
    }
    int mid = (i + j) / 2;
    int le = query(r * 2, i, mid);
    int ri = query(r * 2 + 1, mid + 1, j);
    seg[r] = (seg[r * 2] + seg[r * 2 + 1]) % mod;
    return (le + ri) % mod;
  }
  int query(int l, int r) {
    if (l > r) return 0;
    a = l;
    b = r;
    k = 0;
    return query(1, 0, n - 1);
  }
  void update(int l, int r, int z) {
    a = l;
    b = r;
    k = z;
    query(1, 0, n - 1);
  }
} st[N];
struct segtree2 {
  vector<int> seg, lazy, aux, ac;
  int n, k, a, b;
  segtree2() {}
  segtree2(int n) : n(n) {
    seg.resize(4 * n + 10, 0);
    lazy.resize(4 * n + 10, 0);
    ac.resize(4 * n + 10, 0);
    aux.resize(4 * n + 10, 0);
  }
  void build_ac() {
    for (int i = 0; i < n; i++) ac[i + 1] = (ac[i] + aux[i]) % mod;
  }
  void prop(int r, int i, int j) {
    if (!lazy[r]) return;
    seg[r] += lazy[r] * 1LL * (ac[j + 1] - ac[i]) % mod;
    seg[r] %= mod;
    if (i != j) {
      lazy[r * 2] = (lazy[r * 2] + lazy[r]) % mod;
      lazy[r * 2 + 1] = (lazy[r * 2 + 1] + lazy[r]) % mod;
    }
    lazy[r] = 0;
  }
  int query(int r, int i, int j) {
    prop(r, i, j);
    if (i > b or j < a) return 0;
    if (i >= a and j <= b) {
      lazy[r] += k;
      prop(r, i, j);
      return seg[r];
    }
    int mid = (i + j) / 2;
    int le = query(r * 2, i, mid);
    int ri = query(r * 2 + 1, mid + 1, j);
    seg[r] = (seg[r * 2] + seg[r * 2 + 1]) % mod;
    return (le + ri) % mod;
  }
  int query(int l, int r) {
    a = l;
    b = r;
    k = 0;
    return query(1, 0, n - 1);
  }
  void update(int l, int r, int z) {
    a = l;
    b = r;
    k = z;
    query(1, 0, n - 1);
  }
} st2[N];
void dfs(int u, int pu) {
  ent[u] = dfscnt++;
  sz[u] = 1;
  for (auto v : g[u]) {
    if (v == pu) continue;
    dfs(v, u);
    pai[v] = u;
    sz[u] += sz[v];
  }
  sai[u] = dfscnt - 1;
}
vector<int> chains[N];
int cnt_chain = 1, pos_chain[N], id_chain[N], head[N];
void build_hld(int u, int pu, int chain) {
  id_chain[u] = chain;
  chains[chain].push_back(u);
  pos_chain[u] = chains[chain].size();
  pos_chain[u]--;
  int maior = 0;
  for (auto v : g[u])
    if (v != pu and sz[v] > sz[maior]) maior = v;
  for (auto v : g[u]) {
    if (v == pu) continue;
    if (v == maior) {
      build_hld(v, u, chain);
    } else {
      cnt_chain++;
      build_hld(v, u, cnt_chain);
    }
  }
}
int main(void) {
  int n, q;
  scanf("%d %d", &n, &q);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 0);
  st[0] = segtree(n);
  build_hld(1, 0, 1);
  for (int i = 1; i <= cnt_chain; i++) {
    st[i] = segtree(chains[i].size() + 5);
    head[i] = chains[i][0];
    for (int j = 1; j < chains[i].size(); j++) {
      int vv = chains[i][j - 1];
      nxt[vv] = n - sz[chains[i][j]];
    }
  }
  while (q--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int v, d;
      scanf("%d %d", &v, &d);
      {
        int l = 0;
        int r = ent[v] - 1;
        if (l <= r) {
          st[0].update(l, r, sz[v] * d % mod);
        }
      }
      {
        int l = sai[v] + 1;
        int r = n - 1;
        if (l <= r) {
          st[0].update(l, r, sz[v] * d % mod);
        }
      }
      acum[v] += d;
      acum[v] %= mod;
      st[0].update(ent[v], ent[v], n * 1LL * d % mod);
      while (v) {
        int id = id_chain[v];
        int pos = pos_chain[v];
        st[id].update(pos, pos, nxt[v] * d % mod);
        break;
        v = pai[head[id]];
      }
    } else {
      int v;
      scanf("%d", &v);
      long long ans = st[0].query(ent[v], ent[v]);
      while (v) {
        int id = id_chain[v];
        int pos = pos_chain[v];
        ans += st[id].query(0, pos - 1);
        ans %= mod;
        v = head[id];
        if (v != 1) {
          int par = pai[v];
          ans += (n - sz[v]) * acum[par] % mod;
          ans %= mod;
        }
        v = pai[v];
      }
      cout << ans * inv(n) % mod << endl;
    }
  }
  return 0;
}