H. Hardcore Aura Farming
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

João Carlos and Arthur are big streamers in the world of Roblox. They decided to team up for a collaboration event!

Arthur wants to make the best collaboration possible, so he modeled the $$$N$$$ Roblox games he has in common with João as a tree: an undirected, connected, and acyclic graph. To study the impact on the community, he will conduct $$$Q$$$ simulations, where in the $$$i$$$-th simulation, he will ask João to play with his followers the games corresponding to the vertices on the path* from $$$S_i$$$ to $$$F_i$$$.

João currently has $$$M$$$ followers, each identified by a different integer from $$$1$$$ to $$$M$$$ according to their skill in Roblox. During the simulations, to keep the matches interesting, João decided that for every game $$$j$$$, he will play it with all his followers with identifiers from $$$L_j$$$ to $$$R_j$$$. Additionally, since João is a pro player, every follower who plays with him the game $$$j$$$ will immediately gain $$$K_j$$$ aura (those who do not play gain $$$0$$$ aura).

Thus, at the end of simulation $$$i$$$, every follower $$$k$$$ ends up with an accumulated aura $$$A_{i, k}$$$, which is the sum of the auras they gained throughout all the games played by João in that simulation. As part of his analysis, Arthur would like to calculate the result $$$W_i$$$, which is the sum of the accumulated auras of the followers with identifiers from $$$X_i$$$ to $$$Y_i$$$, that is, $$$W_i = \sum_{k = X_i}^{Y_i} A_{i, k}$$$.

However, Arthur needs to do his Studies in Security work. Help him calculate the results $$$W$$$ for all $$$Q$$$ simulations! Since each $$$W$$$ can be very large, you must print the remainder of $$$W$$$ when divided by $$$998244353$$$.

Note that the simulations are INDEPENDENT, meaning the accumulated aura does NOT persist between simulations.

*: In a tree, there is only one path between two vertices that does not pass through the same vertex more than once.

Input

The first line contains two integers: $$$N$$$ $$$(1 \le N \le 5 \cdot 10^4)$$$ and $$$M$$$ $$$(1 \le M \le 10^{9})$$$, representing the number of games and the number of João Carlos's followers.

The next $$$N-1$$$ lines contain two distinct integers $$$U$$$ and $$$V$$$ $$$(1 \le U, V \le N)$$$ indicating that there is an edge between the vertices corresponding to games $$$U$$$ and $$$V$$$.

This is followed by $$$N$$$ lines containing three integers. The $$$j$$$-th line contains $$$L_j$$$, $$$R_j$$$ $$$(1 \le L_j \le R_j \le M)$$$ and $$$K_j$$$ $$$(1 \le K_i \lt 998244353)$$$, the integers associated with game $$$j$$$.

The next line contains an integer $$$Q$$$ $$$(1 \le Q \le 5 \cdot 10^4)$$$, the number of simulations.

Finally, there are $$$Q$$$ lines containing four integers. These integers are encrypted. Let $$$W_{i-1}$$$ be the result of the $$$(i-1)$$$-th simulation (if $$$i = 1$$$, $$$W_{i-1} = 0$$$). Your program will receive $$$S_i \oplus W_{i-1}$$$, $$$F_i \oplus W_{i-1}$$$ $$$(1 \le S_i, F_i \le N)$$$, $$$X_i \oplus W_{i-1}$$$ and $$$Y_i \oplus W_{i-1}$$$ $$$(1 \le X_i \le Y_i \le M)$$$ describing the parameters of the $$$i$$$-th simulation.

Output

Write $$$Q$$$ lines, each containing a single integer. The $$$i$$$-th line should contain $$$W_i$$$: the result of the $$$i$$$-th simulation.

Example
Input
10 10
3 4
9 6
1 9
4 5
4 2
5 6
7 10
4 8
10 1
6 9 10
4 6 8
7 9 1
1 3 6
5 7 1
3 6 1
5 8 10
9 9 10
2 5 4
6 6 7
10
6 2 2 6
40 40 45 32
3 5 9 10
0 5 3 7
42 46 46 38
44 40 35 34
38 37 35 37
5 5 13 13
13 12 2 2
23 28 17 29
Output
42
0
1
44
43
32
4
10
20
13
Note

$$$\oplus$$$ indicates the XOR (exclusive OR) operation applied bit by bit. For example, $$$3$$$ is $$$0011$$$ in binary, and $$$5$$$ is $$$0101$$$. $$$3 \oplus 5 = 6$$$, which is $$$0110$$$ in binary.