Berland is a vast country consisting of $n$ cities. The road network of Berland can be represented as a rooted tree, meaning there are $n-1$ roads in total, and one can reach any city from any other city by exactly one path without visiting any city twice. For convenience in representing the country, for each city $i$, a city $p_i$ is fixed, which is the first city one must travel to from city $i$ to reach city 1. In other words, city $p_i$ is the parent of city $i$ if the tree is rooted at city 1.

Each city in Berland has one gas station. Gas stations have a special pricing policy, and for each station, a range of prices at which they are willing to sell gasoline is fixed. A gas station in city $i$ is willing to sell gasoline at any price from $l_i$ to $r_i$ inclusive.

The King of Berland is a family man, and for $m$ years, he has had two sons born each year. The King's children have been involved in state affairs from an early age, and at the end of each year, they check the honesty of gasoline prices. From birth, the King's children born in year $i$ are responsible for checking gasoline prices on the paths from city $a_i$ to city $b_i$ and from city $c_i$ to city $d_i$, respectively.

The check proceeds as follows: both children simultaneously start their journey from cities $a_i$ and $c_i$, respectively. The first son born in year $i$ moves along the path from city $a_i$ to city $b_i$, and the second moves from city $c_i$ to city $d_i$. The children check that the price of gasoline in city $a_i$ is the same as the price of gasoline in city $c_i$. Then they check that the price of gasoline in the second city on the path from $a_i$ to $b_i$ is the same as the price in the second city on the path from $c_i$ to $d_i$. They repeat this for the pair of third cities on their paths, and so on. Finally, they check that the price of gasoline in city $b_i$ is the same as the price of gasoline in city $d_i$. It is guaranteed that the length of the path from city $a_i$ to city $b_i$ is equal to the length of the path from city $c_i$ to city $d_i$.

Gas stations must strictly obey the laws, and therefore all gasoline price checks must not reveal any violations. Help the gas stations of Berland figure out how many ways they can set gasoline prices over $m$ years. In other words, for each $i$ from 1 to $m$, calculate how many ways prices can be set at all gas stations such that after the birth of the first $i$ pairs of the King's children, all their checks reveal no violations, and the price at any gas station is within the allowed price range. Since the number of such ways can be large, calculate the answer modulo $10^9 + 7$.

Input

The first line contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of cities in Berland.

The second line contains $(n-1)$ integers $p_2, p_3, p_4, \dots, p_n$ ($1 \le p_i \le n$), where $p_i$ denotes the number of the next city on the path from city $i$ to city 1.

Each of the following $n$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i < 10^9 + 7$), specifying the allowed price range at gas station $i$.

The next line contains a single integer $m$ ($1 \le m \le 200\,000$) — the number of years during which the King had two sons each year.

Each of the following $m$ lines contains four integers $a_i, b_i, c_i, d_i$ ($1 \le a_i, b_i, c_i, d_i \le n$), specifying the two paths on which the King's children born in year $i$ will check gasoline prices. It is guaranteed that the length of the path between cities $a_i$ and $b_i$ is equal to the length of the path between cities $c_i$ and $d_i$.

Output

Output $m$ lines, each containing one number. The number in the $i$-th line should be equal to the number of ways to set gasoline prices in all cities such that the King's children born in years up to and including $i$ do not reveal any violations in their checks. Output the numbers modulo $10^9 + 7$.

Examples

Input 1

5
1 1 2 2
2 4
1 3
1 3
2 4
4 4
4
1 1 2 2
1 2 2 1
3 4 4 3
3 4 3 5

Output 1

18
18
4
0

Input 2

8
1 2 3 4 5 8 6
3 7
2 6
3 8
5 10
5 8
2 9
3 8
6 8
4
1 3 7 6
4 1 5 7
1 7 7 1
1 8 2 7

Output 2

720
120
120
1

Note

Consider the first example.

After the birth of the first two sons, the prices in cities 1 and 2 must be equal. There are 2 ways to choose the same gasoline price for cities 1 and 2 such that it falls within the allowed price range for these cities. Thus, the total number of ways to set gasoline prices is $2 \cdot 3 \cdot 3 \cdot 1 = 18$.

The second pair of sons will check prices on paths $1-2$ and $2-1$. This means the gasoline prices in cities 1 and 2 must match, which is already satisfied. Therefore, after the birth of the second pair of sons, the answer has not changed.

The third pair of sons will check prices on paths $3-1-2-4$ and $4-2-1-3$. Then the gasoline price in city 3 must be equal to the price in city 4, and the price in city 1 must be equal to the price in city 2. The prices in cities 1 and 2 are already the same. For cities 3 and 4, there are 2 ways to choose the same gasoline price such that it falls within the allowed price range for these cities. Thus, the total number of ways to set gasoline prices is $2 \cdot 2 \cdot 1 = 6$.

The fourth pair of sons will check prices on paths $3-1-2-4$ and $3-1-2-5$. This means that the prices in cities 4 and 5 must be equal, and since the prices in cities 3 and 4 already match, the prices in cities 3, 4, and 5 must all be the same. The gasoline price in city 3 must be no more than 3, and the gasoline price in city 5 must be no less than 4. Thus, after the birth of the fourth pair of sons, there are no ways to set gasoline prices such that all checks are satisfied and the prices are within the required ranges.

Subtasks