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

Недавно Поликарп выполнил $$$n$$$ последовательно пришедших заданий.

Для каждого выполненного задания известно время $$$s_i$$$, когда оно было дано, никакие два задания не были даны в одно и то же время. Также дано время $$$f_i$$$, когда задание было выполнено. Для каждого задания есть неизвестная величина $$$d_i$$$ ($$$d_i>0$$$) — длительность выполнения задания.

Известно, что задания были выполнены в том порядке, в котором пришли. Поликарп выполнял задания следующим образом:

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

Найдите $$$d_i$$$ (длительность выполнения) каждого задания.

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

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

Далее следуют описания наборов входных данных.

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке каждого набора входных данных записано ровно $$$n$$$ целых чисел $$$s_1 < s_2 < \dots < s_n$$$ ($$$0 \le s_i \le 10^9$$$).

В третьей строке каждого набора входных данных записано ровно $$$n$$$ целых чисел $$$f_1 < f_2 < \dots < f_n$$$ ($$$s_i < f_i \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого из $$$t$$$ наборов входных данных выведите $$$n$$$ положительных целых чисел $$$d_1, d_2, \dots, d_n$$$ — длительности выполнения каждого задания.

Пример
Входные данные
4
3
0 3 7
2 10 11
2
10 15
11 16
9
12 16 90 195 1456 1569 3001 5237 19275
13 199 200 260 9100 10000 10914 91066 5735533
1
0
1000000000
Выходные данные
2 7 1 
1 1 
1 183 1 60 7644 900 914 80152 5644467 
1000000000
Примечание

Первый набор входных данных:

В начале очередь пуста: $$$[ ]$$$. И туда сразу приходит первое задание. В момент времени $$$2$$$ Поликарп заканчивает делать первое задание, соответственно, длительность выполнения первого задания — $$$2$$$. Очередь пуста, поэтому Поликарп просто ждёт.

В момент времени $$$3$$$ приходит второе задание. А в момент времени $$$7$$$ приходит третье задание, и теперь очередь выглядит так: $$$[7]$$$.

В момент времени $$$10$$$ Поликарп заканчивает делать второе задание, в итоге длительность выполнения второго задания — $$$7$$$.

И в момент времени $$$10$$$ Поликарп сразу начинает делать третье задание и заканчивает в момент времени $$$11$$$. В итоге длительность выполнения третьего задания — $$$1$$$.

Пример первого набора входных данных.