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;
template <class T, class U>
void ckmin(T &a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
void ckmax(T &a, U b) {
  if (a < b) a = b;
}
long long expo(long long a, long long e) {
  if (e == 0) return 1;
  long long res = expo(a * a % 998244353, e >> 1);
  if (e & 1) {
    res *= a;
    res %= 998244353;
  }
  return res;
}
int N, Q, T;
long long iN;
vector<int> edge[500013];
int parent[500013], st[500013], ft[500013], depth[500013], subtree[500013],
    ancestor[20][500013];
long long upd[500013], dp[500013];
long long stor[500013];
vector<pair<long long, long long> > upds;
vector<int> ord;
void dfs(int u, int p) {
  st[u] = ft[u] = T;
  subtree[u] = 1;
  T++;
  for (int v : edge[u]) {
    if (v == p) continue;
    parent[v] = u;
    depth[v] = depth[u] + 1;
    dfs(v, u);
    ft[u] = ft[v];
    subtree[u] += subtree[v];
  }
  ord.push_back(u);
}
int kth(int u, int k) {
  for (auto i = (18) - 1; i >= (0); i--) {
    if (k & (1 << i)) {
      u = ancestor[i][u];
    }
  }
  return u;
}
bool insubt(int u, int v) {
  if (u == N) return true;
  return (st[u] <= st[v] && st[v] <= ft[u]);
}
long long get(long long u, long long v) {
  if (u == v) return 0;
  if (insubt(u, v)) {
    int w = kth(v, depth[v] - depth[u] - 1);
    return subtree[w];
  }
  return N - subtree[u];
}
void rebuild() {
  for (auto p : upds) {
    upd[p.first] += p.second;
  }
  for (auto i = (0); i < (N); i++) {
    if (upd[i] == 0) continue;
    upd[i] %= 998244353;
    stor[0] += subtree[i] * upd[i];
    stor[0] %= 998244353;
    stor[i] += (N - subtree[i]) * upd[i];
    stor[i] %= 998244353;
    for (int v : edge[i]) {
      if (v == parent[i]) continue;
      stor[v] -= subtree[v] * upd[i];
      stor[v] %= 998244353;
    }
  }
  for (auto i = (N)-1; i >= (0); i--) {
    int u = ord[i];
    for (int v : edge[u]) {
      if (v == parent[u]) continue;
      stor[v] += stor[u];
      if (stor[v] >= 998244353) stor[v] -= 998244353;
    }
  }
  for (auto i = (0); i < (N); i++) {
    dp[i] += stor[i];
    dp[i] %= 998244353;
    if (dp[i] < 0) dp[i] += 998244353;
    upd[i] = 0;
    stor[i] = 0;
  }
  upds.clear();
  return;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(12);
  cerr << fixed << setprecision(4);
  cin >> N >> Q;
  for (auto i = (0); i < (N - 1); i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  iN = expo(N, 998244353 - 2);
  dfs(0, N);
  for (auto i = (0); i < (20); i++) {
    ancestor[i][N] = N;
  }
  for (auto i = (0); i < (N); i++) {
    ancestor[0][i] = parent[i];
  }
  for (auto i = (1); i < (20); i++) {
    for (auto j = (0); j < (N); j++) {
      ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
    }
  }
  for (auto i = (0); i < (Q); i++) {
    int qid, u;
    cin >> qid >> u;
    u--;
    if (i % 241 == 0) {
      rebuild();
    }
    if (qid == 2) {
      long long ans = dp[u];
      for (pair<long long, long long> p : upds) {
        ans += (N - get(p.first, u)) * p.second;
        ans %= 998244353;
      }
      cout << ans << '\n';
    }
    if (qid == 1) {
      long long v;
      cin >> v;
      v *= iN;
      v %= 998244353;
      upds.push_back({u, v});
    }
  }
  return 0;
}