E. Цены на бензин
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
Берляндия — это огромная страна, состоящая из $$$n$$$ городов. Дорожную сеть Берляндии можно представить в виде корневого дерева, то есть всего в стране $$$n - 1$$$ дорога, и от любого города можно добраться до любого другого ровно по одному пути, если не посещать никакой город дважды. Для удобства представления страны, для каждого города $$$i$$$ зафиксирован город $$$p_i$$$, равный первому городу, в который надо ехать из города $$$i$$$, чтобы добраться до города $$$1$$$. Иными словами, город $$$p_i$$$ равен предку города $$$i$$$, если дерево подвесить за город $$$1$$$.

В каждом городе Берляндии работает по одной заправке. У заправок особое ценообразование, и для каждой заправки зафиксирован диапазон цен, за которые там готовы продавать бензин. Заправка в городе с номером $$$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$$$.

Заправки должны строго подчиняться законам, а поэтому все проверки цен на бензин не должны выявлять нарушений. Помогите заправкам Берляндии выяснить, сколькими способами они могут выставлять цены на бензин в течение $$$m$$$ лет. Другими словами, для каждого $$$i$$$ от $$$1$$$ до $$$m$$$ посчитайте, сколькими способами можно выставить цены на бензин во всех заправках, чтобы после рождения первых $$$i$$$ пар детей короля, все их проверки не выявили нарушений, а на любой заправке цена находилась в допустимом диапазоне цен. Так как число таких способов может быть большим, посчитайте ответ по модулю $$$10^9 + 7$$$.

Входные данные

В первой строке дано единственное целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — число городов в Берляндии.

Во второй строке даны $$$(n - 1)$$$ чисел $$$p_2,\ p_3,\ p_4,\ \ldots,\ p_n$$$ ($$$1 \le p_i \le n$$$), где $$$p_i$$$ обозначает номер следующего города на пути из города $$$i$$$ в город $$$1$$$.

В каждой из следующих строк даны по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i < 10^9+7$$$), задающие допустимый диапазон цен на заправке номер $$$i$$$.

В следующей строке дано единственное целое число $$$m$$$ ($$$1 \le m \le 200\,000$$$) — количество лет, в течение которых у короля рождалось по два сына.

В каждой из следующих $$$m$$$ строк даны по четыре целых числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ и $$$d_i$$$ ($$$1 \le a_i, b_i, c_i, d_i \le n$$$), задающие два пути, на которых будут проверять цены на бензин дети короля, рождённые в год $$$i$$$. Гарантируется, что длина пути между городами $$$a_i$$$ и $$$b_i$$$ равна длине пути между городами $$$c_i$$$ и $$$d_i$$$.

Выходные данные

В $$$m$$$ строках выведите по одному числу. Число в $$$i$$$-й строке должно равняться числу способов выставить цены на бензин во всех городах, чтобы дети короля, рождённые в годы до $$$i$$$-го включительно не выявили нарушений в проверках. Числа выводите по модулю $$$10^9 + 7$$$.

Примеры

Входные данные
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
Выходные данные
18
18
4
0
Входные данные
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
Выходные данные
720
120
120
1
Примечание

Рассмотрим первый пример.

После рождения первых двух сыновей цены в городах $$$1$$$ и $$$2$$$ должны быть равны. Всего существует 2 способа выбрать одинаковую цену на бензин для городов $$$1$$$ и $$$2$$$, чтобы она входила в допустимый диапазон цен для этих городов. Значит, всего способов выставить цены на бензин: $$$2 \cdot 3 \cdot 3 \cdot 1 = 18$$$.

Вторая пара сыновей будет проверять цены на путях $$$1 - 2$$$ и $$$2 - 1$$$. Значит, цены на бензин в городах $$$1$$$ и $$$2$$$ должны совпадать, что уже выполняется. Поэтому после рождения второй пары сыновей ответ никак не изменился.

Третья пара сыновей будет проверять цены на путях $$$3 - 1 - 2 - 4$$$ и $$$4 - 2 - 1 - 3$$$. Тогда цена не бензин в городе $$$3$$$ должна быть равна цене в городе $$$4$$$, и цена в городе $$$1$$$ должна быть равна цене в городе $$$2$$$. Цены в городах $$$1$$$ и $$$2$$$ уже одинаковые. Для городов $$$3$$$ и $$$4$$$ существует 2 способа выбрать одинаковую цену на бензин, чтобы она входила в допустимый диапазон цен для этих городов. Значит, всего способов выставить цены на бензин: $$$2 \cdot 2 \cdot 1 = 4$$$. Четвертая пара сыновей будет проверять цены на путях $$$3 - 1 - 2 - 4$$$ и $$$3 - 1 - 2 - 5$$$. Это означает, что цены в городах $$$4$$$ и $$$5$$$ должны быть равны, и так как цены в городах $$$3$$$ и $$$4$$$ уже совпадают, то в городах $$$3$$$, $$$4$$$ и $$$5$$$ должна быть одинаковая цена на бензин. Цена на бензин в городе $$$3$$$ должна быть не больше 3, а цена на бензин в городе $$$5$$$ должна быть не меньше 4. Значит, после рождения четвёртой пары сыновей не существует способов выставить цены на бензин так, чтобы все проверки выполнялись и цены находились в необходимых диапазонах.