E. Удалите за наименьшую стоимость
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ элементов. У каждого из этих элементов есть натуральное значение $$$a_i$$$, а также натуральная стоимость удаления $$$c_i$$$. Вам необходимо удалить все элементы, кроме одного, заплатив минимально возможную стоимость. Для этого вы выполняете следующую операцию $$$n - 1$$$ раз:

За одну операцию вы выбираете два соседних элемента и удаляете наименьший из них по значению. За данную операцию вы платите стоимость удаления наименьшего по стоимости элемента среди этих двух. Если же эти два элемента равны по значению, вы можете удалить любой из них, заплатив стоимость удаления минимального из них по стоимости удаления. После удаления элементы, стоявшие правее удаляемого, смещаются влево на одну позицию, таким образом, пропусков не остается.

Также у вас есть $$$n$$$ обнулений стоимостей удаления массива. После $$$i$$$-го обнуления стоимость удаления элемента с индексом $$$p_i$$$ становится равной $$$0$$$. Гарантируется, что все $$$p_i$$$ различны. Вам необходимо для изначальных элементов решить данную задачу, а также после каждого из обнулений.

Обратите внимание: после $$$i$$$-го обнуления стоимость удаления $$$p_i$$$ элемента остаётся равной $$$0$$$ во всех последующих решаемых задачах ($$$i + 1, i + 2, \dots, n$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n + 1$$$ чисел — минимальную стоимость удаления всех элементов, кроме одного, до всех обнулений и после каждого из них.

Пример
Входные данные
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
Выходные данные
42 36 30 30 30 12 12 12 0 0 0 
3000000000 0 0 0 0
Примечание

Объяснение первого набора тестовых данных примера:

Минимальная стоимость удаления всех элементов до обнулений — 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$$$. Можно доказать, что добиться меньшей стоимости удаления всех элементов, кроме одного, невозможно.

После первого запроса обнуления первый элемент становится равен ($$$5, 0$$$). Теперь первые два элемента можно удалить не за $$$3+3$$$, а за $$$0+0$$$. Суммарная стоимость удаления всех элементов, кроме одного, теперь равна $$$36$$$.