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>
const long long N = 5e5 + 9, mod = 998244353;
typedef long long aN[N];
long long cnt = 0, tot = 0;
long long readll() {
  long long x = 0, w = 1;
  int c = getchar();
  for (; c < '0' || c > '9'; c - '-' || (w = -w), c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = x * 10 + (c ^ 48), c = getchar())
    ;
  return x * w;
}
int readchar(int l = '0', int r = 'z') {
  int c = getchar();
  for (; c < l || c > r; c = getchar())
    ;
  return c;
}
aN next, to, head, dfn, size, son, top, tag, fa;
long long pow(long long a, long long b, long long p) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % p;
    a = a * a % p, b >>= 1;
  }
  return res;
}
void add(long long u, long long v) {
  next[++cnt] = head[u], to[head[u] = cnt] = v;
}
void dfs(long long u, long long fa) {
  dfn[u] = ++tot, size[u] = 1, son[u] = 0;
  for (register long long i = head[u], v; v = to[i], i; i = next[i])
    if (v ^ fa)
      dfs(v, u), size[u] += size[v], (size[v] > size[son[u]]) && (son[u] = v);
}
void dfs(long long u, long long fa, long long t) {
  ::fa[u] = fa, top[u] = t ? top[fa] : u;
  if (son[u]) dfs(son[u], u, 1);
  for (register long long i = head[u], v; v = to[i], i; i = next[i])
    if (v ^ fa && v ^ son[u]) dfs(v, u, 0);
}
struct bit {
  aN f;
  long long tag, n;
  void set(long long n_) {
    memset(f, tag = 0, sizeof(long long) * ((n = n_) + 1));
  }
  void update(long long u, long long c) {
    for (; u <= n; f[u] += c, u += u & -u)
      ;
  }
  void update(long long l, long long r, long long c) {
    update(l, c), update(r + 1, -c);
  }
  long long query(long long u) {
    long long res = 0;
    while (u) res += f[u], u &= ~-u;
    return tag + res;
  }
} t;
void update_tree(long long u, long long c, long long n) {
  tag[u] = (tag[u] + c) % mod;
  if (son[u])
    t.update(dfn[son[u]], dfn[son[u]] + size[son[u]] - 1,
             (n - size[son[u]]) * c % mod);
  if (u != 1)
    t.tag = (t.tag + size[u] * c) % mod,
    t.update(dfn[u], dfn[u] + size[u] - 1, (mod - size[u]) * c % mod);
}
long long query_tree(long long u, long long n) {
  long long res = (tag[u] * n + t.query(dfn[u])) % mod;
  u = top[u];
  while (u) res = (res + tag[fa[u]] * (n - size[u])) % mod, u = top[fa[u]];
  return res;
}
int main() {
  long long n = readll(), m = readll(), u, v, ni = pow(n, mod - 2, mod);
  for (register long long i = 2; i <= n; i++)
    u = readll(), v = readll(), add(u, v), add(v, u);
  dfs(1, 0), dfs(1, 0, 0);
  t.set(n);
  for (register long long i = 1; i <= m; i++)
    if (readll() == 1)
      u = readll(), update_tree(u, readll(), n);
    else
      printf("%lld\n", query_tree(readll(), n) * ni % mod);
  return 0;
}