C. Собеседование на работу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп открывает свою IT-компанию. Он хочет нанять $$$n$$$ программистов и $$$m$$$ тестировщиков.

На собеседование придут $$$n+m+1$$$ кандидатов, пронумерованных от $$$1$$$ до $$$n+m+1$$$ в хронологическом порядке их прибытия. У $$$i$$$-го кандидата есть навык программирования $$$a_i$$$ и навык тестирования $$$b_i$$$ (навык программирования человека отличается от его навыка тестирования). Навык команды — это сумма навыков программирования всех нанятых в качестве программистов и сумма навыков тестирования всех нанятых в качестве тестировщиков.

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

Ваша задача — для каждого кандидата рассчитать навык команды, если на собеседование придут все, кроме него. Обратите внимание, что это означает, что придут ровно $$$n+m$$$ кандидатов, и все $$$n+m$$$ мест в компании будут заняты.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из трех строк:

  • первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$0 \le n, m \le 2 \cdot 10^5$$$; $$$2 \le n + m + 1 \le 2 \cdot 10^5$$$) — количество программистов и количество тестировщиков, которых Монокарп хочет нанять, соответственно;
  • вторая строка содержит $$$n + m + 1$$$ целых чисел $$$a_1, a_2, \dots, a_{n+m+1}$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — навык программирования $$$i$$$-го кандидата;
  • третья строка содержит $$$n + m + 1$$$ целых чисел $$$b_1, b_2, \dots, b_{n+m+1}$$$ ($$$1 \le b_i \le 10^9$$$; $$$b_i \ne a_i$$$), где $$$b_i$$$ — навык тестирования $$$i$$$-го кандидата.

Дополнительное ограничение на входные данные: сумма $$$(n + m + 1)$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$n + m + 1$$$ целых чисел, где $$$i$$$-е число должно быть равно навыку команды, если на собеседование придут все, кроме $$$i$$$-го кандидата.

Пример
Входные данные
4
1 0
2 1
1 2
0 2
4 5 5
5 4 1
1 2
2 1 5 4
5 2 3 1
3 1
4 3 3 4 1
5 5 4 5 2
Выходные данные
1 2 
5 6 9 
8 11 11 12 
13 13 13 12 15
Примечание

Рассмотрим третий набор входных данных в примере:

  • если $$$1$$$-й кандидат не придет, $$$2$$$-го кандидата возьмут тестировщиком, $$$3$$$-го кандидата возьмут программистом, $$$4$$$-го кандидата возьмут тестировщиком. Суммарный навык команды будет $$$2 + 5 + 1 = 8$$$;
  • если $$$2$$$-й кандидат не придет, $$$1$$$-го кандидата возьмут тестировщиком, $$$3$$$-го кандидата возьмут программистом, $$$4$$$-го кандидата возьмут тестировщиком. Суммарный навык команды будет $$$5 + 5 + 1 = 11$$$;
  • если $$$3$$$-й кандидат не придет, $$$1$$$-го кандидата возьмут тестировщиком, $$$2$$$-го кандидата возьмут тестировщиком, $$$4$$$-го кандидата возьмут программистом. Суммарный навык команды будет $$$5 + 2 + 4 = 11$$$;
  • если $$$4$$$-й кандидат не придет, $$$1$$$-го кандидата возьмут тестировщиком, $$$2$$$-го кандидата возьмут тестировщиком, $$$3$$$-го кандидата возьмут программистом. Суммарный навык команды будет $$$5 + 2 + 5 = 12$$$.