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 = 150005, P = 998244353, S = 400;
int n, q, t, a[N], d[N], L[N], R[N], dfn[N], sz[N], fa[N], dfncnt;
int b[N], pos[N], len, s[N], sum, son[S][N];
vector<int> g[N];
int c[N], tag[N];
void inline add(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
void inline ins(int x, int y) {
  if (x > n) return;
  add(tag[pos[x]], y);
  add(c[x], y);
}
int inline ask(int x) {
  int p = pos[x];
  int res = 0;
  for (int i = 1; i < p; i++) add(res, tag[i]);
  for (int i = L[p]; i <= x; i++) add(res, c[i]);
  return res;
}
void dfs(int u) {
  sz[u] = 1;
  dfn[u] = ++dfncnt;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (v == fa[u]) continue;
    fa[v] = u;
    dfs(v);
    sz[u] += sz[v];
  }
}
int inline isA(int x, int y) {
  return dfn[x] <= dfn[y] && dfn[y] <= dfn[x] + sz[x] - 1;
}
int inline power(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % P;
    a = 1ll * a * a % P;
    b >>= 1;
  }
  return res;
}
int inline inv(int x) { return power(x, P - 2); }
void inline upd(int l, int r, int k) {
  ins(l, k);
  ins(r + 1, P - k);
}
int main() {
  scanf("%d%d", &n, &q);
  t = sqrt(n);
  for (int i = 1; i <= n; i++) {
    pos[i] = (i - 1) / t + 1;
    if (!L[pos[i]]) L[pos[i]] = i;
  }
  for (int i = 1, u, v; i < n; i++)
    scanf("%d%d", &u, &v), g[u].push_back(v), g[v].push_back(u), d[v]++, d[u]++;
  dfs(1);
  for (int i = 1; i <= n; i++)
    if (d[i] > t) b[++len] = i;
  for (int i = 1; i <= len; i++) {
    int u = b[i];
    for (int j = 0; j < g[u].size(); j++) {
      int v = g[u][j];
      if (v == fa[u]) continue;
      for (int k = dfn[v]; k < dfn[v] + sz[v]; k++) son[i][k] = v;
    }
  }
  int I = inv(n);
  while (q--) {
    int op, v;
    scanf("%d%d", &op, &v);
    if (op == 1) {
      int w;
      scanf("%d", &w);
      if (d[v] > t) {
        add(s[v], w);
      } else {
        int bb = 0;
        add(sum, 1ll * w * I % P);
        add(bb, 1ll * w * I % P);
        for (int i = 0; i < g[v].size(); i++) {
          int k = g[v][i];
          if (k == fa[v]) {
            upd(dfn[v], dfn[v] + sz[v] - 1, 1ll * I * (n - sz[v]) % P * w % P);
            add(bb, 1ll * I * (n - sz[v]) % P * w % P);
          } else {
            int val = 1ll * I * sz[k] % P * w % P;
            add(sum, val);
            upd(dfn[k], dfn[k] + sz[k] - 1, P - val);
            add(bb, val);
          }
        }
      }
    } else {
      int res = ask(dfn[v]);
      add(res, sum);
      for (int i = 1; i <= len; i++) {
        int u = b[i];
        if (isA(u, v)) {
          int t = son[i][dfn[v]];
          add(res, 1ll * I * (n - sz[t]) % P * s[u] % P);
        } else {
          add(res, 1ll * I * sz[u] % P * s[u] % P);
        }
      }
      printf("%d\n", res);
    }
  }
  return 0;
}