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;
int const N = 150000, W = 500, md = 998244353;
vector<int> bgw[N + 1], tr[N + 1], vq, bg;
int tman[N + 1], n, q, sall, sz[N + 1], pr[N + 1], tpr[N + 1], in[N + 1],
    out[N + 1], bgsm[N + 1], inv;
bool isbg[N + 1];
inline void ad(int &x, int y) {
  if ((x += y) >= md) x -= md;
}
int T;
void pl(int v = 1, int p = 0) {
  in[v] = T++;
  for (int &u : tr[v])
    if (u != p) pl(u, v);
  out[v] = T;
}
void plsz(int v, int p = 0) {
  sz[v] = 1;
  for (int &u : tr[v])
    if (u != p) {
      plsz(u, v);
      sz[v] += sz[u];
    }
}
int aI, aS;
void assz(int v, int p) {
  bgw[v][aI] = aS;
  for (int &u : tr[v])
    if (u != p) assz(u, v);
}
struct Q {
  int tp, v, d;
  void sc() {
    scanf("%d", &tp);
    if (tp == 1)
      scanf("%d%d", &v, &d);
    else
      scanf("%d", &v);
  }
} qu[N];
bool cmp(int a, int b) { return in[a] < in[b]; }
void dopr() {
  for (int i = 1; i < (int)(n); ++i) ad(tpr[i], tpr[i - 1]);
  for (int i = 0; i < (int)(n); ++i) ad(pr[i], tpr[i]);
  for (int i = 0; i < (int)(n); ++i) tpr[i] = 0;
}
int pw(int x, int p) {
  int an = 1;
  while (p) {
    if (p & 1) an = (long long)an * x % md;
    x = (long long)x * x % md;
    p >>= 1;
  }
  return an;
}
int main() {
  scanf("%d%d", &n, &q);
  inv = pw(n, md - 2);
  for (int i = 1; i < (int)(n); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    tr[a].push_back(b);
    tr[b].push_back(a);
  }
  pl();
  for (int i = 1; i < (int)(n + 1); ++i)
    if (tr[i].size() > W) bg.push_back(i), isbg[i] = true;
  for (int i = 1; i < (int)(n + 1); ++i) bgw[i].resize(bg.size());
  for (int i = 0; i < (int)(bg.size()); ++i) {
    plsz(bg[i]);
    aI = i;
    for (int &u : tr[bg[i]]) {
      aS = md - sz[u];
      assz(u, bg[i]);
    }
  }
  plsz(1);
  for (int i = 1; i < (int)(n + 1); ++i) sort(tr[i].begin(), tr[i].end(), cmp);
  for (int i = 0; i < (int)(q); ++i) qu[i].sc();
  for (int i = 0; i < (int)(q); ++i) {
    int j = i, s2 = W;
    vq.clear();
    while (j < q && s2) {
      if (qu[j].tp == 2) {
        --s2;
        vq.push_back(qu[j].v);
      }
      ++j;
    }
    sort(vq.begin(), vq.end(), cmp);
    vq.resize(unique(vq.begin(), vq.end()) - vq.begin());
    while (i < j) {
      if (qu[i].tp == 1) {
        int v = qu[i].v, d = qu[i].d;
        ad(sall, (long long)n * d % md);
        if (isbg[v])
          ad(bgsm[v], d);
        else {
          int k = 0;
          while (k < vq.size() && in[vq[k]] <= in[v]) {
            if (vq[k] != v)
              ad(tman[vq[k]], (long long)(md - (n - sz[v])) * d % md);
            ++k;
          }
          for (int i = 0; i < (int)(tr[v].size()); ++i) {
            int u = tr[v][i], c;
            if (in[u] < in[v]) {
              c = (long long)(md - (n - sz[v])) * d % md;
              ad(tpr[0], c);
              ad(tpr[in[v]], md - c);
              ad(tpr[out[v]], c);
            } else {
              c = (long long)(md - sz[u]) * d % md;
              ad(tpr[in[u]], c);
              ad(tpr[out[u]], md - c);
              while (k < vq.size() && in[vq[k]] < out[u]) {
                ad(tman[vq[k]], c);
                ++k;
              }
            }
          }
          while (k < vq.size()) {
            ad(tman[vq[k]], (long long)(md - (n - sz[v])) * d % md);
            ++k;
          }
        }
      } else {
        int v = qu[i].v;
        int an = tman[v];
        ad(an, pr[in[v]]);
        for (int i = 0; i < (int)(bg.size()); ++i)
          if (bg[i] != v) ad(an, (long long)bgsm[bg[i]] * bgw[v][i] % md);
        ad(an, sall);
        an = (long long)an * inv % md;
        printf("%d\n", an);
      }
      ++i;
    }
    for (int u : vq) tman[u] = 0;
    --i;
    dopr();
  }
}