Multiset —is a set of numbers in which there can be equal elements, and the order of the numbers does not matter. Two multisets are equal when each value occurs the same number of times. For example, the multisets {2,2,4}{2,2,4} and {2,4,2}{2,4,2} are equal, but the multisets {1,2,2}{1,2,2} and {1,1,2}{1,1,2} — are not. Problem E. Split Into Two Sets ***** In this problem, the only restriction is this: you need to split all the dominoes into two sets (each domino belongs to exactly one of the two sets) so that in each set all numbers on the dominoes of a set are different (there are no duplicate numbers within one set of dominoes). It's written in the statement, just read it. You are given two multisets 𝑎a and 𝑏b, each consisting of 𝑛n integers. In a single operation, any element of the 𝑏b multiset can be doubled or halved (rounded down). In other words, you have one of the following operations available for an element 𝑥x of the 𝑏b multiset:

• or replace 𝑥x with 𝑥⋅2x⋅2,
• or replace 𝑥x with ⌊𝑥2⌋⌊x2⌋ (round down).

Note that you cannot change the elements of the 𝑎a multiset. See if you can make the multiset 𝑏b become equal to the multiset 𝑎a in an arbitrary number of operations (maybe 00). For example, if 𝑛=4n=4, 𝑎={4,24,5,2}a={4,24,5,2}, 𝑏={4,1,6,11}b={4,1,6,11}, then the answer is yes. We can proceed as follows:

• Replace 11 with 1⋅2=21⋅2=2. We get 𝑏={4,2,6,11}b={4,2,6,11}.
• Replace 1111 with ⌊112⌋=5⌊112⌋=5. We get 𝑏={4,2,6,5}b={4,2,6,5}.
• Replace 66 with 6⋅2=126⋅2=12. We get 𝑏={4,2,12,5}b={4,2,12,5}.
• Replace 1212 with 12⋅2=2412⋅2=24. We get 𝑏={4,2,24,5}b={4,2,24,5}.
• Got equal multisets 𝑎={4,24,5,2}a={4,24,5,2} and 𝑏={4,2,24,5}b={4,2,24,5}.

Equate Multisets solution codeforces

The first line of input data contains a single integer 𝑡t (1≤𝑡≤1041≤t≤104) —the number of test cases. Each test case consists of three lines. The first line of the test case contains an integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) —the number of elements in the multisets 𝑎a and 𝑏b. The second line gives 𝑛n integers: 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎1≤𝑎2≤⋯≤𝑎𝑛≤1091≤a1≤a2≤⋯≤an≤109) —the elements of the multiset 𝑎a. Note that the elements may be equal. The third line contains 𝑛n integers: 𝑏1,𝑏2,…,𝑏𝑛b1,b2,…,bn (1≤𝑏1≤𝑏2≤⋯≤𝑏𝑛≤1091≤b1≤b2≤⋯≤bn≤109) — elements of the multiset 𝑏b. Note that the elements may be equal. It is guaranteed that the sum of 𝑛n values over all test cases does not exceed 2⋅1052⋅105.

Equate Multisets solution codeforces

For each test case, print on a separate line:

• YES if you can make the multiset 𝑏b become equal to 𝑎a,
• NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive answer). Example input Copy

5
4
2 4 5 24
1 4 6 11
3
1 4 17
4 5 31
5
4 7 10 13 14
2 14 14 26 42
5
2 2 4 4 4
28 46 62 71 98
6
1 2 10 16 64 80
20 43 60 74 85 99

output Copy

YES
NO
YES
YES
YES

Equate Multisets solution codeforces

The first example is explained in the statement. In the second example, it is impossible to get the value 3131 from the numbers of the multiset 𝑏b by available operations. In the third example, we can proceed as follows:

• Replace 22 with 2⋅2=42⋅2=4. We get 𝑏={4,14,14,26,42}b={4,14,14,26,42}.
• Replace 1414 with ⌊142⌋=7⌊142⌋=7. We get 𝑏={4,7,14,26,42}b={4,7,14,26,42}.
• Replace 2626 with ⌊262⌋=13⌊262⌋=13. We get 𝑏={4,7,14,13,42}b={4,7,14,13,42}.
• Replace 4242 with ⌊422⌋=21⌊422⌋=21. We get 𝑏={4,7,14,13,21}b={4,7,14,13,21}.
• Replace 2121 with ⌊212⌋=10⌊212⌋=10. We get 𝑏={4,7,14,13,10}b={4,7,14,13,10}.
• Got equal multisets 𝑎={4,7,10,13,14}a={4,7,10,13,14} and 𝑏={4,7,14,13,10}b={4,7,14,13,10}.