Tree of Almost Clean Money

Money grows on a tree with $N$ vertices. The vertices are numbered $0$ to $N-1$ and vertex $0$ is the root. Every vertex $i$ other than vertex $0$ has a parent $p(i)$ with $p(i) < i$. At the start, vertex $i$ holds $v(i)$ monetary units.

An organization runs $Q$ operations on the tree. Each operation has two steps.

1. Pick $K$ vertices $x(1), \dots, x(K)$ from the tree ($0 \le x(i) \le N-1$). The same vertex may be picked more than once. For each $i$ with $1 \le i \le K$, add $y(i)$ monetary units to vertex $x(i)$.
2. Pick two vertices $u$ and $v$ ($0 \le u, v \le N-1$). Compute the total amount of money held by the vertices on the unique path between $u$ and $v$, with $u$ and $v$ included.

Compute the answer to step 2 of every operation.

The limits are as follows.

• $1 \le N \le 500000$
• $1 \le Q \le 50000$
• $1 \le K \le 1000$
• $0 \le v(i) < 1000000007$
• $0 \le y(i) < 1000000007$

The first line contains the number of vertices $N$. Each of the next $N-1$ lines contains two space separated integers $p(i)$ and $i$ describing one edge of the tree. The next line contains the starting amounts $v(0), \dots, v(N-1)$, separated by spaces.

The next line contains the number of operations $Q$. Each of the next $Q$ lines describes one operation with nine space separated integers in this order: $K$, $x(1)$, $y(1)$, $A$, $B$, $C$, $D$, $u$, $v$ ($0 \le A, B, C, D < 1000000007$). Only $x(1)$ and $y(1)$ are given directly. The remaining values for $2 \le i \le K$ come from

$x(i) = (A \cdot x(i-1) + B) \bmod N$

$y(i) = (C \cdot y(i-1) + D) \bmod 1000000007$

Print $Q$ lines. Line $j$ contains the answer to step 2 of operation $j$. Money added in step 1 stays in the vertex, so every operation computes its answer with the step 1 additions of all earlier operations and of its own step 1 already applied.

An answer can exceed the range of a 32-bit integer.

In the first example, operation 1 has $A = C = 1$ and $B = D = 0$, so the value $1$ is added to vertex $1$ one thousand times. The path between vertex $0$ and vertex $2$ passes through vertices $0$, $1$, $2$, and the total amount of money in them is $1006$.

In operation 2 the generated values are $x(1)=0$, $y(1)=5$, $x(2)=1$, $y(2)=12$, and the path between vertex $2$ and vertex $3$ passes through every vertex of the tree.

In operation 3, $K = 1$, so $A$, $B$, $C$, $D$ are not used.