给你一颗有根树，每个节点有一个逃脱代价 $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

样例 1 解释

下面是本样例的实际每次询问和答案：

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$，字符串长度就是根节点到我所在节点经过的边数。

我想请你帮我的是，如何使用最短的时间完成逃离？我可能会给你多个问题，时间紧迫，请你尽快告诉我答案。

歌词

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

在烟火虹霓之中，做梦想家，

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

——“ 那是你啊。”

在平淡际遇之中，时光发芽，

在空旷教室大喊，未曾声沙，

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

——“只有你啊。”