G. Mayor
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You just moved in your new country A.G.M. Lands and the mayor already called you in to give you a task. The elections are coming and the mayor heard that you are an amazing programmer, therefore he wants you to help him build a program that will let him understand what are his chances of success. You know that the country can be represented as a tree, that initially everyone loves the mayor and would 100% vote for him, and that both the mayor and his opponent are able to send their employees out in the country to try and persuade the residents to change their vote. Formally, you are given a tree containing $$$N$$$ nodes (rooted at node $$$1$$$), where each node has an initial probability of $$$1$$$ to vote for the Mayor, and $$$Q$$$ operations of the following types:

  1. $$$1$$$ $$$x$$$ $$$y$$$ $$$p$$$ $$$q$$$ $$$(0 \le p \lt 998244353, 1 \le q \lt 998244353, p \le q)$$$ - The Mayor's opponent will send out an employee to all residents between nodes $$$x$$$ and $$$y$$$ to convince them NOT to vote with the Mayor. For each resident, he has a probability of $$$p/q$$$ to convince them.
  2. $$$2$$$ $$$x$$$ $$$y$$$ $$$p$$$ $$$q$$$ $$$(0 \le p \lt 998244353, 1 \le q \lt 998244353, p \le q)$$$ - The Mayor will send out an employee to all residents between nodes $$$x$$$ and $$$y$$$ to convince them to vote with the Mayor. For each resident, he has a probability of $$$p/q$$$ to convince them.
  3. $$$3$$$ $$$x$$$ - The Mayor asks what is the expected value of the number of residents living in the subtree of node $$$x$$$ that will vote for him in that exact moment. The answer to this question should be given modulo $$$998244353$$$. The root of the tree is node $$$1$$$.
Input

On the first line, you are given an integer $$$N$$$ ($$$1 \le N \le 10^5$$$) denoting the number of residents. On the next $$$N - 1$$$ lines, there are two integers, $$$x$$$ ($$$1 \le x \le N$$$) and $$$y$$$ ($$$1 \le y \le N$$$), representing that there is a road between resident $$$x$$$ and resident $$$y$$$. On the next line, you are given an integer $$$Q$$$ ($$$1 \le Q \le 10^5$$$) denoting the number of operations. The next $$$Q$$$ lines will each contain the description of an operation as described above. Please note that for the operations $$$1$$$ and $$$2$$$, you should also take into account what the previous probability was and update accordingly. For example, if someone had a probability of $$$1$$$ to vote for the Mayor, and operation $$$2$$$ happens, the probability would remain $$$1$$$ since that person was already voting for the Mayor, therefore persuasion work was redundant.

Output

For each question from the mayor, print the answer modulo $$$998244353$$$ on a new line.

Example
Input
6
1 2
1 3
1 4
4 5
4 6
5
3 1
1 6 5 1 3
3 1
1 3 2 2 3
3 1
Output
6
5
3