Ксюша — именитый эксперт в области компьютерной безопасности. Известная корпорация, разрабатывающая программное обеспечение RISC-V процессоров, наняла Ксюшу для расследования недавнего инцидента. Неопознанный горилл пробрался в продовый контур корпорации и похитил секретную разработку — массив из $$$n$$$ положительных целых чисел $$$a_1, a_2, \ldots, a_n$$$. Известно, что этот массив был упорядочен по неубыванию ($$$1 \le a_1 \le a_2 \le \ldots \le a_n$$$).
Неопознанный горилл — опытный хакер, поэтому он придумал, как обойти периметр фильтрации внутреннего трафика и извлечь массив $$$a$$$ во внешнюю сеть. Горилл дописал в конец массива $$$a$$$ элементы $$$a_1, a_1 + a_2, \ldots, a_1 + a_2 + \ldots + a_n$$$, другими словами, элементы массива префиксных сумм $$$a$$$. Затем горилл перемешал получившийся массив длины $$$2n$$$ случайным образом и назвал его $$$b$$$.
Ксюша смогла восстановить массив $$$b$$$ из логов, но чтобы оценить ущерб, нанесённый корпорации, необходимо восстановить похищенный массив $$$a$$$. Это слишком простая задача для Ксюши, поэтому её предстоит выполнить вам.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Далее следует описание наборов.
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве $$$a$$$.
Во второй строке даны $$$2 n$$$ целых числа $$$b_1, b_2, \ldots, b_{2 n}$$$ ($$$1 \le b_i \le 10^9$$$) — элементы массива $$$b$$$. Гарантируется, что существует массив $$$a$$$, соответствующий данному массиву $$$b$$$.
Также гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел — элементы массива $$$a$$$.
341 4 9 5 9 18 1 4110000 10000211021102 999 11022101 999
1 4 4 9 10000 999 11021102
В первом наборе входных данных горилл действовал так:
- Похитил массив $$$[1, 4, 4, 9]$$$;
- Дописал к массиву его префиксные суммы, получив $$$[1, 4, 4, 9, 1, 5, 9, 18]$$$;
- Перемешал полученный массив, получив $$$[1, 4, 9, 5, 9, 18, 1, 4]$$$.
