这是问题的困难版本。唯一的区别是,在这个版本中,每个人只能向不超过一个人提供糖果,并且从不超过一个人那里接收糖果。请注意,一次提交不能同时通过两个版本的问题。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
中考结束后,大牛和他的朋友们要去聚会。每个人都会带着一些糖果来。
聚会上将会有 $$$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 Yes
注意
在第一个测试用例中,第二个人给第一个人$$$1$$$糖果,那么所有人都有$$$3$$$糖果。
在第二个测试用例中,第四个人给第二个人$$$1$$$糖果,第五个人给第一个人$$$2$$$糖果,第三个人什么也不做。交换后,每个人都有 $$$3$$$ 糖果。
在第三个测试用例中,不可能所有人都拥有相同数量的糖果。
在第四个测试用例中,两个人不需要做任何事情。