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 JAVA):

Solution:
/**
 * Created by Aminul on 11/26/2019.
 */

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class D {
    static int MAGIC;
    static int TIME = 0, start[], end[], size[], par[];
    static int g[][], n;
    static long mod = 998244353, INV_N, lazy[]; // inv[];
    static ArrayDeque<int[]> heavyParList[];
    static int heavyParents[][][];
    static BinaryIndexTree BIT;

    public static void main(String[] args) throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        n = in.nextInt();
        MAGIC = 300;
        init();
        int q = in.nextInt();

        int from[] = new int[n - 1], to[] = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            from[i] = in.nextInt();
            to[i] = in.nextInt();
        }

        g = packU(n + 1, from, to);
        dfs(1, 0);

        ArrayDeque<Integer> heavyNodes = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (g[i].length >= MAGIC) heavyNodes.addLast(i);
        }
        getHeavyParents(heavyNodes);

        for (int i = 0; i < q; i++) {
            int op = in.nextInt(), u = in.nextInt();
            if (op == 1) {
                int d = in.nextInt();
                update(u, d);
            } else {
                pw.println(query(u));
            }
        }

        pw.close();
    }

    static void init() {
        TIME = 0;
        start = new int[n + 1];
        end = new int[n + 1];
        size = new int[n + 1];
        par = new int[n + 1];
        BIT = new BinaryIndexTree(n + 10);
        INV_N = modInverse(n, mod);
        lazy = new long[n + 1];
    }


    static void update(int v, long d) {
        lazy[v] = (lazy[v] + d) % mod;
        long dn = (d * INV_N) % mod;
        if (g[v].length < MAGIC) {
            for (int u : g[v]) {
                if (u != par[v]) BIT.add(start[u], end[u], (n - size[u]) * dn % mod);
            }
        }
        if (v != 1) {
            BIT.add(1, start[v] - 1, (dn * size[v]) % mod);
            BIT.add(end[v] + 1, BIT.n - 1, (dn * size[v]) % mod);
        }
    }

    static long query(int u) {
        long res = (lazy[u] + BIT.sum(start[u])) % mod;
        for (int h[] : heavyParents[u]) {
            res = (res + (lazy[h[0]] * h[1])) % mod;
        }
        return res;
    }


    static void dfs(int u, int p) {
        par[u] = p;
        size[u] = 1;
        start[u] = ++TIME;
        for (int v : g[u]) {
            if (v != p) {
                dfs(v, u);
                size[u] += size[v];
            }
        }
        end[u] = TIME;
    }

    static void getHeavyParents(ArrayDeque<Integer> heavy) {
        heavyParList = genDQ(n + 1);
        for (int u : heavy) {
            for (int c : g[u]) {
                if (c != par[u]) dfs(c, u, u, (int) (((n - size[c]) * INV_N) % mod));
            }
        }
        heavyParents = new int[n + 1][][];
        for (int i = 1; i <= n; i++) {
            heavyParents[i] = new int[heavyParList[i].size()][];
            int j = 0;
            for(int a[] : heavyParList[i]) heavyParents[i][j++] = a;
        }
    }


    static void dfs(int u, int p, int parent, int size) {
        heavyParList[u].addLast(new int[]{parent, size});
        for (int v : g[u]) {
            if (v != p) dfs(v, u, parent, size);
        }
    }

    static <T> ArrayDeque<T>[] genDQ(int n) {
        ArrayDeque<T> list[] = new ArrayDeque[n];
        for (int i = 0; i < n; i++) list[i] = new ArrayDeque<T>();
        return list;
    }

    static int[][] packU(int n, int[] from, int[] to) {
        int[][] g = new int[n][];
        int[] p = new int[n];
        for (int f : from)
            p[f]++;
        for (int t : to)
            p[t]++;
        for (int i = 0; i < n; i++)
            g[i] = new int[p[i]];
        for (int i = 0; i < from.length; i++) {
            g[from[i]][--p[from[i]]] = to[i];
            g[to[i]][--p[to[i]]] = from[i];
        }
        return g;
    }

    public static long mod(long a, long m) {
        long A = (a % m);
        return A >= 0 ? A : A + m;
    }

    public static long modInverse(long a, long m) {
        a = mod(a, m);
        return a == 0 ? 0 : mod((1 - modInverse(m % a, a) * m) / a, m);
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class BinaryIndexTree {
        public long bit[];
        public int n;

        public BinaryIndexTree(int N) {
            n = N;
            bit = new long[n];
        }

        public void add(int i, int j, long value) {
            add(i, value);
            add(j + 1, -value);
        }

        public void add(int i, long value) {
            value = mod(value, mod);
            for (; i < n; i = i + (i & -i)) {
                bit[i] += value;
                if (bit[i] >= mod) bit[i] -= mod;
            }
        }

        public long sum(int i) {
            long sum = 0;
            for (; i > 0; i = i - (i & -i)) {
                sum += bit[i];
                if (sum >= mod) sum -= mod;
            }
            return sum;
        }

        public long query(int i, int j) {
            return mod(sum(j) - sum(i - 1), mod);
        }
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;

        public FastReader(InputStream is) {
            this.is = is;
        }

        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }


        public String nextLine() {
            int c = skip();
            StringBuilder sb = new StringBuilder();
            while (!isEndOfLine(c)) {
                sb.appendCodePoint(c);
                c = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        public char readChar() {
            return (char) skip();
        }
    }
}