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;
vector<int> adjList[150000], adjList2[150000];
int parent[150000], size[150000], disc[150000], fin[150000], num = 0;
int doDFS(int u, int p) {
  int i;
  parent[u] = p, size[u] = 1;
  disc[u] = num++;
  for (i = 0; i < adjList[u].size(); i++) {
    int v = adjList[u][i];
    if (v != p) size[u] += doDFS(v, u), adjList2[u].push_back(v);
  }
  fin[u] = num;
  return size[u];
}
int bit[150001], all = 0;
int update(int i, int num, int n) {
  if (i == 0) {
    all += num;
    if (all >= 998244353) all -= 998244353;
    return 0;
  }
  for (i++; i <= n; i += i & (-i)) {
    bit[i] += num;
    if (bit[i] >= 998244353) bit[i] -= 998244353;
  }
  return 0;
}
int query(int i) {
  int sum = all;
  for (i++; i > 0; i -= i & (-i)) {
    sum += bit[i];
    if (sum >= 998244353) sum -= 998244353;
  }
  return sum;
}
int inv(long long int n) {
  int e = 998244353 - 2;
  long long int r = 1;
  while (e > 0) {
    if (e & 1) r *= n, r %= 998244353;
    e >>= 1;
    n *= n, n %= 998244353;
  }
  return r;
}
vector<int> big;
int bigSum[150000];
int main() {
  int i, j;
  int n, q;
  int t, u, v, d;
  scanf("%d %d", &n, &q);
  for (i = 0; i < n - 1; i++) {
    scanf("%d %d", &u, &v);
    u--, v--;
    adjList[u].push_back(v);
    adjList[v].push_back(u);
  }
  int B = sqrt(n);
  doDFS(0, -1);
  for (i = 0; i < n; i++) {
    if (adjList[i].size() > B) big.push_back(i);
  }
  int invn = inv(n);
  for (i = 0; i < q; i++) {
    scanf("%d", &t);
    if (t == 1) {
      scanf("%d %d", &u, &d), u--;
      if (adjList[u].size() > B)
        bigSum[u] += d, bigSum[u] %= 998244353;
      else {
        update(0, d, n);
        for (j = 0; j < adjList[u].size(); j++) {
          int v = adjList[u][j];
          if (v != parent[u]) {
            int x = ((long long int)size[v] * d) % 998244353;
            update(0, x, n), update(disc[v], 998244353 - x, n),
                update(fin[v], x, n);
          } else {
            int x = ((long long int)(n - size[u]) * d) % 998244353;
            update(disc[u], x, n), update(fin[u], 998244353 - x, n);
          }
        }
      }
    } else {
      scanf("%d", &u), u--;
      int ans = query(disc[u]);
      for (j = 0; j < big.size(); j++) {
        v = big[j];
        if (u == v)
          ans += ((long long int)bigSum[v] * n) % 998244353;
        else if ((disc[u] >= disc[v]) && (disc[u] < fin[v])) {
          int l = 0, r = adjList2[v].size() - 1;
          while (l < r) {
            int m = (l + r + 1) / 2;
            if (disc[u] >= disc[adjList2[v][m]])
              l = m;
            else
              r = m - 1;
          }
          ans += ((long long int)(n - size[adjList2[v][l]]) * bigSum[v]) %
                 998244353;
        } else
          ans += ((long long int)size[v] * bigSum[v]) % 998244353;
        if (ans >= 998244353) ans -= 998244353;
      }
      printf("%I64d\n", ((long long int)ans * invn) % 998244353);
    }
  }
  return 0;
}