310671: CF1868B1. Candy Party (Easy Version)

B1. Candy Party (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the easy version of the problem. The only difference is that in this version everyone must give candies to exactly one person and receive candies from exactly 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 exactly 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 exactly 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
No

Note

In the first test case:

• The first person gives $1$ candy to the third person;
• The second person gives $2$ candies to the first person;
• The third person gives $1$ candy to the second person.

Then all people have $3$ candies.

In the second test case:

• The fifth person gives $4$ candies to the first person, from now on the first person has $5$ candies;
• The first person gives $2$ candies to the third person;
• The third person gives $2$ candies to the fifth person;
• The fourth person gives $2$ candies to the second person;
• The second person gives $1$ candy to the fourth person.

Then all people have $3$ candies. Note that at first the first person cannot give $2$ candies to the third person, since he only has $a_1=1$ candy. But after the fifth person gives him $4$ candies, he can do this, because he currently has $1+4=5$ 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 first person gives $1024$ candies to the second person, and the second person gives $1024$ candies to the first person as well.

题目大意：
这是一个关于分配糖果的问题。有n个人参加聚会，每个人初始时拥有一些糖果。在聚会期间，他们将以任意顺序排队，并且每个人将精确地执行以下操作一次：选择一个整数p（1≤p≤n）和一个非负整数x，然后给他2^x个糖果给第p个人。注意，一个人不能给出比他当前拥有的更多的糖果（他可能在此之前从其他人那里收到糖果），并且他不能给自己糖果。如果每个人从精确一个人那里收到糖果，并且所有人交换糖果后拥有相同数量的糖果，则输出"Yes"，否则输出"No"。

输入数据格式：
第一行包含一个整数t（1≤t≤1000），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（2≤n≤2×10^5），表示聚会的人数。
每个测试用例的第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9），表示每个人拥有的糖果数量。

输出数据格式：
对于每个测试用例，如果存在一种交换糖果的方式使得每个人都从精确一个人那里收到糖果，并且所有人交换糖果后拥有相同数量的糖果，则输出"Yes"，否则输出"No"。输出大小写不敏感。题目大意： 这是一个关于分配糖果的问题。有n个人参加聚会，每个人初始时拥有一些糖果。在聚会期间，他们将以任意顺序排队，并且每个人将精确地执行以下操作一次：选择一个整数p（1≤p≤n）和一个非负整数x，然后给他2^x个糖果给第p个人。注意，一个人不能给出比他当前拥有的更多的糖果（他可能在此之前从其他人那里收到糖果），并且他不能给自己糖果。如果每个人从精确一个人那里收到糖果，并且所有人交换糖果后拥有相同数量的糖果，则输出"Yes"，否则输出"No"。 输入数据格式： 第一行包含一个整数t（1≤t≤1000），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（2≤n≤2×10^5），表示聚会的人数。 每个测试用例的第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9），表示每个人拥有的糖果数量。 输出数据格式： 对于每个测试用例，如果存在一种交换糖果的方式使得每个人都从精确一个人那里收到糖果，并且所有人交换糖果后拥有相同数量的糖果，则输出"Yes"，否则输出"No"。输出大小写不敏感。