E. Remove at the lowest cost
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$n$$$ elements. Each of these elements has a natural value $$$a_i$$$ and a natural removal cost $$$c_i$$$. You need to remove all elements except one, paying the minimum possible cost. To do this, you perform the following operation $$$n - 1$$$ times:

In one operation, you choose two adjacent elements and remove the one with the smaller value. For this operation, you pay the removal cost of the least expensive element among the two. If these two elements have equal values, you can remove either of them, paying the removal cost of the minimum of the two in terms of removal cost. After removing an element, the elements to the right of the removed element shift left by one position, leaving no gaps.

You also have $$$n$$$ zeroing operations for the removal costs of the array. After the $$$i$$$-th zeroing operation, the removal cost of the element with index $$$p_i$$$ becomes $$$0$$$. It is guaranteed that all $$$p_i$$$ are distinct. You need to solve this problem for the original elements, as well as after each of the zeroing operations.

Note: After the $$$i$$$-th zeroing operation, the removal cost of the element $$$p_i$$$ remains $$$0$$$ in all subsequent problems ($$$i + 1, i + 2, \dots, n$$$).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains one natural number $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of elements you have.

The second line of each test case contains $$$n$$$ natural numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the values of the elements.

The third line of each test case contains $$$n$$$ natural numbers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$) — the removal costs of the elements.

The fourth line of each test case contains $$$n$$$ natural numbers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the indices of the elements whose removal costs are zeroed, in the corresponding order. It is guaranteed that all $$$p_i$$$ are distinct.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$n + 1$$$ numbers — the minimum cost of removing all elements except one, before all zeroings and after each of them.

Example
Input
2
10
5 5 8 10 4 3 4 10 5 5
10 3 9 6 9 8 7 8 10 3
1 10 2 9 5 6 7 4 3 8
4
1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
1 2 4 3
Output
42 36 30 30 30 12 12 12 0 0 0 
3000000000 0 0 0 0
Note

Explanation of the first test case example:

The minimum cost of removing all elements before zeroings is — 42.

To achieve this cost, you can, for example:

  • Remove the first and second elements of the array for a cost of $$$3$$$. These are the elements ($$$5,10$$$) and ($$$5, 3$$$) — $$$\textbf{(value, cost)}$$$. Then we can first remove the element ($$$5,10$$$) for the cost of the second element — $$$3$$$, since the value of the second element is equal to the value of the first. Next, we can choose the remaining element ($$$5,3$$$) and the element ($$$8,9$$$) (the third in the array before removal). The value $$$5 \le 8$$$, so the element ($$$5,3$$$) is also removed for a cost of $$$3$$$.
  • Remove the last two elements of the array ($$$5,10$$$) and ($$$5,3$$$). They are removed similarly for a cost of $$$3$$$.
  • The remaining elements of the array can be removed using, for example, the element ($$$10,6$$$) — the fourth element in the original array. The value of this element is greater than or equal to the values of all remaining elements, so all remaining elements of the array can be removed for a cost of $$$6$$$. The element ($$$10,6$$$) itself will not be removed and will remain as the last element of the array.

The total cost of all removed elements is $$$3+3+6+6+6+6+6+3+3=42$$$. It can be proven that achieving a lower cost of removing all elements except one is impossible.

After the first zeroing request, the first element becomes ($$$5, 0$$$). Now the first two elements can be removed not for $$$3+3$$$, but for $$$0+0$$$. The total cost of removing all elements except one is now $$$36$$$.