Công ty của bạn có $n$ người. Người thứ $1$ là chủ tịch, $n-1$ người còn lại là nhân viên. Nhân viên thứ $i$ (với mọi $2\le i\le n$) có đúng một sếp $p_i$ $(1\le p_i<i)$.

Hôm nay có $m$ người bất kỳ đến văn phòng làm việc. Mọi người lần lượt đến văn phòng với thứ tự bất kỳ, và không có hai người đến văn phòng tại cùng một thời điểm. Người thứ $i$ có mức độ căng thẳng $f_i$, ban đầu bằng $0$. Với mỗi $i\ge 2$:

• Nếu nhân viên $i$ đến muộn hơn sếp $p_i$ của họ thì mức độ căng thẳng $f_{p_i}$ của sếp của nhân viên này sẽ tăng lên một lượng $a_i$;

• Trái lại, nếu nhân viên $i$ đến sớm hơn sếp $p_i$ thì mức độ căng thẳng $f_i$ của nhân viên này sẽ tăng lên một lượng $b_i$.

Mức độ căng thẳng của công ty là tổng mức độ căng thẳng của tất cả $m$ người đến văn phòng: $\sum _{i=1}^n{f}_i$ Với mỗi $m$ từ $1$ đến $n$, hãy tìm mức độ căng thẳng ít nhất có thể của công ty khi có $m$ người đi làm hôm nay.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case $t$ $(1\le t\le 1000)$. Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa một số nguyên $n$ $(2\le n\le 2000)$ — số người trong công ty.

• Dòng thứ hai chứa $n-1$ số nguyên $p_2,p_3,\dots ,p_n$ $(1\le p_i<i)$ — chỉ số sếp của các nhân viên.

• Dòng thứ ba chứa $n-1$ số nguyên $a_2,a_3,\dots ,a_n$ $(0\le a_i\le {10}^5)$ — lượng tăng mức độ căng thẳng của sếp của nhân viên $i$ nếu nhân viên này đến trễ hơn sếp.

• Dòng thứ tư chứa $n-1$ số nguyên $b_2,b_3,\dots ,b_n$ $(0\le b_i\le {10}^5)$ — lượng tăng mức độ căng thẳng của nhân viên $i$ nếu sếp của nhân viên này đến trễ hơn nhân viên.

Đảm bảo rằng tổng của $n$ qua tất cả các test case không vượt quá $2000$.

Output

Với mỗi test case, in ra $n$ số nguyên, với số thứ $m$ là mức độ căng thẳng ít nhất có thể của công ty khi có $m$ người đi làm hôm nay.

Scoring

Sample Input 1

2
5
1 2 2 4
5 8 2 6
6 2 8 8
5
1 2 3 4
7 6 4 9
10 5 5 3

Sample Output 1

0 0 0 6 15 
0 0 0 7 19

Notes

• Nếu hôm nay có $m=1$ người đến văn phòng, ta có thể chọn nhân viên bất kỳ đến văn phòng, và mức độ căng thẳng của công ty sẽ là $0$ vì sẽ không có ai đến trễ hơn ai cả.

• Nếu hôm nay có $m=2$ người đến văn phòng, người thứ $5$ có thể đến đầu tiên, sau đó là người thứ $1$. Mức độ căng thẳng của công ty sẽ là $0$ vì người thứ $1$ và $5$ không có quan hệ trực tiếp với nhau.

• Nếu hôm nay có $m=3$ người đến văn phòng. Người thứ $1$, $3$ và $4$ có thể đến văn phòng theo thứ tự $1\to 3\to 4$. Mức độ căng thẳng của công ty vẫn là $0$ vì không có hai người nào đến công ty có quan hệ trực tiếp với nhau.

• Với $m=4$, ta có thể chọn thứ tự $1\to 3\to 4\to 5$. Do $4$ là sếp của $5$ và $5$ đến muộn hơn $4$, sự khó chịu của $4$ là $f_4=6$. Do đó mức độ căng thẳng của công ty là $6$.

• Với $m=5$, ta có thể chọn thứ tự $1\to 3\to 2\to 4\to 5$. Trong trường hợp này, ta có: $f=[5,2,2,6,0]$.

  Mức độ căng thẳng của công ty sẽ là $15$.