Dano drzewo ukorzenione, w którym każdy węzeł ma koszt ucieczki $t_u$, koszt przejścia do ojca $f_u$ oraz koszt przejścia do dziecka $v$ wynoszący $g_v$.

Dla każdego zapytania $(u, k)$ należy wybrać węzeł $v$ w taki sposób, aby na ścieżce z $u$ do $v$ każdy wierzchołek znajdował się w odległości od korzenia nie mniejszej niż $k$, a suma kosztu dotarcia do tego punktu oraz kosztu ucieczki z niego była jak najmniejsza. Masz do obsłużenia bardzo wiele zapytań; dla każdego z nich należy podać minimalny całkowity koszt.

Wejście

Pierwsza linia zawiera osiem nieujemnych liczb całkowitych $n, m, \mathrm{SA}, \mathrm{SB}, \mathrm{SC}, t_1, t_2$, gdzie $n$ oznacza liczbę węzłów drzewa, a $m$ liczbę zapytań.

W następnej linii znajduje się $n$ nieujemnych liczb całkowitych $t_i$.

Kolejne $n - 1$ linii zawiera po $3$ liczby całkowite $p_i, f_i, g_i$, gdzie $i$ jest numerowane od $2$, $p_i$ to ojciec węzła $i$, przy czym zachodzi $p_i < i$.

Aby ograniczyć ilość danych wejściowych i wyjściowych, zapytania i wyniki są generowane przez poniższy kod. Tablica length[] przechowuje liczbę krawędzi na ścieżce od węzła $i$ do korzenia. Twoim zadaniem jest zaimplementowanie funkcji query(). Po przetworzeniu tablicy length[] w programie głównym, należy wywołać funkcję solve().

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);
}

Kod ten znajduje się w pliku lyric/template.cpp w załączonych materiałach.

Wyjście

Wynik powinien być zgodny z wartością zmiennej output z powyższego kodu.

Przykład

Wejście 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

Wyjście 1

23

Uwagi

Poniżej przedstawiono rzeczywiste zapytania i odpowiedzi dla tego przykładu:

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

Ograniczenia

Dla $100\%$ danych: $1\le n\le 3\times 10^5, 1\le m \le 6\times 10^6, 0\le t_1, t_2 \le 1$, pozostałe liczby całkowite mieszczą się w zakresie od $0$ do $10^9$.

Dla $0\%$ danych: gwarantowane $m \le 5\times 10^7$.