B2. Конфетная вечеринка (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие состоит в том, что в этой версии каждый должен дать конфеты не более чем одному человеку и получить конфеты не более чем от одного человека. Обратите внимание, что посылка не может пройти обе версии задачи одновременно. Вы можете делать взломы, только если обе версии задачи решены.

После экзамена Daniel и его друзья собираются устроить вечеринку. Все придут с конфетами.

На вечеринке будут присутствовать $$$n$$$ человек. Изначально у $$$i$$$-го человека есть $$$a_i$$$ конфет. Во время вечеринки они будут обмениваться конфетами. Для этого они выстроятся в произвольном порядке и каждый из них сделает следующее не более одного раза:

  • Выберет целое число $$$p$$$ ($$$1 \le p \le n$$$) и неотрицательное целое число $$$x$$$, затем даст $$$2^{x}$$$ конфет $$$p$$$-му человеку. Заметим, что человек не может отдать больше конфет, чем у него есть в данный момент (он мог получить конфеты от кого-то другого), и он не может отдать конфеты самому себе.

Daniel любит справедливость, поэтому он будет счастлив тогда и только тогда, когда каждый получит конфеты от не более чем одного человека. В то же время его друг Tom любит среднее, поэтому он будет счастлив тогда и только тогда, когда у всех людей будет одинаковое количество конфет после всех обменов.

Определите, существует ли способ обменяться конфетами так, чтобы Daniel и Tom были счастливы после обменов.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$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$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите «Yes» (без кавычек), если существует способ обменяться конфетами так, чтобы Daniel и Tom были счастливы, и выведите «No» (без кавычек) в противном случае.

Вы можете вывести ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительный ответ.

Пример
Входные данные
6
3
2 4 3
5
1 2 3 4 5
6
1 4 7 1 5 4
2
20092043 20092043
12
9 9 8 2 4 4 3 5 1 1 1 1
6
2 12 7 16 11 12
Выходные данные
Yes
Yes
No
Yes
No
Yes
Примечание

В первом наборе входных данных второй человек даёт $$$1$$$ конфету первому человеку, поэтому у всех людей есть по $$$3$$$ конфеты.

Во втором наборе входных данных четвёртый человек даёт $$$1$$$ конфету второму человеку, пятый человек даёт $$$2$$$ конфеты первому человеку, третий человек ничего не делает. После всех обменов у каждого есть по $$$3$$$ конфеты.

В третьем наборе входных данных невозможно сделать так, чтобы у всех людей было одинаковое количество конфет.

В четвёртом наборе входных данных двум людям не нужно ничего делать.