給你一棵有根樹，每個節點有一個逃脫代價 $t_u$，每個節點到達自己的父親有一個代價 $f_u$，到達自己的孩子 $v$ 有一個代價 $g_v$。

每次給你一個 $u, k$，詢問從 $u$ 出發，如何選取一個節點 $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$，$i$ 從 $2$ 開始編號，$p_i$ 是 $i$ 的父親節點，保證 $p_i < i$。

為了減少輸入和輸出量，詢問和輸出可以認為由以下程式碼接管，注意下文中的 length[] 陣列意為：第 $i$ 項是 $i$ 節點到根節點經過的邊數。你要解決詢問的部分是其中的 query() 函式。你可以在主程式中處理完 length[] 陣列後呼叫一次 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);
}

你可以在下發檔案中的 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$，字串長度就是根節點到我所在節點經過的邊數。

我想請你幫我的是，如何使用最短的時間完成逃離？我可能會給你多個問題，時間緊迫，請你儘快告訴我答案。

歌詞

在無趣人生之中，撞出水花，

在煙火虹霓之中，做夢想家，

逆光而來的剪影，心跳一霎，

——「 那是你啊。」

在平淡際遇之中，時光發芽，

在空曠教室大喊，未曾聲沙，

我眼中所有色彩，最明亮的，

——「只有你啊。」