Để đồng bộ đèn cho lễ hội, Tinar nối ~n~ trạm điều khiển thành một cây có gốc tại trạm ~1~. Các trạm được đánh số từ ~1~ đến ~n~. Trạm ~i~ có độ khuếch đại ~a_i~ và cấp ưu tiên ~r_i~. Độ khuếch đại có thể âm, còn cấp ưu tiên của các trạm đôi một khác nhau.

Lunar muốn thử phát tín hiệu trên một tuyến đi qua trạm ~i~. Cường độ của tuyến là tổng độ khuếch đại của tất cả các trạm trên tuyến, tính cả hai đầu mút. Một tuyến hợp lệ đi theo đường đi đơn duy nhất từ trạm ~u~ đến trạm ~v~ và thỏa mãn các điều kiện sau.

• Cả ~u~ và ~v~ đều nằm trong cây con gốc ~i~.
• Đường đi từ ~u~ đến ~v~ đi qua trạm ~i~.
• Mọi trạm ~j~ trên đường đi đều có ~r_j \le r_i~.

Cây con gốc ~i~ chứa cả trạm ~i~. Lunar có thể chọn tuyến chỉ gồm trạm ~i~, tức là ~u = v = i~.

Với mỗi trạm ~i~ từ ~1~ đến ~n~, hãy tính cường độ lớn nhất của một tuyến hợp lệ đối với trạm đó.

Input

• Dòng đầu tiên chứa số nguyên ~t~ ~(1 \le t \le 10^4)~, là số bộ test.
• Dòng đầu tiên của mỗi test chứa số nguyên ~n~ ~(2 \le n \le 10^6)~, là số trạm.
• Dòng thứ hai chứa ~n - 1~ số nguyên ~p_2, p_3, \ldots, p_n~ ~(1 \le p_i \le n,\ p_i \ne i)~, trong đó ~p_i~ là cha của trạm ~i~. Các quan hệ cha tạo thành một cây có gốc tại trạm ~1~.
• Dòng thứ ba chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(-10^7 \le a_i \le 10^7)~, là độ khuếch đại của các trạm.
• Dòng thứ tư chứa ~n~ số nguyên ~r_1, r_2, \ldots, r_n~ ~(1 \le r_i \le n)~, là cấp ưu tiên của các trạm. Các giá trị ~r_i~ đôi một khác nhau.

Tổng ~n~ qua tất cả các test trong một file input không vượt quá ~5 \cdot 10^5~.

Output

Với mỗi test, in ra một dòng gồm ~n~ số nguyên. Số thứ ~i~ là cường độ lớn nhất của một tuyến hợp lệ đối với trạm ~i~.

Subtask

Bạn nhận toàn bộ số điểm của một subtask nếu chương trình vượt qua tất cả các test thuộc subtask đó.

Sample Input 1

1
6
1 1 3 3 3
5 2 -9 4 -16 36
6 1 4 2 3 5

Sample Output 1

34 2 -5 4 -16 36