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;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
  cin.exceptions(ios::failbit);
}
template <typename T>
static constexpr T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
static constexpr T wrap_pos(T a, T m) {
  return a < 0 ? a + m : a;
}
template <typename T>
static constexpr T sqr(T a) {
  return a * a;
}
template <typename T>
static constexpr T mod(T a, T m) {
  return wrap_pos(a % m, m);
}
template <typename T>
static constexpr T inverse2(T a, T m) {
  return a <= 1 ? a : mod((1 - inverse2(m % a, a) * m) / a, m);
}
template <typename T>
static constexpr T inverse(T a, T m) {
  return inverse2(mod(a, m), m);
}
template <typename T, typename P>
static constexpr T power(T a, P b) {
  return b == 0 ? T(1) : (b % 2) ? power(a, b - 1) * a : sqr(power(a, b / 2));
}
template <typename T, typename C, T Modulus>
class MR {
 private:
  struct tag_plus {};
  struct tag_minus {};
  struct tag_good {};
  T value;
  static_assert(std::numeric_limits<C>::max() / Modulus / Modulus > 0,
                "compute type is too small");
  static_assert(Modulus < std::numeric_limits<T>::max() / 2,
                "storage type is too small");
  static constexpr T reduce(T value, tag_plus) {
    return value >= Modulus ? value - Modulus : value;
  }
  static constexpr T reduce(T value, tag_minus) {
    return value < 0 ? value + Modulus : value;
  }
  static constexpr T reduce(T value, tag_good) { return value; }

 public:
  static constexpr T modulus = Modulus;
  constexpr MR() : value(0) {}
  constexpr MR(C value) : value(reduce(value % Modulus, tag_minus())) {}
  template <typename tag_t>
  constexpr MR(T value, tag_t tag) : value(reduce(value, tag)) {}
  MR &operator=(C value) {
    this->value = reduce(value % Modulus, tag_minus());
    return *this;
  }
  constexpr MR operator+(MR b) const { return MR(value + b.value, tag_plus()); }
  constexpr MR operator-(MR b) const {
    return MR(value - b.value, tag_minus());
  }
  constexpr MR operator*(MR b) const {
    return MR(C(value) * C(b.value) % Modulus, tag_good());
  }
  constexpr MR operator-() const { return MR(-value, tag_minus()); }
  MR &operator+=(MR b) {
    value = reduce(value + b.value, tag_plus());
    return *this;
  }
  MR &operator-=(MR b) {
    value = reduce(value - b.value, tag_minus());
    return *this;
  }
  MR &operator*=(MR b) {
    value = C(value) * C(b.value) % Modulus;
    return *this;
  }
  constexpr bool operator==(MR b) const { return value == b.value; }
  constexpr bool operator!=(MR b) const { return value != b.value; }
  constexpr T get() const { return value; }
  constexpr MR inverse() const {
    return MR(::inverse(C(value), C(Modulus)), tag_good());
  }
  constexpr MR operator/(MR b) const { return *this * b.inverse(); }
  MR &operator/=(MR b) { return *this *= b.inverse(); }
};
template <typename T, typename C, T Modulus>
static inline std::ostream &operator<<(std::ostream &o, MR<T, C, Modulus> mr) {
  return o << mr.get();
}
template <typename T, typename Op = std::plus<T> >
class BIT {
 private:
  std::vector<T> values;
  Op op;
  T identity;

 public:
  explicit BIT(typename std::vector<T>::size_type size = 0, Op op = Op(),
               T identity = T())
      : values(size + 1, identity), op(op), identity(identity) {}
  typename std::vector<T>::size_type size() const { return values.size() - 1; }
  void add(typename std::vector<T>::size_type idx, T delta) {
    assert(idx < size());
    idx++;
    while (idx < values.size()) {
      values[idx] = op(values[idx], delta);
      idx += idx & ~(idx - 1);
    }
  }
  void add_pair(typename std::vector<T>::size_type idx1,
                typename std::vector<T>::size_type idx2, T delta) {
    add(idx1, delta);
    add(idx2, -delta);
  }
  T sum(typename std::vector<T>::size_type idx) const {
    assert(idx < size());
    T ans = identity;
    idx++;
    while (idx > 0) {
      ans = op(ans, values[idx]);
      idx &= idx - 1;
    }
    return ans;
  }
  T sum_exclusive(typename std::vector<T>::size_type idx) const {
    return (idx == 0) ? identity : sum(idx - 1);
  }
};
struct partition_t {
  int sizes;
  int start, end;
};
struct node {
  int id;
  int end;
  int size = 1;
  int parent = -1;
  vector<int> edges;
  vector<partition_t> parts;
};
static int N;
static vector<node> nodes;
static void make_tree(int cur, int parent) {
  node &n = nodes[cur];
  n.parent = parent;
  if (parent != -1) n.edges.erase(find(begin(n.edges), end(n.edges), parent));
  for (int y : n.edges) {
    make_tree(y, cur);
    n.size += nodes[y].size;
  }
  sort(begin(n.edges), end(n.edges),
       [&](int a, int b) { return nodes[a].size < nodes[b].size; });
}
static void label_tree(int cur, int &pool) {
  node &n = nodes[cur];
  n.id = pool++;
  for (int y : n.edges) label_tree(y, pool);
  n.end = pool;
  partition_t part{-1, -1, -1};
  for (int y : n.edges) {
    const node &z = nodes[y];
    if (part.sizes != -1 && z.size != part.sizes) {
      n.parts.push_back(part);
      part.sizes = -1;
    }
    if (part.sizes == -1) {
      part.sizes = nodes[y].size;
      part.start = nodes[y].id;
    }
    part.end = nodes[y].end;
  }
  if (part.sizes != -1) n.parts.push_back(part);
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  int Q;
  cin >> N >> Q;
  nodes.resize(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    nodes[u].edges.push_back(v);
    nodes[v].edges.push_back(u);
  }
  make_tree(0, -1);
  int pool = 0;
  label_tree(0, pool);
  BIT<MR<int, long long, 998244353> > bit(N + 1);
  MR<int, long long, 998244353> frac =
      MR<int, long long, 998244353>(N).inverse();
  for (int i = 0; i < Q; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int v, d;
      cin >> v >> d;
      v--;
      MR<int, long long, 998244353> scale = frac * d;
      const node &n = nodes[v];
      for (const auto &part : n.parts)
        bit.add_pair(part.start, part.end, scale * (N - part.sizes));
      bit.add_pair(n.id, n.id + 1, d);
      MR<int, long long, 998244353> outside = scale * n.size;
      bit.add_pair(0, n.id, outside);
      bit.add_pair(n.end, N, outside);
    } else {
      int v;
      cin >> v;
      v--;
      MR<int, long long, 998244353> ans = bit.sum(nodes[v].id);
      cout << ans << '\n';
    }
  }
  return 0;
}