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;
constexpr long long N = 2e5 + 5;
constexpr long long M = 998244353;
struct IO {
  char buf[(1 << 20)], *p1, *p2;
  char pbuf[(1 << 20)], *pp;
  IO() : p1(buf), p2(buf), pp(pbuf) {}
  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
  inline char gc() {
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, (1 << 20), stdin);
    return p1 == p2 ? ' ' : *p1++;
  }
  inline bool blank(char ch) {
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
  }
  template <class T>
  inline void read(T& x) {
    double tmp = 1;
    bool sign = 0;
    x = 0;
    char ch = gc();
    for (; !(ch >= '0' && ch <= '9'); ch = gc())
      if (ch == '-') sign = 1;
    for (; (ch >= '0' && ch <= '9'); ch = gc()) x = x * 10 + (ch - '0');
    if (ch == '.')
      for (ch = gc(); (ch >= '0' && ch <= '9'); ch = gc())
        tmp /= 10.0, x += tmp * (ch - '0');
    if (sign) x = -x;
  }
  inline void read(char* s) {
    char ch = gc();
    for (; blank(ch); ch = gc())
      ;
    for (; !blank(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }
  inline void read(char& c) {
    for (c = gc(); blank(c); c = gc())
      ;
  }
  inline void push(const char& c) {
    if (pp - pbuf == (1 << 20)) fwrite(pbuf, 1, (1 << 20), stdout), pp = pbuf;
    *pp++ = c;
  }
  template <class T>
  inline void write(T x) {
    if (x < 0) x = -x, push('-');
    static T sta[35];
    T top = 0;
    do {
      sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) push(sta[--top] + '0');
  }
  template <class T>
  inline void write(T x, char lastChar) {
    write(x), push(lastChar);
  }
} io;
namespace RMQ {
template <class V, class U, class Q, long long N>
class SegTree {
 private:
  function<V(const V& l, const V& r)> pu;
  function<Q(const V& v)> q;
  function<Q(const Q& l, const Q& r)> qu;
  function<void(V& v, const U& u)> up;
  function<void(U& u, const U& off)> upt;
  struct SegNode {
    unsigned id, l, r, m;
    V val;
    U tag;
    SegTree* parent() {
      return (SegTree*)((char*)this - offsetof(SegTree, nodes[0]) -
                        id * sizeof(nodes[0]));
    }
    void build(unsigned idx, unsigned s, unsigned e) {
      id = idx, l = s, r = e, m = (l + r) >> 1;
      if (l != r)
        left().build(idx << 1, s, m), right().build((idx << 1) + 1, m + 1, e);
    }
    void build(unsigned idx, unsigned s, unsigned e, V* a) {
      id = idx, l = s, r = e, m = (l + r) >> 1;
      if (l != r)
        left().build(idx << 1, s, m, a),
            right().build((idx << 1) + 1, m + 1, e, a), pushup();
      else
        val = a[l];
    }
    void pushup() { val = parent()->pu(left().val, right().val); }
    void pushdown() {
      if (l == r || tag == U(0)) return;
      left().update(l, m, tag), right().update(m + 1, r, tag);
      pushup();
      tag = U(0);
    }
    Q query(unsigned s, unsigned e) {
      if (s == l && r == e) {
        return parent()->q(val);
      }
      pushdown();
      if (e <= m) return left().query(s, e);
      if (s > m) return right().query(s, e);
      return parent()->qu(left().query(s, m), right().query(m + 1, e));
    }
    void update(unsigned s, unsigned e, U off) {
      if (s == l && r == e) {
        parent()->up(val, off);
        parent()->upt(tag, off);
        return;
      }
      pushdown();
      if (e <= m)
        left().update(s, e, off);
      else if (s > m)
        right().update(s, e, off);
      else
        left().update(s, m, off), right().update(m + 1, e, off);
      pushup();
    }
    SegNode& left() { return parent()->nodes[id << 1]; }
    SegNode& right() { return parent()->nodes[(id << 1) + 1]; }
  } nodes[N * 4];

 public:
  SegTree(function<V(const V& l, const V& r)> pu, function<Q(const V& v)> q,
          function<Q(const Q& l, const Q& r)> qu,
          function<void(V& v, const U& u)> up,
          function<void(U& u, const U& off)> upt)
      : pu(pu), q(q), qu(qu), up(up), upt(upt) {}
  void build(signed l, signed r) { nodes[1].build(1, l, r); }
  void build(signed l, signed r, V* a) { nodes[1].build(l, r, a); }
  void update(signed s, signed e, U off) { nodes[1].update(s, e, off); }
  Q query(signed s, signed e) { return nodes[1].query(s, e); }
};
template <class T>
T sum(const T& l, const T& r) {
  return l + r;
}
template <class T>
T max(const T& l, const T& r) {
  return std::max(l, r);
}
template <class T>
T min(const T& l, const T& r) {
  return std::min(l, r);
}
template <class T>
T query_sum(const T& l, const T& r) {
  return l + r;
}
template <class T>
T query_val(const T& l) {
  return l;
}
template <class T>
void update(T& v, const T& off) {
  v += off;
}
template <class T>
void update_tag(T& v, const T& off) {
  v += off;
}
template <class T, T M>
T sum(const T& l, const T& r) {
  return (l + r + M) % M;
}
template <class T, T M>
void update(T& v, const T& off) {
  v = (v + off + M) % M;
}
template <class T, T M>
void update_tag(T& v, const T& off) {
  v = (v + off + M) % M;
}
template <class T, long long N>
struct BIT {
  T c[N];
  inline signed lowbit(signed x) { return x & -x; }
  inline void add(signed x, T off) {
    for (signed i = x; i < N; i += lowbit(i)) c[i] += off;
  }
  inline T sum(signed x) {
    T ans = 0;
    for (signed i = x; i; i -= lowbit(i)) ans += c[i];
    return ans;
  }
};
}  // namespace RMQ
long long kpow(long long a, long long b) {
  long long c = 1 % M;
  while (b) {
    if (b & 1) c = c * a % M;
    a = a * a % M;
    b >>= 1;
  }
  return c;
}
inline long long inv(long long x) { return kpow(x, M - 2); }
long long n, q;
RMQ::SegTree<long long, long long, long long, N> tree(
    RMQ::sum<long long, M>, RMQ::query_val<long long>, RMQ::sum<long long, M>,
    RMQ::update<long long, M>, RMQ::update_tag<long long, M>);
vector<long long> g[N];
long long par[N], sz[N], son[N], top[N], dfn[N], rnk[N], d[N], w[N];
long long tot;
void dfs(long long u, long long p) {
  par[u] = p;
  d[u] = d[p] + 1;
  sz[u] = 1;
  for (long long v : g[u]) {
    if (v == p) continue;
    dfs(v, u);
    sz[u] += sz[v];
    if (sz[v] > sz[son[u]]) son[u] = v;
  }
}
void dfs2(long long u, long long t) {
  top[u] = t;
  dfn[u] = ++tot;
  rnk[dfn[u]] = u;
  if (son[u]) dfs2(son[u], t);
  for (long long v : g[u]) {
    if (v == par[u] || v == son[u]) continue;
    dfs2(v, v);
  }
}
signed main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  ;
  io.read(n), io.read(q);
  long long V = inv(n);
  for (long long i = 1; i <= n - 1; i++) {
    long long u, v;
    io.read(u), io.read(v);
    g[u].push_back(v), g[v].push_back(u);
  }
  dfs(1, 0);
  dfs2(1, 1);
  tree.build(1, n);
  while (q--) {
    long long o, v, d;
    io.read(o);
    io.read(v);
    if (o == 1) {
      io.read(d);
      long long t = sz[v] * d % M;
      w[v] = (w[v] + d) % M;
      tree.update(1, n, t);
      tree.update(dfn[v], dfn[v] + sz[v] - 1, M - t);
      if (son[v]) {
        tree.update(dfn[son[v]], dfn[son[v]] + sz[son[v]] - 1,
                    (n - sz[son[v]]) * d % M);
      }
    } else {
      long long ans = (w[v] * n % M + tree.query(dfn[v], dfn[v])) % M;
      for (v = top[v]; par[v]; v = top[par[v]]) {
        ans = (ans + (n - sz[v]) * w[par[v]] % M) % M;
      }
      io.write(ans * V % M, '\n');
    }
  }
  return 0;
}