30633번 - Цены на бензин 서브태스크다국어

문제

Берляндия --- это огромная страна, состоящая из $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$.

서브태스크

노트

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

После рождения первых двух сыновей цены в городах 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 = 6$.

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