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;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios {
  fast_ios() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  };
} fast_ios_;
template <typename T>
void ndarray(vector<T> &vec, int len) {
  vec.resize(len);
}
template <typename T, typename... Args>
void ndarray(vector<T> &vec, int len, Args... args) {
  vec.resize(len);
  for (auto &v : vec) ndarray(v, args...);
}
template <typename T>
bool mmax(T &m, const T q) {
  if (m < q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
bool mmin(T &m, const T q) {
  if (m > q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) {
  return make_pair(l.first + r.first, l.second + r.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) {
  return make_pair(l.first - r.first, l.second - r.second);
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto v : vec) os << v << ",";
  os << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec) {
  os << "deq[";
  for (auto v : vec) os << v << ",";
  os << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa) {
  os << "(" << pa.first << "," << pa.second << ")";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp) {
  os << "{";
  for (auto v : mp) os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) {
  os << "{";
  for (auto v : mp) os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}
lint extgcd(lint a, lint b, lint &x, lint &y) {
  lint d = a;
  if (b != 0)
    d = extgcd(b, a % b, y, x), y -= (a / b) * x;
  else
    x = 1, y = 0;
  return d;
}
lint mod_inverse(lint a, lint m) {
  lint x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}
struct UndirectedTree {
  int V;
  int root;
  int dfs_cnt;
  vector<vector<int>> edge;
  UndirectedTree(int N = 0) : V(N), dfs_cnt(0), edge(N) {}
  void add_edge(int u, int v) {
    edge[u].emplace_back(v);
    edge[v].emplace_back(u);
  }
  vector<int> par;
  vector<int> subtree_size;
  vector<int> dfs_id;
  void _tree_dfs(int now, int prv) {
    par[now] = prv;
    subtree_size[now] = 1;
    dfs_id[now] = dfs_cnt++;
    for (auto nxt : edge[now])
      if (nxt != prv) {
        _tree_dfs(nxt, now);
        subtree_size[now] += subtree_size[nxt];
      }
  }
  void tree_dfs(int r) {
    root = r;
    par.resize(V, -1);
    subtree_size.resize(V, -1);
    dfs_id.resize(V, 0);
    dfs_cnt = 0;
    _tree_dfs(root, -1);
  }
  vector<int> prev_heavy;
  int DT;
  void _tree_dfs_th(int now, int prv, int ph) {
    prev_heavy[now] = ph;
    if ((int)edge[now].size() >= DT) ph = now;
    for (auto nxt : edge[now])
      if (nxt != prv) {
        _tree_dfs_th(nxt, now, ph);
      }
  }
  void tree_dfs_th(int B) {
    DT = B;
    prev_heavy.assign(V, -1);
    _tree_dfs_th(root, -1, -1);
  }
  vector<vector<int>> parinfo;
  void _hp_dfs(int now, int prv, int c, int r) {
    parinfo[r][now] = c;
    for (auto nxt : edge[now])
      if (nxt != prv) _hp_dfs(nxt, now, c, r);
  }
  void heavy_prepare() {
    parinfo.resize(V);
    for (int now = (0), now_end_ = (V); now < now_end_; now++)
      if ((int)edge[now].size() >= DT) {
        parinfo[now].resize(V);
        for (auto nxt : edge[now])
          if (nxt != par[now]) _hp_dfs(nxt, now, nxt, now);
      }
  }
};
constexpr lint MOD = 998244353;
struct BIT {
  using T = lint;
  int len;
  vector<T> val;
  BIT(int num) : len(num), val(num + 1) {}
  BIT() : BIT(0) {}
  void reset() { fill(val.begin(), val.end(), 0); }
  void _add(int pos, T v) {
    while (pos > 0 and pos <= len) {
      val[pos] += v;
      if (val[pos] >= MOD) val[pos] -= MOD;
      pos += pos & -pos;
    }
  }
  T _sum(int pos) const {
    T res = 0;
    while (pos > 0) res += val[pos], pos -= pos & -pos;
    return res % MOD;
  }
  void range_add(int l, int r, T v) {
    _add(l + 1, v);
    _add(r + 1, MOD - v);
  }
  T get(int x) { return _sum(x + 1); }
};
vector<lint> cache;
constexpr int B = 200;
int main() {
  int N, Q;
  cin >> N >> Q;
  UndirectedTree tree(N);
  for (int _ = (0), __end_ = (N - 1); _ < __end_; _++) {
    int u, v;
    cin >> u >> v;
    tree.add_edge(u - 1, v - 1);
  }
  tree.tree_dfs(0);
  tree.tree_dfs_th(B);
  tree.heavy_prepare();
  lint Ninv = mod_inverse(N, MOD);
  BIT bit(N);
  cache.resize(N);
  for (int _ = (0), __end_ = (Q); _ < __end_; _++) {
    int q, v;
    cin >> q >> v;
    v--;
    int bid = tree.dfs_id[v];
    if (q == 1) {
      lint d;
      cin >> d;
      lint stsz = tree.subtree_size[v];
      lint A = N - stsz;
      bit.range_add(0, N, d * stsz % MOD * Ninv % MOD);
      bit.range_add(bid, bid + stsz, d * A % MOD * Ninv % MOD);
      if ((int)tree.edge[v].size() >= B) {
        (cache[v] += d) %= MOD;
      } else {
        for (auto nxt : tree.edge[v])
          if (nxt != tree.par[v]) {
            lint cid = tree.dfs_id[nxt], cstsz = tree.subtree_size[nxt];
            bit.range_add(cid, cid + cstsz, MOD - d * cstsz % MOD * Ninv % MOD);
          }
      }
    } else {
      lint ret = bit.get(bid);
      while (tree.prev_heavy[v] >= 0) {
        int p = tree.prev_heavy[v];
        int c = tree.parinfo[p][v];
        ret = ret + MOD - cache[p] * tree.subtree_size[c] % MOD * Ninv % MOD;
        v = p;
      }
      ret %= MOD;
      printf("%lld\n", ret);
    }
  }
}