Gasoline Prices

Berlandia is a large country with $n$ cities. Its road network is a rooted tree, so the country has $n - 1$ roads, and between any two cities there is exactly one path that visits no city twice. For each city $i$, $p_i$ is the city that comes first on the way from city $i$ to city 1. In other words, when the tree is hung from city 1, $p_i$ is the parent of city $i$. Each city has one gas station. Station $i$ can sell gasoline at any price from $l_i$ to $r_i$ inclusive. The king has two sons every year for $m$ years. The sons take part in state affairs from early childhood, and at the end of each year they check that gasoline prices are fair. The sons born in year $i$ check prices on the path from $a_i$ to $b_i$ and on the path from $c_i$ to $d_i$. The check works as follows. Both sons start at the same time, from $a_i$ and $c_i$. The first son walks from $a_i$ to $b_i$, and the second walks from $c_i$ to $d_i$. They check that the price at $a_i$ equals the price at $c_i$. Then they check that the prices at the second cities of the two paths are equal. They repeat this for the third cities, and so on. Finally they check that the price at $b_i$ equals the price at $d_i$. The two paths are guaranteed to have the same length. The stations must obey the law, so no check may find a violation. Count the ways the stations can set prices over $m$ years. For each $i$ from 1 to $m$, count the ways to set prices at all stations so that after the first $i$ pairs of sons are born, every check passes and every station's price is within its allowed range. Print the answer modulo $10^9+7$.

The first line contains $n$ ($1 \le n \le 200000$), the number of cities. The second line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i \le n$). Each of the next $n$ lines contains $l_i$ and $r_i$ ($1 \le l_i \le r_i < 10^9+7$), the allowed price range at station $i$. The next line contains $m$ ($1 \le m \le 200000$). Each of the next $m$ lines contains $a_i$, $b_i$, $c_i$, and $d_i$ ($1 \le a_i, b_i, c_i, d_i \le n$). The lengths of the paths from $a_i$ to $b_i$ and from $c_i$ to $d_i$ are guaranteed to be equal.

Print $m$ lines, each with one integer. The $i$-th line is the number of ways to set prices so that the sons born in years up to and including year $i$ find no violation, modulo $10^9+7$.

Consider the first example. After the first two sons are born, the prices at cities 1 and 2 must be equal. There are 2 ways to choose one shared price for cities 1 and 2 that lies in both allowed ranges. So the total is $2 \cdot 3 \cdot 3 \cdot 1 = 18$. The second pair checks the paths $1 - 2$ and $2 - 1$. The prices at cities 1 and 2 are already equal, so the answer does not change after the second pair. The third pair checks the paths $3 - 1 - 2 - 4$ and $4 - 2 - 1 - 3$. Then the prices at cities 3 and 4 must be equal, and the prices at cities 1 and 2 must be equal. Cities 1 and 2 already match. There are 2 ways to choose a shared price for cities 3 and 4 within their ranges. So the total is $2 \cdot 2 \cdot 1 = 6$. The fourth pair checks the paths $3 - 1 - 2 - 4$ and $3 - 1 - 2 - 5$. Then the prices at cities 4 and 5 must be equal. Since cities 3 and 4 already match, cities 3, 4, and 5 must share one price. The price at city 3 must be at most 3, and the price at city 5 must be at least 4. So after the fourth pair is born, there is no way to set prices that pass every check and keep each price in its range.