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. Значит, после рождения четвёртой пары сыновей не существует способов выставить цены на бензин так, чтобы все проверки выполнялись и цены находились в необходимых диапазонах.