Cho cây \(n\) đỉnh có gốc là \(1\), mỗi đỉnh \(u\) được cho các số \(c_u, l_u, r_u\). Hãy tìm dãy \(b_u\) sao cho gọi \(a_u = \sum b_v\) với \(v\) là các đỉnh con của cây con gốc \(u\) (tính cả \(u\)) thì \(l_u \le a_u\le r_u\), và tổng \(\sum (b_u\times c_u)\) là nhỏ nhất.

Input

Dòng đầu chứa số \(T\) là số lượng test:

• Dòng đầu chứa số \(n\) (\(1\le n\le 10^5\))
• Dòng hai chứa \(n - 1\) số \(p_2, p_3, ..., p_n\) với \(p_u\) là cha của \(u\) (\(1 \le p_u < u\))
• Dòng ba chứa \(n\) số \(c_u\) (\(1\le c_u\le 10^9\))
• \(n\) dòng tiếp theo mỗi dòng chứa hai số \(l_u, r_u\) (\(0\le l_u\le r_u\le 10^9\))

Tổng \(n\) của tất cả các test không vượt quá \(10^5\).

Output

Với mỗi test ghi ra như sau: nếu có cách chọn dãy \(b\)

• Dòng đầu ghi ra tổng nhỏ nhất tìm được
• Dòng hai ghi ra \(n\) số là dãy \(b\) tìm được

ngược lại ghi ra \(-1\) trên một dòng.

Ví dụ:

Input 1:

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

Output 1:

8
0 2 3 
-1

Giải thích: