310232: CF1801E. Gasoline prices

E. Gasoline pricestime limit per test3.5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output Berland — is a huge country consisting of $n$ cities. The road network of Berland can be represented as a root tree, that is, there is only $n - 1$ road in the country, and you can get from any city to any other exactly one way, if you do not visit any city twice. For the convenience of representing the country, for each city $i$, the city $p_i$ is fixed, equal to the first city to which you need to go from the city $i$ to get to the city $1$. In other words, the city $p_i$ is equal to the ancestor of the city $i$ if the tree is hung for the city $1$.

There is one gas station in each city of Berland. Gas stations have special pricing, and for each gas station there is a fixed range of prices for which they are ready to sell gasoline. A gas station in the city with the number $i$ is ready to sell gasoline at any price from $l_i$ to $r_i$ inclusive.

The King of Berland — is an exemplary family man, and for $m$ years, two sons were born to him every year. The king's children have been involved in public affairs since early childhood, and at the end of each year they check the honesty of gasoline prices. From birth, the king's children, who are born in the year $i$, are responsible for checking gasoline prices on the ways from the city of $a_i$ to the city of $b_i$ and from the city of $c_i$ to the city of $d_i$, respectively.

The check is as follows: both children simultaneously start their journey from the cities $a_i$ and $c_i$, respectively. The first son of the king, born in the year $i$, moves along the path from the city $a_i$ to the city $b_i$, and the second  — from the city $c_i$ to the city $d_i$. Children check that the price of gasoline in the city of $a_i$ coincides with the price of gasoline in the city of $c_i$. Next, they check that the price of gasoline in the second city on the way from $a_i$ to $b_i$ coincides with the price in the second city on the way from $c_i$ to $d_i$. Then they repeat the same thing for a couple of third cities on their paths and so on. At the end, they check that the price of gasoline in the city of $b_i$ coincides with the price of gasoline in the city of $d_i$. It is guaranteed that the length of the path from the city $a_i$ to the city $b_i$ coincides with the length of the path from the city $c_i$ to the city $d_i$.

Gas stations must strictly obey the laws, and therefore all checks of gasoline prices should not reveal violations. Help Berland gas stations find out how many ways they can set gasoline prices for $m$ years. In other words, for each $i$ from $1$ to $m$, calculate how many ways you can set gasoline prices at all gas stations so that after the birth of the first $i$ pairs of the king's children, all their checks did not reveal violations, and at any gas station the price was in the acceptable price range. Since the number of such methods 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)$ numbers $p_2,\ p_3,\ p_4,\ \ldots,\ p_n$ ($1 \le p_i \le n$), where $p_i$ denotes the number of the next city on the way from city $i$ to city $1$.

In each of the following lines, two integers are given $l_i$ and $r_i$ ($1 \le l_i \le r_i < 10^9+7$), specifying the acceptable range of prices at the gas station number $i$.

The following line contains a single integer $m$ ($1 \le m \le 200\,000$) — the number of years during which two sons were born to the king.

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

Output

In $m$ lines, print one number each. The number in the $i$ line should be equal to the number of ways to set gasoline prices in all cities so that the king's children born in the years up to and including $i$ do not reveal violations in inspections. Output the numbers modulo $10^9 + 7$.

Examples

Input

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

18
18
4
0

Input

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

720
120
120
1

Note

Consider the first example.

After the birth of the first two sons, the prices in the cities of $1$ and $2$ should be equal. In total, there are 2 ways to choose the same gasoline price for the cities of $1$ and $2$ so that it falls within the acceptable price range for these cities. So, there are only ways to set gasoline prices: $2 \cdot 3 \cdot 3 \cdot 1 = 18$.

The second pair of sons will check the prices on the paths $1 - 2$ and $2 - 1$. This means that gasoline prices in the cities of $1$ and $2$ must match, which is already being done. Therefore, after the birth of the second pair of sons, the answer did not change in any way.

The third pair of sons will check the prices on the tracks $3 - 1 - 2 - 4$ and $4 - 2 - 1 - 3$. Then the price of non-gasoline in the city of $3$ should be equal to the price in the city of $4$, and the price in the city of $1$ should be equal to the price in the city of $2$. Prices in the cities of $1$ and $2$ are already the same. For the cities of $3$ and $4$, there are 2 ways to choose the same price for gasoline so that it falls within the acceptable price range for these cities. So, there are only ways to set gasoline prices: $2 \cdot 2 \cdot 1 = 4$. The fourth pair of sons will check the prices on the tracks $3 - 1 - 2 - 4$ and $3 - 1 - 2 - 5$. This means that the prices in the cities of $4$ and $5$ should be equal, and since the prices in the cities of $3$ and $4$ already coincide, then in the cities of $3$, $4$ and $5$ there should be the same price for gasoline. The price of gasoline in the city of $3$ should be no more than 3, and the price of gasoline in the city of $5$ should be no less than 4. So, after the birth of the fourth pair of sons, there are no ways to set gasoline prices so that all checks are carried out and prices are in the required ranges.

题目大意：
贝尔兰是一个由n个城市组成的大国。国家的道路网络可以表示为一棵根树，即国内只有n-1条道路，如果你不重复访问任何城市，你可以从任何城市到任何其他城市。为了方便表示国家，对于每个城市i，固定一个城市p_i，等于从城市i到城市1需要先到达的第一个城市。换句话说，如果树是挂在城市1上的，那么城市p_i等于城市i的祖先。

贝尔兰每个城市都有一个加油站。加油站有特殊的定价，每个加油站都有一个固定的价格范围，他们愿意在这个范围内销售汽油。城市i的加油站准备以任何价格从l_i到r_i（包括）出售汽油。

贝尔兰的国王是一个模范的家庭主夫，m年来，每年都会有两个儿子出生。国王的孩子们从小就参与公共事务，并在每年年底检查汽油价格的诚实性。从出生起，出生在年份i的国王的孩子负责检查从城市a_i到城市b_i和从城市c_i到城市d_i的汽油价格。

检查如下：两个孩子同时从城市a_i和c_i开始他们的旅程。国王在年份i出生的第一个儿子沿着从城市a_i到城市b_i的路径移动，第二个儿子从城市c_i到城市d_i。孩子们检查城市a_i的汽油价格是否与城市c_i的汽油价格相同。接下来，他们检查从a_i到b_i的第二座城市的汽油价格是否与从c_i到d_i的第二座城市的汽油价格相同。然后，他们对路径上的第三对城市重复同样的操作，等等。最后，他们检查城市b_i的汽油价格是否与城市d_i的汽油价格相同。保证从城市a_i到城市b_i的路径长度与从城市c_i到城市d_i的路径长度相同。

加油站必须严格遵守法律，因此所有汽油价格的检查都不应发现违规。帮助贝尔兰的加油站找出他们可以设置汽油价格的方式数。换句话说，对于每个i从1到m，计算在所有加油站设置汽油价格的方式数，以便在国王的前i对孩子出生后，他们所有的检查都没有发现违规，并且任何加油站的油价都在可接受的价格范围内。由于这样的方法可能很多，计算答案模10^9+7。

输入输出数据格式：
输入：
第一行包含一个整数n（1≤n≤200,000）——贝尔兰的城市数量。
第二行包含n-1个数p_2, p_3, p_4, ..., p_n（1≤p_i≤n），其中p_i表示从城市i到城市1需要先到达的第一个城市。
接下来每行包含两个整数l_i和r_i（1≤l_i≤r_i<10^9+7），指定编号为i的加油站的接受价格范围。
接下来一行包含一个整数m（1≤m≤200,000）——国王有两个儿子出生的年数。
接下来m行，每行四个整数a_i, b_i, c_i和d_i（1≤a_i, b_i, c_i, d_i≤n），指定国王的孩子在年份i出生时将检查汽油价格的两条路径。保证从城市a_i到城市b_i的路径长度与从城市c_i到城市d_i的路径长度相同。

输出：
m行，每行一个数。第i行的数应该等于在所有城市设置汽油价格的方式数，使得国王的孩子在年份i及以前出生时没有在检查中发现违规。输出答案模10^9+7。题目大意： 贝尔兰是一个由n个城市组成的大国。国家的道路网络可以表示为一棵根树，即国内只有n-1条道路，如果你不重复访问任何城市，你可以从任何城市到任何其他城市。为了方便表示国家，对于每个城市i，固定一个城市p_i，等于从城市i到城市1需要先到达的第一个城市。换句话说，如果树是挂在城市1上的，那么城市p_i等于城市i的祖先。 贝尔兰每个城市都有一个加油站。加油站有特殊的定价，每个加油站都有一个固定的价格范围，他们愿意在这个范围内销售汽油。城市i的加油站准备以任何价格从l_i到r_i（包括）出售汽油。 贝尔兰的国王是一个模范的家庭主夫，m年来，每年都会有两个儿子出生。国王的孩子们从小就参与公共事务，并在每年年底检查汽油价格的诚实性。从出生起，出生在年份i的国王的孩子负责检查从城市a_i到城市b_i和从城市c_i到城市d_i的汽油价格。 检查如下：两个孩子同时从城市a_i和c_i开始他们的旅程。国王在年份i出生的第一个儿子沿着从城市a_i到城市b_i的路径移动，第二个儿子从城市c_i到城市d_i。孩子们检查城市a_i的汽油价格是否与城市c_i的汽油价格相同。接下来，他们检查从a_i到b_i的第二座城市的汽油价格是否与从c_i到d_i的第二座城市的汽油价格相同。然后，他们对路径上的第三对城市重复同样的操作，等等。最后，他们检查城市b_i的汽油价格是否与城市d_i的汽油价格相同。保证从城市a_i到城市b_i的路径长度与从城市c_i到城市d_i的路径长度相同。 加油站必须严格遵守法律，因此所有汽油价格的检查都不应发现违规。帮助贝尔兰的加油站找出他们可以设置汽油价格的方式数。换句话说，对于每个i从1到m，计算在所有加油站设置汽油价格的方式数，以便在国王的前i对孩子出生后，他们所有的检查都没有发现违规，并且任何加油站的油价都在可接受的价格范围内。由于这样的方法可能很多，计算答案模10^9+7。 输入输出数据格式： 输入： 第一行包含一个整数n（1≤n≤200,000）——贝尔兰的城市数量。 第二行包含n-1个数p_2, p_3, p_4, ..., p_n（1≤p_i≤n），其中p_i表示从城市i到城市1需要先到达的第一个城市。 接下来每行包含两个整数l_i和r_i（1≤l_i≤r_i<10^9+7），指定编号为i的加油站的接受价格范围。 接下来一行包含一个整数m（1≤m≤200,000）——国王有两个儿子出生的年数。 接下来m行，每行四个整数a_i, b_i, c_i和d_i（1≤a_i, b_i, c_i, d_i≤n），指定国王的孩子在年份i出生时将检查汽油价格的两条路径。保证从城市a_i到城市b_i的路径长度与从城市c_i到城市d_i的路径长度相同。 输出： m行，每行一个数。第i行的数应该等于在所有城市设置汽油价格的方式数，使得国王的孩子在年份i及以前出生时没有在检查中发现违规。输出答案模10^9+7。