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;
namespace IO {
const int BUFFER_SIZE = 1 << 15;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;
char output_buffer[BUFFER_SIZE];
int output_pos = 0;
char number_buffer[100];
uint8_t lookup[100];
void _update_input_buffer() {
  input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
  input_pos = 0;
  if (input_len == 0) input_buffer[0] = EOF;
}
inline char next_char(bool advance = true) {
  if (input_pos >= input_len) _update_input_buffer();
  return input_buffer[advance ? input_pos++ : input_pos];
}
template <typename T>
inline void read_int(T &number) {
  bool negative = false;
  number = 0;
  while (!isdigit(next_char(false)))
    if (next_char() == '-') negative = true;
  do {
    number = 10 * number + (next_char() - '0');
  } while (isdigit(next_char(false)));
  if (negative) number = -number;
}
template <typename T, typename... Args>
inline void read_int(T &number, Args &...args) {
  read_int(number);
  read_int(args...);
}
void _flush_output() {
  fwrite(output_buffer, sizeof(char), output_pos, stdout);
  output_pos = 0;
}
inline void write_char(char c) {
  if (output_pos == BUFFER_SIZE) _flush_output();
  output_buffer[output_pos++] = c;
}
template <typename T>
inline void write_int(T number, char after = '\0') {
  if (number < 0) {
    write_char('-');
    number = -number;
  }
  int length = 0;
  while (number >= 10) {
    uint8_t lookup_value = lookup[number % 100];
    number /= 100;
    number_buffer[length++] = (lookup_value & 15) + '0';
    number_buffer[length++] = (lookup_value >> 4) + '0';
  }
  if (number != 0 || length == 0) write_char(number + '0');
  for (int i = length - 1; i >= 0; i--) write_char(number_buffer[i]);
  if (after) write_char(after);
}
void init() {
  bool exit_success = atexit(_flush_output) == 0;
  assert(exit_success);
  for (int i = 0; i < 100; i++) lookup[i] = (i / 10 << 4) + i % 10;
}
}  // namespace IO
const int MOD = 998244353;
struct mod_int {
  int val;
  mod_int(long long v = 0) {
    if (v < 0) v = v % MOD + MOD;
    if (v >= MOD) v %= MOD;
    val = v;
  }
  static int mod_inv(int a, int m = MOD) {
    int g = m, r = a, x = 0, y = 1;
    while (r != 0) {
      int q = g / r;
      g %= r;
      swap(g, r);
      x -= q * y;
      swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  explicit operator int() const { return val; }
  mod_int &operator+=(const mod_int &other) {
    val += other.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  mod_int &operator-=(const mod_int &other) {
    val -= other.val;
    if (val < 0) val += MOD;
    return *this;
  }
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    return x % m;
    unsigned x_high = x >> 32, x_low = (unsigned)x;
    unsigned quot, rem;
    asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
    return rem;
  }
  mod_int &operator*=(const mod_int &other) {
    val = fast_mod((uint64_t)val * other.val);
    return *this;
  }
  mod_int &operator/=(const mod_int &other) { return *this *= other.inv(); }
  friend mod_int operator+(const mod_int &a, const mod_int &b) {
    return mod_int(a) += b;
  }
  friend mod_int operator-(const mod_int &a, const mod_int &b) {
    return mod_int(a) -= b;
  }
  friend mod_int operator*(const mod_int &a, const mod_int &b) {
    return mod_int(a) *= b;
  }
  friend mod_int operator/(const mod_int &a, const mod_int &b) {
    return mod_int(a) /= b;
  }
  mod_int &operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
  mod_int &operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
  mod_int operator++(int) {
    mod_int before = *this;
    ++*this;
    return before;
  }
  mod_int operator--(int) {
    mod_int before = *this;
    --*this;
    return before;
  }
  mod_int operator-() const { return val == 0 ? 0 : MOD - val; }
  bool operator==(const mod_int &other) const { return val == other.val; }
  bool operator!=(const mod_int &other) const { return val != other.val; }
  mod_int inv() const { return mod_inv(val); }
  mod_int pow(long long p) const {
    assert(p >= 0);
    mod_int a = *this, result = 1;
    while (p > 0) {
      if (p & 1) result *= a;
      a *= a;
      p >>= 1;
    }
    return result;
  }
  friend ostream &operator<<(ostream &stream, const mod_int &m) {
    return stream << m.val;
  }
};
struct LCA {
  int n = 0;
  vector<vector<int>> adj;
  vector<int> parent, subtree_size;
  vector<int> tour_start, tour_end;
  vector<int> heavy_root;
  LCA(int _n = 0) { init(_n); }
  LCA(const vector<vector<int>> &_adj) { init(_adj); }
  void init(int _n) {
    n = _n;
    adj.assign(n, {});
    parent.resize(n);
    subtree_size.resize(n);
    tour_start.resize(n);
    tour_end.resize(n);
    heavy_root.resize(n);
  }
  void init(const vector<vector<int>> &_adj) {
    init(_adj.size());
    adj = _adj;
  }
  void add_edge(int a, int b) {
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  void dfs(int node, int par) {
    parent[node] = par;
    subtree_size[node] = 1;
    if (par >= 0)
      adj[node].erase(find(adj[node].begin(), adj[node].end(), par));
    for (int &child : adj[node]) {
      dfs(child, node);
      subtree_size[node] += subtree_size[child];
      if (subtree_size[child] > subtree_size[adj[node].front()])
        swap(child, adj[node].front());
    }
  }
  int tour, post_tour;
  void tour_dfs(int node, bool heavy) {
    heavy_root[node] = heavy ? heavy_root[parent[node]] : node;
    tour_start[node] = tour++;
    bool heavy_child = true;
    for (int child : adj[node]) {
      tour_dfs(child, heavy_child);
      heavy_child = false;
    }
    tour_end[node] = tour;
  }
  void build() {
    parent.assign(n, -1);
    for (int i = 0; i < n; i++)
      if (parent[i] < 0) dfs(i, -1);
    tour = post_tour = 0;
    for (int i = 0; i < n; i++)
      if (parent[i] < 0) tour_dfs(i, false);
  }
};
template <typename T>
struct fenwick_tree {
  int tree_n = 0;
  T tree_sum = 0;
  vector<T> tree;
  fenwick_tree(int n = -1) {
    if (n >= 0) init(n);
  }
  void init(int n) {
    tree_n = n;
    tree_sum = 0;
    tree.assign(tree_n + 1, 0);
  }
  template <typename T_array>
  void build(const T_array &initial) {
    assert((int)initial.size() == tree_n);
    tree_sum = 0;
    for (int i = 1; i <= tree_n; i++) {
      tree[i] = initial[i - 1];
      tree_sum += initial[i - 1];
      for (int k = (i & -i) >> 1; k > 0; k >>= 1) tree[i] += tree[i - k];
    }
  }
  void update(int index, const T &change) {
    assert(0 <= index && index < tree_n);
    tree_sum += change;
    for (int i = index + 1; i <= tree_n; i += i & -i) tree[i] += change;
  }
  T query(int count) const {
    assert(count <= tree_n);
    T sum = 0;
    for (int i = count; i > 0; i -= i & -i) sum += tree[i];
    return sum;
  }
  T query_suffix(int start) const { return tree_sum - query(start); }
  T query(int a, int b) const { return query(b) - query(a); }
  T get(int a) const {
    assert(0 <= a && a < tree_n);
    int above = a + 1;
    T sum = tree[above];
    above -= above & -above;
    while (a != above) {
      sum -= tree[a];
      a -= a & -a;
    }
    return sum;
  }
  int find_last_prefix(T sum) const {
    if (sum < 0) return -1;
    int prefix = 0;
    for (int k = 31 - __builtin_clz(tree_n); k >= 0; k--)
      if (prefix + (1 << k) <= tree_n && tree[prefix + (1 << k)] <= sum) {
        prefix += 1 << k;
        sum -= tree[prefix];
      }
    return prefix;
  }
};
template <typename T>
struct range_add_point_query_tree {
  int tree_n = 0;
  fenwick_tree<T> tree;
  range_add_point_query_tree(int n = -1) {
    if (n >= 0) init(n);
  }
  void init(int n) {
    tree_n = n;
    tree.init(n);
  }
  template <typename T_array>
  void build(const T_array &initial) {
    assert((int)initial.size() == tree_n);
    vector<T> initial_diffs(tree_n);
    for (int i = 0; i < tree_n; i++)
      initial_diffs[i] = initial[i] - (i > 0 ? initial[i - 1] : 0);
    tree.build(initial_diffs);
  }
  void update(int start, int end, const T &change) {
    assert(0 <= start && start <= end && end <= tree_n);
    if (start < tree_n) tree.update(start, change);
    if (end < tree_n) tree.update(end, -change);
  }
  T query(int index) const {
    assert(0 <= index && index < tree_n);
    return tree.query(index + 1);
  }
};
int main() {
  IO::init();
  int N, Q;
  IO::read_int(N, Q);
  LCA lca(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    IO::read_int(u, v);
    u--;
    v--;
    lca.add_edge(u, v);
  }
  lca.build();
  vector<mod_int> delta(N, 0), updates(N, 0);
  range_add_point_query_tree<mod_int> tree(N);
  mod_int everyone = 0;
  mod_int inv_N = mod_int(1) / N;
  for (int q = 0; q < Q; q++) {
    int type, v;
    mod_int d;
    IO::read_int(type, v);
    v--;
    if (type == 1) {
      int d_int;
      IO::read_int(d_int);
      d = d_int;
      mod_int above = lca.subtree_size[v] * d;
      everyone += above;
      delta[v] -= above;
      if (!lca.adj[v].empty()) {
        int child = lca.adj[v][0];
        tree.update(lca.tour_start[child], lca.tour_end[child],
                    (N - lca.subtree_size[child]) * d - above);
      }
      updates[v] += d;
    } else if (type == 2) {
      mod_int answer =
          (everyone + tree.query(lca.tour_start[v]) + delta[v]) * inv_N +
          updates[v];
      mod_int light_sum = 0;
      while (true) {
        v = lca.heavy_root[v];
        int p = lca.parent[v];
        if (p < 0) break;
        light_sum +=
            (N - lca.subtree_size[v] - lca.subtree_size[p]) * updates[p];
        v = p;
      }
      answer += light_sum * inv_N;
      IO::write_int((int)answer, '\n');
    } else {
      assert(false);
    }
  }
}