B. Отрицательные префиксы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел.

Каждая позиция массива $$$i$$$ ($$$1 \le i \le n$$$) либо заблокирована, либо разблокирована. Разрешается взять все значения на разблокированных позициях, переупорядочить их произвольным образом и вернуть их на разблокированные позиции. Не разрешается удалять значения, добавлять новые или переупорядочивать значения на заблокированных позициях.

Например, если $$$a = [-1, 1, \underline{3}, 2, \underline{-2}, 1, -4, \underline{0}]$$$, подчеркнутые позиции заблокированы. Можно получить следующие массивы:

  • $$$[-1, 1, \underline{3}, 2, \underline{-2}, 1, -4, \underline{0}]$$$;
  • $$$[-4, -1, \underline{3}, 2, \underline{-2}, 1, 1, \underline{0}]$$$;
  • $$$[1, -1, \underline{3}, 2, \underline{-2}, 1, -4, \underline{0}]$$$;
  • $$$[1, 2, \underline{3}, -1, \underline{-2}, -4, 1, \underline{0}]$$$;
  • и некоторые другие.

Пусть $$$p$$$ будет последовательностью префиксных сумм массива $$$a$$$ после переупорядочения. То есть $$$p_1 = a_1$$$, $$$p_2 = a_1 + a_2$$$, $$$p_3 = a_1 + a_2 + a_3$$$, $$$\dots$$$, $$$p_n = a_1 + a_2 + \dots + a_n$$$.

Пусть $$$k$$$ будет максимальным $$$j$$$ ($$$1 \le j \le n$$$) таким, что $$$p_j < 0$$$. Если нет таких $$$j$$$, что $$$p_j < 0$$$, то $$$k = 0$$$.

Ваша цель — переупорядочить значения таким образом, чтобы $$$k$$$ было минимально возможным.

Выведите массив $$$a$$$ после переупорядочения такой, что значение $$$k$$$ для него минимально возможно. Если существует несколько ответов, то выведите любой из них.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Затем следует описание $$$t$$$ наборов входных данных.

В первой строке каждого набора записано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество элементов в массиве $$$a$$$.

Во второй строке каждого набора записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^5 \le a_i \le 10^5$$$) — начальный массив $$$a$$$.

В третьей строке каждого набора записаны $$$n$$$ целых чисел $$$l_1, l_2, \dots, l_n$$$ ($$$0 \le l_i \le 1$$$), где $$$l_i = 0$$$ значит, что позиция $$$i$$$ разблокирована, а $$$l_i = 1$$$ значит, что позиция $$$i$$$ заблокирована.

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

Выведите $$$n$$$ целых чисел — массив $$$a$$$ после переупорядочения. Значение $$$k$$$ (максимальное такое $$$j$$$, что $$$p_j < 0$$$ (или $$$0$$$, если таких $$$j$$$ нет)) должно быть минимально возможно. Для каждой заблокированной позиции выведенное число должно совпадать с начальным. Значения на всех разблокированных позициях должны быть перестановкой начальных значений.

Если существует несколько ответов, то выведите любой из них.

Пример
Входные данные
5
3
1 3 2
0 0 0
4
2 -3 4 -1
1 1 1 1
7
-8 4 -2 -6 4 7 1
1 0 0 0 1 1 0
5
0 1 -4 6 3
0 0 0 1 1
6
-1 7 10 4 -8 -1
1 0 0 0 0 1
Выходные данные
1 2 3
2 -3 4 -1
-8 -6 1 4 4 7 -2
-4 0 1 6 3
-1 4 7 -8 10 -1
Примечание

В первом наборе входных данных можно переставить все значения как угодно, но любое переупорядочение приведет к $$$k = 0$$$. Например, для переупорядочения $$$[1, 2, 3]$$$, $$$p=[1, 3, 6]$$$, поэтому нет такого $$$j$$$, что $$$p_j < 0$$$. Таким образом, $$$k = 0$$$.

Во втором наборе не разрешается переупорядочивать элементы вообще. Поэтому массив в выводе должен совпадать с данным массивом.

В третьем наборе префиксные суммы в выведенном массиве равны $$$p = [-8, -14, -13, -9, -5, 2, 0]$$$. Максимальное $$$j$$$ равно $$$5$$$, поэтому $$$k = 5$$$. Невозможно переупорядочить так, чтобы было $$$k < 5$$$.

В четвертом наборе $$$p = [-4, -4, -3, 3, 6]$$$.

В пятом наборе $$$p = [-1, 3, 10, 2, 12, 11]$$$.