310681: CF1869D2. Candy Party (Hard Version)

D2. Candy Party (Hard Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the hard version of the problem. The only difference is that in this version everyone must give candies to no more than one person and receive candies from no more than one person. Note that a submission cannot pass both versions of the problem at the same time. You can make hacks only if both versions of the problem are solved.

After Zhongkao examination, Daniel and his friends are going to have a party. Everyone will come with some candies.

There will be $n$ people at the party. Initially, the $i$-th person has $a_i$ candies. During the party, they will swap their candies. To do this, they will line up in an arbitrary order and everyone will do the following no more than once:

• Choose an integer $p$ ($1 \le p \le n$) and a non-negative integer $x$, then give his $2^{x}$ candies to the $p$-th person. Note that one cannot give more candies than currently he has (he might receive candies from someone else before) and he cannot give candies to himself.

Daniel likes fairness, so he will be happy if and only if everyone receives candies from no more than one person. Meanwhile, his friend Tom likes average, so he will be happy if and only if all the people have the same number of candies after all swaps.

Determine whether there exists a way to swap candies, so that both Daniel and Tom will be happy after the swaps.

Input

The first line of input contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 2\cdot 10^5$) — the number of people at the party.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$) — the number of candies each person has.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, print "Yes" (without quotes) if exists a way to swap candies to make both Daniel and Tom happy, and print "No" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

ExampleInput

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

Output

Yes
Yes
No
Yes
No
Yes

Note

In the first test case, the second person gives $1$ candy to the first person, then all people have $3$ candies.

In the second test case, the fourth person gives $1$ candy to the second person, the fifth person gives $2$ candies to the first person, the third person does nothing. And after the swaps everyone has $3$ candies.

In the third test case, it's impossible for all people to have the same number of candies.

In the fourth test case, the two people do not need to do anything.

题目大意：
这个题目是“糖果派对”的困难版本。在这个版本中，每个人只能给不超过一个人糖果，并且也只能从不超过一个人那里获得糖果。注意，一个提交不能同时通过这个问题的两个版本。只有当两个版本的问题都解决了，你才能进行攻击。

丹尼尔和他的朋友们中考后要开一个派对，每个人都将带来一些糖果。派对上将有n个人，最初第i个人有a_i个糖果。在派对期间，他们将交换他们的糖果。为此，他们会任意排列，每个人最多做一次以下事情：

选择一个整数p（1≤p≤n）和一个非负整数x，然后给他2^x个糖果给第p个人。注意，一个人不能给出比他当前拥有的更多的糖果（他可能在之前从别人那里收到糖果），并且他不能给自己糖果。

丹尼尔喜欢公平，所以只有当每个人都从不超过一个人那里得到糖果时，他才会高兴。同时，他的朋友汤姆喜欢平均，所以只有当所有人交换糖果后都有相同数量的糖果时，他才会高兴。

确定是否存在一种交换糖果的方式，使得丹尼尔和汤姆在交换后都会感到高兴。

输入数据格式：
输入的第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数n（2≤n≤2×10^5）——派对上的人数。

每个测试用例的第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9）——每个人拥有的糖果数量。

保证所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，如果存在一种交换糖果的方式，使得丹尼尔和汤姆都会感到高兴，则打印"Yes"（不带引号），否则打印"No"（不带引号）。

你可以以任何大小写输出答案。例如，字符串"yEs"、"yes"、"Yes"和"YES"都将被视为肯定的回答。题目大意： 这个题目是“糖果派对”的困难版本。在这个版本中，每个人只能给不超过一个人糖果，并且也只能从不超过一个人那里获得糖果。注意，一个提交不能同时通过这个问题的两个版本。只有当两个版本的问题都解决了，你才能进行攻击。 丹尼尔和他的朋友们中考后要开一个派对，每个人都将带来一些糖果。派对上将有n个人，最初第i个人有a_i个糖果。在派对期间，他们将交换他们的糖果。为此，他们会任意排列，每个人最多做一次以下事情： 选择一个整数p（1≤p≤n）和一个非负整数x，然后给他2^x个糖果给第p个人。注意，一个人不能给出比他当前拥有的更多的糖果（他可能在之前从别人那里收到糖果），并且他不能给自己糖果。 丹尼尔喜欢公平，所以只有当每个人都从不超过一个人那里得到糖果时，他才会高兴。同时，他的朋友汤姆喜欢平均，所以只有当所有人交换糖果后都有相同数量的糖果时，他才会高兴。 确定是否存在一种交换糖果的方式，使得丹尼尔和汤姆在交换后都会感到高兴。 输入数据格式： 输入的第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（2≤n≤2×10^5）——派对上的人数。 每个测试用例的第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9）——每个人拥有的糖果数量。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，如果存在一种交换糖果的方式，使得丹尼尔和汤姆都会感到高兴，则打印"Yes"（不带引号），否则打印"No"（不带引号）。 你可以以任何大小写输出答案。例如，字符串"yEs"、"yes"、"Yes"和"YES"都将被视为肯定的回答。