题目背景

翻译自 ROI 2022 D1T2。

租赁滑雪设备的网点网络是一棵根节点为 $1$ 的树，由 $n$ 个节点组成，编号从 $1$ 到 $n$。每个节点上都有一个租赁点。位于第 $i$ 个节点的租赁点需要以 $c_i$ 卢布的价格购买设备套件。

设 $a_i$ 表示在位于节点 $i$ 子树的所有租赁点中将要购买的滑雪设备套件的总数。根据市场调研，这个值必须要满足 $l_i\le a_i\le r_i$。

题目描述

需要确定在赛季开始时每个租赁点需要购买多少套设备，以便对于网络中任何一个子树，设备套件的总数量都在市场营销人员指定的范围内，并且购买的所有设备套件的总成本最小，或是否不可能满足所有市场营销条件。

输入格式

每个测试点包含多个测试数据。第一行给出一个整数 $t$，表示测试数据的数量。接下来是 $t$ 个测试数据。

每个测试数据的第一行给出一个整数 $n$（$1\le n\le100,000$），表示树中的节点数量。

接下来一行给出 $n-1$ 个整数 $p_2,p_3,\dots,p_n$（$1\le p_i<i$），表示节点 $i$ 的父节点为节点 $p_i$。

接下来一行给出 $n$ 个整数 $c_1,\dots,c_n$（$1\le c_i\le10^9$），其中 $c_i$ 表示 $i$ 号租赁点购买一个设备套件的价格。

接下来 $n$ 行，每行给出两个整数 $l_i$ 和 $r_i$（$0\le l_i\le r_i\le10^9$），表示对位于节点编号为 $i$ 的租赁点的子树中设备套件的总数的限制。

保证所有测试用例中 $n$ 的总和不超过 $100,000$。

输出格式

对于每个测试数据，以下面的格式输出答案。

如果无法满足所有市场营销条件，请输出 -1。

否则，在第一行中输出购买整个网络的滑雪设备需要花费的最小卢布数。在第二行中，输出 $n$ 个整数 $b_i$，其中 $b_i$ 表示编号为 $i$ 的租赁点需要购买的设备套件的数量。如果有多种方式以最小的成本满足所有市场营销条件，可以输出其中一种。

2
3
1 1
3 1 2
5 7
1 2
2 4
2
1
5 5
0 1
2 2

8
0 2 3
-1

提示

样例输入的第一组数据说明：

$c_1 b_1 + c_2 b_2 + c_3 b_3 = 0 + 2 + 6 = 8$。

数据范围：

设节点 $i$ 的子树中的节点数量为 $s_i$。

全部数据范围见输入格式。