Nhân dịp năm mới Nhật Trường đã đặt ra cho mình mục tiêu lên rank cao thủ đấu trường chân lý nhưng có vẻ là quá khó với anh ấy. Sau một khoảng thời gian cày cuốc lên rank xuống rank Trường đã quá mệt mỗi . Nên Nhật Trường quyết định nhìn lại bản thân và cải thiện mình, trước hết anh ấy liệt kê ra những thói xấu của mình và xem xét cải thiện dần (lưu ý rằng việc chơi tft không được tính là một thói xâu).

Trường liệt kê ra ~n~ thói quen của mình. Mỗi thói quen có:

• Một giá trị ~a_i~ thể hiện mức độ ảnh hưởng.
• Một chi phí loại bỏ ~c_i~ thể hiện mức độ khó khăn khi từ bỏ thói quen đó.

• Mục tiêu của Trường là loại bỏ tất cả thói quen, chỉ giữ lại đúng một thói quen duy nhất và hy vọng thói quen đó là thói quen chơi tft, sao cho tổng chi phí phải trả là nhỏ nhất có thể. Cụ thể quy tắc loại bỏ của anh ấy như sau, trường sẽ thực hiện đúng ~n - 1~ lần thao tác

• Ở mỗi lần, Trường chọn hai thói quen kề nhau.

• Trong hai thói quen đó, Trường sẽ loại bỏ thói quen có giá trị nhỏ hơn.
• Chi phí phải trả cho thao tác này là chi phí nhỏ hơn trong hai chi phí loại bỏ của hai thói quen được chọn.
• Nếu hai thói quen có giá trị bằng nhau, Trường có thể loại bỏ một trong hai, nhưng vẫn phải trả chi phí bằng chi phí nhỏ hơn trong hai chi phí loại bỏ.
• Sau khi loại bỏ một thói quen, các thói quen phía sau sẽ dịch trái lại để không tạo khoảng trống.

Biêt rằng trong năm mới để chi ân sự nổ lực của Trường , anh ấy sẽ có thêm ~n~ cơ hội đặc biệt. Với mỗi cơ hội đặt biệt thứ ~i~, chi phí loại bỏ của thói quen có chỉ số ~p_i~ sẽ trở thành ~0~. Lưu ý các chỉ số ~p_i~ là khác nhau và sau khi một chi phí đã trở thành ~0~, nó sẽ giữ nguyên bằng 0 trong tất cả các lần sau.

Vì quá mệt sau chuỗi ngày leo rank nên ấy Trường muốn xác định thật nhanh tổng chi phí tối ưu để loại bỏ các thói quen xấu trong các trường hợp sau:

• Danh sách ban đầu khi chưa áp dụng cơ hội đặc biệt.
• Sau mỗi lần nhận được một cơ hội mới.

Yêu cầu: Hãy tính chi phí nhỏ nhất để đưa danh sách về duy nhất một thói quen tại mỗi thời điểm nêu trên.

Input

• Dòng đầu tiên chứa số nguyên ~t~ là số bộ test với ~(1 \le t \le 10^4)~
• Dòng đầu tiên của mỗi test chứa số nguyên ~n~ với ~(2 \le n \le 2 \cdot 10^5)~.
• Dòng thứ hai của mỗi test chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ với ~(1 \le a_i \le 10^9)~.
• Dòng thứ ba của mỗi test chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~ với ~(1 \le c_i \le 10^9)~.
• Dòng thứ tư của mỗi test chứa ~n~ số nguyên ~p_1, p_2, \dots, p_n~ ~(1 \le p_i \le n)~, các giá trị ~p_i~ đôi một khác nhau.

Đảm bảo tổng ~n~ của tất cả các test không vượt quá ~2 \cdot 10^5~.

Output

Với mỗi test, in ra ~n + 1~ số nguyên:

• Chi phí nhỏ nhất ban đầu (chưa có ưu đãi).
• Và sau mỗi lần ưu đãi, theo thứ tự.

Subtask

Sample Input 1

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

Sample Output 1

6 4 0 0 0 0 0 

Giải thích

Ban đầu ta có:

• a = [7, 9, 5, 7, 4, 6]
• c = [9, 2, 4, 1, 8, 9]

Ta có thể thực hiện các thao tác loại bỏ như sau:

• Chọn cặp (7, 9) → loại bỏ 7, chi phí min(9,2)=2.
• Chọn cặp (5, 7) → loại bỏ 5, chi phí min(4,1)=1.
• Chọn cặp (7, 4) → loại bỏ 4, chi phí min(1,8)=1.
• Chọn cặp (7, 6) → loại bỏ 6, chi phí min(1,9)=1.
• Chọn cặp (9, 7) → loại bỏ 7, chi phí min(2,1)=1.

Tổng chi phí phải trả là:

[ 2 + 1 + 1 + 1 + 1 = 6 ]

Do đó chi phí nhỏ nhất ban đầu là 6.

Sau ưu đãi thứ nhất p₁ = 1, chi phí c₁ trở thành 0. Khi đó thao tác đầu tiên (7, 9) có chi phí min(0,2)=0, các bước còn lại giữ nguyên nên tổng chi phí giảm còn 4.

Sau ưu đãi thứ hai p₂ = 2, ta có thêm c₂ = 0. Nhờ đó ta có thể sắp xếp các thao tác sao cho mỗi lần loại bỏ đều có chi phí bằng 0, nên tổng chi phí tối thiểu trở thành 0.

Các ưu đãi tiếp theo chỉ làm thêm nhiều chi phí bằng 0, vì vậy kết quả vẫn giữ nguyên.