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;
inline int input() {
  char c = getchar();
  int o;
  while (c > 57 || c < 48) c = getchar();
  for (o = 0; c > 47 && c < 58; c = getchar()) o = (o << 1) + (o << 3) + c - 48;
  return o;
}
const int MAXN = 15e4 + 5, MOD = 998244353;
vector<int> Edge[MAXN];
int inv, n, q, visit, fa[MAXN], son[MAXN], siz[MAXN], Anc[MAXN], vis[MAXN];
long long T[MAXN], A[MAXN];
void INV() {
  inv = 1;
  long long a = n, t = MOD - 2;
  while (t) {
    if (t & 1) inv = inv * a % MOD;
    a = a * a % MOD;
    t >>= 1;
  }
}
void Add(int p, long long a) {
  for (; p <= n; p += (p & (-p))) T[p] = (T[p] + a) % MOD;
}
long long Query(int p) {
  long long ans = 0;
  for (; p; p -= (p & (-p))) ans = (ans + T[p]) % MOD;
  return ans;
}
void Modify(int p, long long a) {
  Add(vis[p], a);
  Add(vis[p] + siz[p], MOD - a);
}
void Dfs(int s) {
  siz[s] = 1;
  for (auto e : Edge[s])
    if (e != fa[s]) {
      fa[e] = s;
      Dfs(e);
      if (siz[e] > siz[son[s]]) son[s] = e;
      siz[s] += siz[e];
    }
}
void Link(int s, int anc) {
  Anc[s] = anc;
  vis[s] = ++visit;
  if (son[s]) Link(son[s], anc);
  for (auto e : Edge[s])
    if ((e != son[s]) && (e != fa[s])) Link(e, e);
}
void Ques(int p) {
  long long ans = (Query(vis[p]) + A[p] * n) % MOD;
  for (p = Anc[p]; fa[p]; p = Anc[fa[p]])
    ans = (ans + A[fa[p]] * (n - siz[p])) % MOD;
  printf("%lld\n", ans * inv % MOD);
}
int main() {
  n = input();
  q = input();
  INV();
  int s, e;
  for (int i = 2; i <= n; i++) {
    s = input();
    e = input();
    Edge[s].emplace_back(e);
    Edge[e].emplace_back(s);
  }
  Dfs(1);
  Link(1, 1);
  int op, p;
  long long a;
  for (int i = 1; i <= q; i++) {
    op = input();
    if (op == 1) {
      p = input();
      a = input();
      Add(1, a * siz[p] % MOD);
      A[p] = (A[p] + a) % MOD;
      Modify(p, MOD - (a * siz[p]) % MOD);
      if (son[p]) Modify(son[p], a * (n - siz[son[p]]) % MOD);
    } else
      Ques(input());
  }
  return 0;
}