B. Tree Path Price Queries
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes, rooted at node $$$1$$$. Each node $$$i$$$ contains $$$k_i$$$ items, all having the same price $$$p_i$$$.

You need to process several queries. Each query is described by four integers: $$$u$$$, $$$d$$$, $$$p_{\text{lower}}$$$, and $$$p_{\text{upper}}$$$.

For each query, you must determine the number of items that satisfy all of the following conditions:

  • Their price lies within the range $$$[p_{\text{lower}}, p_{\text{upper}}]$$$.
  • Their corresponding node lies within distance $$$d$$$ from node $$$u$$$.
  • Their node lies on the shortest path from node $$$u$$$ to the root node (node $$$1$$$).
Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of nodes in the tree.

Each of the next $$$n - 1$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n$$$; $$$a \ne b$$$), denoting an edge between nodes $$$a$$$ and $$$b$$$.

Then $$$n$$$ lines follow. The $$$i$$$-th of these lines contains two integers $$$k_i$$$ and $$$p_i$$$ ($$$0 \le k_i \le 10^5$$$, $$$1 \le p_i \le 10^9$$$) — the number of items and their common price at node $$$i$$$.

Then an integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) is given — the number of queries.

In the $$$i$$$'th line of the next $$$q$$$ lines contains four integers $$$U_i ~(1 \le U_i \le n)$$$, $$$D_i~(0 \le D_i \le n - 1)$$$, $$$PL_i$$$ and $$$PU_i~(1 \le PL_i, ~PU_i \le 10^9)$$$.

Let $$$ans_0 = 0$$$. For each query $$$i$$$, the actual parameters are decoded as follows: $$$$$$u = ((U_i + ans_{i-1}) \mod n) + 1,$$$$$$ $$$$$$d = (D_i + ans_{i-1}) \mod n,$$$$$$ $$$$$$p_{\text{lower}} = ((PL_i + ans_{i-1}) \mod 10^9) + 1,$$$$$$ $$$$$$p_{\text{upper}} = ((PU_i + ans_{i-1}) \mod 10^9) + 1.$$$$$$

If $$$p_{\text{lower}} \gt p_{\text{upper}}$$$, then these two values are swapped.

After decoding $$$1 \le u \le n$$$, $$$0 \le d \le n - 1$$$, $$$1 \le p_{\text{lower}} \le p_{\text{upper}} \le 10^9$$$.

After printing the answer to query $$$i$$$, it becomes $$$ans_i$$$, which is then used in decoding query $$$i+1$$$.

Output

For each query, print a single integer — the number of items satisfying the conditions above.

Example
Input
10
1 2
2 3
3 4
4 5
1 6
1 7
3 8
2 9
3 10
3 4
8 5
8 8
3 8
8 7
0 8
0 1
1 9
4 5
4 10
5
7 5 1 10
10 5 7 10
2 1 10 10
8 7 5 10
2 5 7 10
Output
20
0
0
0
8
Note
  • Query 1 $$$(u=8, d=5, p_{lower}=2, p_{upper}=11)$$$: path $$$8 \to 3 \to 2 \to 1$$$, all nodes in the path range $$$[2, 11]$$$, total $$$20$$$ items.
  • Query 2 $$$(u=1, d=5, p_{lower}=28, p_{upper}=31)$$$: path $$$1$$$, no node in price range $$$[28, 31]$$$, total $$$0$$$ item.
  • Query 3 $$$(u=3, d=1, p_{lower}=11, p_{upper}=11)$$$: path $$$3 \to 2$$$, no node with price $$$11$$$, total $$$0$$$ item.
  • Query 4 $$$(u=9, d=7, p_{lower}=6, p_{upper}=11)$$$: path $$$9 \to 2 \to 1$$$, no node in price range $$$[6, 11]$$$, total $$$0$$$ item.
  • Query 5 $$$(u=3, d=5, p_{lower}=8, p_{upper}=11)$$$: path $$$3 \to 2 \to 1$$$, node $$$3$$$ in price range $$$[8, 11]$$$, total $$$8$$$ items.