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> G[150001];
vector<pair<int, long long> > queries;
int N;
int tin[150001], tout[150001];
int filhos[150001];
vector<pair<int, int> > toutfilhos[150001];
int t;
long long val[150001];
int dfsinout(int u, int pai = 0) {
  filhos[u] = 1;
  tin[u] = t++;
  for (auto v : G[u]) {
    if (pai != v) {
      filhos[u] += dfsinout(v, u);
      toutfilhos[u].push_back({tout[v], v});
    }
  }
  tout[u] = t++;
  return filhos[u];
}
long long modInverse(long long a, long long b) {
  return a > 1LL ? b - ((modInverse(b % a, a) * b) / a) : 1LL;
}
long long inv(long long a) {
  long long z = modInverse(a, 998244353);
  if (z < 0) return z + 998244353;
  return z;
}
long long subtrair[150001];
long long comecar[150001];
void dfs(int u, long long acum, int pai = 0) {
  if (acum >= 996491788296388609LL) acum -= 996491788296388609LL;
  acum -= subtrair[u];
  if (acum < 0) acum += 996491788296388609LL;
  val[u] += acum;
  if (val[u] >= 996491788296388609LL) val[u] -= 996491788296388609LL;
  for (auto v : G[u]) {
    if (pai != v) {
      dfs(v, acum + comecar[u] * (N - filhos[v]), u);
    }
  }
  subtrair[u] = 0;
  comecar[u] = 0;
}
int main() {
  int Q, N1, u, v, op;
  scanf("%d %d", &N, &Q);
  N1 = inv(N);
  for (int i = 1; i < N; i++) {
    scanf("%d %d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfsinout(1);
  while (Q--) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d %d", &u, &v);
      queries.push_back({u, v});
    } else {
      scanf("%d", &u);
      if (queries.size() >= 1000) {
        long long inicio = 0;
        for (auto q : queries) {
          val[q.first] += q.second * N;
          if (val[q.first] >= 996491788296388609LL)
            val[q.first] -= 996491788296388609LL;
          inicio += q.second * filhos[q.first];
          if (inicio >= 996491788296388609LL) inicio -= 996491788296388609LL;
          subtrair[q.first] += q.second * filhos[q.first];
          if (subtrair[q.first] >= 996491788296388609LL)
            subtrair[q.first] -= 996491788296388609LL;
          comecar[q.first] += q.second;
          if (comecar[q.first] >= 998244353) comecar[q.first] -= 998244353;
        }
        dfs(1, inicio);
        queries.clear();
      }
      long long ans = val[u];
      for (auto p : queries) {
        if (u == p.first) {
          ans += p.second * N;
          if (ans >= 996491788296388609LL) ans -= 996491788296388609LL;
        } else if (tin[p.first] <= tin[u] && tout[p.first] >= tin[u]) {
          int x = lower_bound(toutfilhos[p.first].begin(),
                              toutfilhos[p.first].end(), make_pair(tin[u], 0))
                      ->second;
          ans += p.second * (N - filhos[x]);
          if (ans >= 996491788296388609LL) ans -= 996491788296388609LL;
        } else {
          ans += p.second * filhos[p.first];
          if (ans >= 996491788296388609LL) ans -= 996491788296388609LL;
        }
      }
      printf("%lld\n", ((ans % 998244353) * N1) % 998244353);
    }
  }
  return 0;
}