Дано корневое дерево, где каждый узел $u$ имеет стоимость побега $t_u$, стоимость перехода к родителю $f_u$ и стоимость перехода к потомку $v$ — $g_v$.

Для каждого запроса $(u, k)$ необходимо выбрать узел $v$ так, чтобы на пути от $u$ до $v$ каждый узел находился на расстоянии от корня не менее $k$ ребер, и минимизировать сумму стоимости достижения этого узла и стоимости побега из него. У вас будет очень много запросов, для каждого из которых нужно найти минимальную общую стоимость.

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

Первая строка содержит восемь неотрицательных целых чисел $n, m, \mathrm{SA}, \mathrm{SB}, \mathrm{SC}, t_1, t_2$, где $n$ — количество узлов в дереве, а $m$ — количество запросов.

Следующая строка содержит $n$ неотрицательных целых чисел $t_i$.

Далее следуют $n - 1$ строка, каждая из которых содержит 3 целых числа $p_i, f_i, g_i$. Узлы нумеруются начиная с 2, где $p_i$ — родитель узла $i$, при этом гарантируется, что $p_i < i$.

Чтобы уменьшить объем ввода и вывода, запросы и вывод генерируются с помощью следующего кода. Обратите внимание, что массив length[] означает количество ребер от узла $i$ до корня. Вам необходимо реализовать функцию query(). Вы можете вызвать функцию solve() в основной программе после заполнения массива length[].

unsigned int SA, SB, SC;
int n, m, t1, t2;

unsigned int rng61() {
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}

long long query(int u, int k);

void solve() {
    long long lastans = 0, output = 0;
    while (m--) {
        int u = (rng61() ^ (t1 * lastans)) % n + 1;
        int k = (rng61() ^ (t1 * lastans)) % (length[u] + 1) * t2;
        lastans = query(u, k);
        output ^= lastans + m;
    }
    printf("%lld\n", output);
}

Этот код можно найти в файле lyric/template.cpp в предоставленных материалах.

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

Выведите значение переменной output, полученное в результате работы алгоритма.

Примеры

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

10 10 629647033 688064407 427303738 1 1
8 7 16 11 7 20 18 9 16 6
1 3 13
2 8 11
3 12 3
4 20 3
5 10 14
3 19 8
7 9 8
8 12 18
6 10 10

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

23

Примечание

Ниже приведены фактические запросы и ответы для данного примера:

4 2
10
1 0
8
6 2
16
10 6
6
6 4
16
6 0
16
6 2
16
6 3
16
10 0
6
1 0
8

Ограничения

Для 100% данных: $1\le n\le 3\times 10^5, 1\le m \le 6\times 10^6, 0\le t_1, t_2 \le 1$, остальные целые числа во входных данных находятся в диапазоне от $0$ до $10^9$.

Для 0% данных гарантируется $m \le 5\times 10^7$.

История

То время, похожее на сказку, промелькнуло мимо. Лань выросла, мир изменился.

Нельзя же вечно строить воздушные замки? Я не хотел этого делать, но... раз уж так вышло, я должен показать ей «новый мир».

Растерянность, изумление. Именно так она выглядела, когда увидела его впервые. Хотя мы репетировали это тысячи раз.

Взросление? Нет, я не признаю этого! Почему мир должен быть таким? Почему мир должен разбивать каждую мечту? И почему я вынужден отпустить её, чтобы она почувствовала эту «беспомощность и страх»?

Пощадите меня, я не могу притворяться довольным или высокопарно заявлять, что это и есть «взросление».

Я боюсь, что пламя войны и ненависти опалит её глаза;

Я боюсь, что грязь невежества осквернит её чистоту;

Я боюсь, что лед этого мира погасит её жар.

Она просидела в своей старой студии весь день, тупо глядя на звездное небо, которое когда-то нарисовала.

На следующий день у неё появился седой волос.

«Имеет ли искусство... хоть какой-то смысл?!»

Да, рисование — это варварство, поэзия — это варварство.

Я когда-то отвечал на её сто тысяч «почему». Но сегодня я не знаю ответа.

Или, вернее, я не знаю, как ей ответить. Пришлось опустить голову и стиснуть зубы.

«...Прости».

Тот храм рухнул. Как поток воды.

Звезды на небе тоже кровоточат.

Я должен забрать Лань и уйти из этого места.

А способ уйти можно найти только в древних рунах.

Система древних магических рун очень сложна, количество её символов неисчислимо, времени в обрез, и я не собираюсь вдаваться в детали. Я лишь скажу тебе, что есть корневое дерево, и ты можешь считать, что путь от корня до узла представляет собой строку. Руна, которую я ношу с собой, также может быть представлена узлом $u$. Каждый узел на дереве может помочь нам сбежать: если текущая руна — это узел $u$, то для активации потребуется время $t_u$. Однако руну, которую я держу, можно изменять, и это тоже требует времени. Я стираю последний символ руны, то есть перехожу из узла $u$ к его родителю, что требует времени $f_u$, или же перехожу к одному из его потомков $v$, что требует времени $g_v$.

Кроме того, есть ограничение: в любой момент времени я должен гарантировать, что длина строки не меньше $k$, где длина строки — это количество ребер от корня до текущего узла.

Я хочу попросить тебя помочь мне: как совершить побег за кратчайшее время? У меня может быть много вопросов, времени мало, пожалуйста, ответь мне как можно скорее.

Текст песни

В скучной жизни, высекая брызги,

Среди неоновых огней, становясь мечтателем,

Силуэт, идущий против света, на мгновение замирает сердце,

— «Это ты».

Среди обыденных встреч, время прорастает,

Крича в пустом классе, не сорвав голос,

Все цвета в моих глазах, самые яркие,

— «Только ты».