题目背景

暴力怎么做？暴力是不是，加边！加边！加边！然后，并查集查询！

Alice 不喜欢并查集，但是她喜欢加边。

题目描述

给定一棵 $n$ 个节点的树，节点从 $1$ 开始编号，$1$ 号节点是根节点，每条边的方向是从父亲到儿子。每个点有一个点权 $a_i$。Alice 和 Bob 在玩游戏，他们在根节点上放了一个棋子，Alice 和 Bob 轮流将棋子沿边移动，谁不能移动谁输。

已知 Alice 是先手或是后手。在游戏开始前，Alice 可以在树上添加一条有向边 $u\to v$（$1\le u,v\le n$），然后和 Bob 在形成的图上玩这个游戏，她希望自己存在必胜策略。她也可以选择不加边。如果无法决出胜负则不算胜利。

给定正整数 $A,B$，Alice 添加边 $u\to v$ 的代价是 $A\times a_u+B\times a_v$。选择不加边的代价为 $0$。

Alice 要最小化她的代价。如果她怎么加边都不满足要求，输出 $-1$。

Alice 会做出 $T$ 次询问，你需要对每个询问输出答案。

输入格式

本题有多组数据。

第一行输入一个正整数 $T$，表示询问次数。

对于每组询问，第一行输入四个正整数 $n,t,A,B$，其中 $n$ 表示树的节点数，$t$ 表示操作顺序，$t=0$ 表示 Alice 先手，$t=1$ 表示 Alice 后手。

接下来一行 $n-1$ 个正整数，第 $i$ 个数表示节点 $i+1$ 的父亲编号 $f_{i+1}$。

接下来一行 $n$ 个正整数，第 $i$ 个表示 $a_i$ 的值。

输出格式

对于每个询问，输出一行一个整数，表示 Alice 的最小代价。如果她怎么加边都不满足要求，输出 $-1$。

4
3 1 2 7
1 1
4 3 2
3 1 2 7
1 2
4 3 2
3 0 2 7
1 2
4 3 2
9 1 523 182
1 1 2 2 2 3 3 1
3 23 18 293 162 483 574 384 109

-1
0
22
86491

提示

【样例解释】

在第 $1$ 组询问中，Alice 是后手，她无论怎么添加边都无法拥有必胜策略，所以输出 $-1$。
在第 $2$ 组询问中，Alice 是后手，她不需要添加边就拥有必胜策略，所以代价为 $0$。
在第 $3$ 组询问中，Alice 是先手，她只能添加一条 $1\to 3$ 的边使自己必胜，此时代价为 $2\times 4+7\times 2=22$。
在第 $4$ 组询问中，Alice 是后手，她可以添加一条 $9\to 5$ 的边使自己必胜，此时代价为 $523\times 109+182\times 162=86491$。她还有其他使自己必胜的方法，但是可以发现 $86491$ 是最小代价。

【数据范围】

本题采用捆绑测试。

• Subtask 1（10 points）：$n\le 10$，$T=1$；
• Subtask 2（15 points）：$\sum n\le 200$；
• Subtask 3（15 points）：$\sum n\le 2000$；
• Subtask 4（10 points）：$f_i=i-1$；
• Subtask 5（10 points）：$f_i=1$；
• Subtask 6（20 points）：$\sum n\le 5\times 10^5$；
• Subtask 7（20 points）：无特殊限制。

对于 $100\%$ 的数据，满足 $1\le T\le 2\times10^3$，$2\le n\le2\times 10^5$，$\sum n\le 5\times 10^6$，$1\le a_i,A,B\le 10^9$，$f_i<i$，$t\in\{0,1\}$。

【提示】

请使用较快的输入方式。