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:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class D2 {
	static PrintWriter out = new PrintWriter(System.out);

	static int N;
	static int adj[][];
	static int[] pre,post,sz;
	static int curIter;
	static BIT bit;
	static int SQRT = 333;
	static long curRes[];
	static long MOD = 998244353;
	static int lift[][];
	static int dep[];
	static int LOG;
	static long modInv[];
	static final boolean debug = false;
	
	public static void main(String[] args) {
		modInv = new long[160000];
		for(int i = 0; i < 160000; i++)
		    modInv[i] = pow(i, MOD-2);
		 
		FS in = new FS();
		N = in.nextInt();
		int Q = in.nextInt();
		int inp[][] = new int[2][N-1];
		int sz2[] = new int[N];
		for(int i = 0; i < N-1; i++) {
			int a = in.nextInt()-1;
			int b = in.nextInt()-1;
			inp[0][i] = a;
			inp[1][i] = b;
			sz2[a]++;
			sz2[b]++;
		}
		
		adj = new int[N][];
		for(int i = 0; i < N; i++) adj[i] = new int[sz2[i]];
		for(int i = 0; i < N-1; i++) {
			int a = inp[0][i];
			int b = inp[1][i];
			adj[a][--sz2[a]] = b;
			adj[b][--sz2[b]] = a;
		}
		
		pre = new int[N]; post = new int[N]; sz = new int[N];
		LOG = Integer.numberOfTrailingZeros(Integer.highestOneBit(N))+1;
		lift = new int[N][LOG];
		dep = new int[N];
		dfs(0, -1, 0);
		
		
		bit = new BIT(curIter);
		int SQRT = 300;
		long curD[] = new long[N];
		int numBig = 0;
		boolean isBig[] = new boolean[N];
		for(int i = 0; i < N; i++) {
			if(adj[i].length >= SQRT) { isBig[i] = true; numBig++;}
		}
		int bigBois[] = new int[numBig];
		int idd = 0;
		for(int i = 0; i < N; i++) {
			if(adj[i].length >= SQRT) bigBois[idd++] = i;
		}
	
		for(int qq = 0; qq < Q; qq++) {
			int type = in.nextInt();
			if(type == 1) {
				int v = in.nextInt()-1;
				long d = in.nextLong();
				curD[v] = (curD[v] + d) % MOD;
				
				if(!isBig[v]) {
					for(int ii : adj[v]) {
						if(dep[ii] < dep[v]) { //parent
							int toAdd = add(0, d*sz[v], N);
							if(debug) System.out.println("v= "+v+"  ii="+ii+" n="+sz[v]);
							bit.update(pre[0], post[0], toAdd);
							bit.update(pre[v], post[v], -toAdd);
						}
						else {
							if(debug) System.out.println("v= "+v+"  ii="+ii+" n="+(N-sz[ii]));
							int toAdd = add(0, d*(N-sz[ii]),N);
							bit.update(pre[ii], post[ii], toAdd);
						}
					}
				}
			}
			else {
				int v = in.nextInt()-1;
				long cur = bit.sum(pre[v])%MOD;
				cur = add(cur, curD[v], 1);
				
				if(debug) System.out.println(" vv= "+v+" sum: "+bit.sum(pre[v])+" plus "+curD[v]);
				for(int ii : bigBois) {
					if(ii == v) continue;
					int lc = beforeLCA(ii, v);
					if(debug) System.out.println("  big="+ii+" lc="+lc+"  val="+curD[ii]);
					if(lc == -1) { // I'm a parent
						cur = add(cur, curD[ii]*sz[ii], N);
					}
					else { //he's a parent of me
						if(debug) System.out.println("   sz="+(N-sz[lc]));
						cur = add(cur, curD[ii]*(N-sz[lc]), N);
					}
				}
				out.println(cur);
			}
		}
		
		out.close();
	}
	
	static int add(long curVal, long num, long den) {
		if(num > MOD) num %= MOD;
		return (int) ((curVal + num*modInv[(int)den])%MOD);
	}
	
	// returns -1 if b is NOT in a's subtree
	static int beforeLCA(int a, int b) {
		if(dep[b] <= dep[a]) return -1;
		//move b up to dep[a] + 1
		for(int i = LOG-1; i >= 0; i--) {
			if(dep[lift[b][i]] > dep[a]) b = lift[b][i];
		}
		if(lift[b][0] != a) return -1;
		return b;
	}
	
	static class Pair{
		int v;
		long d;
		public Pair(int vv, long dd) {
			v=vv;
			d=dd;
		}
	}
	
	static void dfs(int node, int p, int d) {
		dep[node] = d;
		pre[node] = curIter++;
		sz[node] = 1;
		
		//bin lift
		if(p != -1) {
			int curNode = p;
			lift[node][0] = curNode;
			for(int i = 1; i < LOG; i++) {
				curNode = lift[curNode][i-1];
				lift[node][i] = curNode;
			}
		}
		
		
		for(int ii : adj[node]) {
			if(ii != p) {
				dfs(ii, node, d+1);
				sz[node] += sz[ii];
			}
		}
		post[node] = curIter++;
	}
	
	static long pow(long a, long b){
	    if(b == 0) return 1;
	    if(b == 1) return a;
	    if((b&1) == 0){
	        long res = pow(a, b>>1);
	        return (res*res)%MOD;
	    }
	    else{
	        return (a*pow(a,b-1))%MOD;
	    }
	}
	
	static class BIT {
		int n;
		int bar[];
		public BIT(int nn){
			bar = new int[nn+2];
			Arrays.fill(bar, 0);
			n = nn;
		}
		public void update(int a, int b, int val) {
			update(a, val);
			update(b+1, -val);
		}
		public void update(int index, int val){
			index++;
			while(index <= n){
				bar[index] += val;
				if(bar[index] >= MOD) bar[index] -= MOD;
				if(bar[index] < 0) bar[index] += MOD;
				index += index&-index;
			}
		}
		public long sum(int index){
			index++;
			long ans = 0;
			while(index > 0){
				ans += bar[index];
				if(ans >= MOD) ans -= MOD;
				index -= index&-index;
			}
			return ans;
		}
	}
	
	
	static class FS{
		BufferedReader br;
		StringTokenizer st;
		public FS() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {st = new StringTokenizer(br.readLine());}
				catch(Exception e) { throw null;}
			}
			return st.nextToken();
		}
		int nextInt() { return Integer.parseInt(next());}
		double nextDouble() { return Double.parseDouble(next());}
		long nextLong() { return Long.parseLong(next());}
		int[] NIA(int n) {
			int r[] = new int[n];
			for(int i = 0; i < n; i++) r[i] = nextInt();
			return r;
		}
		long[] NLA(int n) {
			long r[] = new long[n];
			for(int i = 0; i < n; i++) r[i] = nextLong();
			return r;
		}
		char[][] grid(int r, int c){
			char res[][] = new char[r][c];
			for(int i = 0; i < r; i++) {
				char l[] = next().toCharArray();
				for(int j = 0; j < c; j++) {
					res[i][j] = l[j];
				}
			}
			return res;
		}
	}
	
}