这是问题的简单版本。唯一的区别是,在这个版本中,每个人都必须给一个人糖果,并从一个人那里接收糖果。请注意,一次提交不能同时通过两个版本的问题。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
中考结束后,丹尼尔和他的朋友们要去聚会。每个人都会带着一些糖果来。
聚会上将会有 $$$n$$$ 人。最初,第 $$$i$$$ 人有 $$$a_i$$$ 糖果。聚会期间,他们会交换糖果。为此,他们将以任意顺序排列,每个人都会执行以下操作一次:
- 选择一个整数 $$$p$$$ ($$$1 \le p \le n$$$) 和一个非负整数 $$$x$$$,然后把他的 $$$2^{x}$$$ 糖果给第 $$$p$$$ 人。请注意,一个人不能给予比他目前拥有的更多的糖果(他可能以前从别人那里收到过糖果),并且他不能给自己糖果。
丹尼尔喜欢公平,所以当且仅当每个人都收到来自同一个人的糖果时,他才会感到高兴。与此同时,他的朋友汤姆喜欢平均,所以当且仅当所有的人在所有交换后都拥有相同数量的糖果时,他才会感到高兴。
确定是否存在交换糖果的方法,以便丹尼尔和汤姆在交换后都会开心。
输入
输入的第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,如果存在交换糖果以使 Daniel 和 Tom 都开心的方法,则打印“Yes”(不带引号),否则打印“No”(不带引号)。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
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
输出 #1
Yes Yes No Yes No No
注意
在第一个测试用例中:
- 第一个人给第三个人$$$1$$$糖果;
- 第二个人给第一个人$$$2$$$糖果;
- 第三个人给第二个人$$$1$$$糖果。
那么所有人都有$$$3$$$糖果。
在第二个测试用例中:
- 第五个人给第一个人$$$4$$$糖果,从现在开始第一个人有$$$5$$$糖果;
- 第一个人给第三个人$$$2$$$糖果;
- 第三个人给第五个人$$$2$$$糖果;
- 第四个人给第二个人$$$2$$$糖果;
- 第二个人给了第四个人 $$$1$$$ 糖果。
那么所有人都有$$$3$$$糖果。请注意,一开始第一个人不能给第三个人 $$$2$$$ 糖果,因为他只有 $$$a_1=1$$$ 糖果。但是第五个人给了他$$$4$$$糖果后,他就可以这样做了,因为他目前有$$$1+4=5$$$糖果。
在第三个测试用例中,不可能所有人都拥有相同数量的糖果。
在第四个测试用例中,第一个人给第二个人 $$$1024$$$ 糖果,第二个人也给第一个人 $$$1024$$$ 糖果。