CF2176E.Remove at the lowest cost

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$).

你有 $n$ 个元素。每个元素具有一个自然数权值 $a_i$ 和一个自然数删除代价 $c_i$。你需要删除其中 $n-1$ 个元素，仅保留一个，使得总花费最小。为此，你需要执行以下操作 $n - 1$ 次：

每次操作中，你选择两个相邻的元素，并删除其中权值较小的那个；此次操作的花费为这两个元素中删除代价较小者的删除代价。若这两个元素权值相等，则你可以任选其一删除，但花费必须是二者中删除代价较小者的删除代价。删除一个元素后，其右侧所有元素向左移动一位，数组中不留空位。

此外，你还有 $n$ 次“清零操作”，用于将数组中某些元素的删除代价置为 $0$。第 $i$ 次清零操作后，下标为 $p_i$ 的元素的删除代价变为 $0$。保证所有 $p_i$ 互不相同。你需要分别求解：原始数组的最优解，以及每次清零操作之后（即共 $n$ 个修改后的数组）的最优解。

注意：第 $i$ 次清零操作后，下标为 $p_i$ 的元素的删除代价在后续所有问题（即第 $i+1, i+2, \dots, n$ 次操作后）中始终保持为 $0$。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个正整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 表示你拥有的元素个数。

每个测试用例的第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）—— 表示各元素的值。

每个测试用例的第三行包含 $n$ 个正整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le 10^9$）—— 表示各元素的移除代价。

每个测试用例的第四行包含 $n$ 个正整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）—— 表示对应顺序下移除代价被置零的元素索引。保证所有 $p_i$ 互不相同。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

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.

对于每个测试用例，输出 $n + 1$ 个数——即在所有归零操作之前，以及每次归零操作之后，移除除一个元素外所有元素的最小代价。

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$.

第一个测试用例示例的解释：

在执行任何归零操作前，移除所有元素的最小代价为 $42$。

为达到该代价，例如可以按如下方式操作：

• 移除数组的前两个元素，代价为 $3$。这两个元素为 $(5,10)$ 和 $(5, 3)$ —— $\textbf{(值, 代价)}$。此时可先移除元素 $(5,10)$，其代价为第二个元素的代价 $3$，因为第二个元素的值等于第一个元素的值。接着，可选择剩余元素 $(5,3)$ 与原数组中第三个元素（即尚未被移除的 $(8,9)$）。由于 $5 \le 8$，因此元素 $(5,3)$ 也可被移除，代价为 $3$。
• 移除数组最后两个元素 $(5,10)$ 和 $(5,3)$。它们同样以代价 $3$ 被移除。
• 剩余的数组元素可通过例如原数组中第四个元素 $(10,6)$ 来移除。该元素的值不小于所有剩余元素的值，因此所有剩余元素均可被移除，代价均为 $6$。而元素 $(10,6)$ 本身不会被移除，并将作为数组的最后一个元素保留。

所有被移除元素的总代价为 $3+3+6+6+6+6+6+3+3=42$。可以证明：在仅保留一个元素的前提下，无法实现低于 $42$ 的移除总代价。

在第一次归零请求后，第一个元素变为 $(5, 0)$。此时前两个元素不再需要花费 $3+3$，而是只需 $0+0$ 即可移除。此时移除所有元素（仅保留一个）的总代价变为 $36$。