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\}$ and $\{2,4,2\}$ are equal, but the multisets $\{1,2,2\}$ and $\{1,1,2\}$ — are not.

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:

replace $x$ with $x \cdot 2$,

or replace $x$ with $\lfloor \frac{x}{2} \rfloor$ (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 $0$).

For example, if $n = 4$, $a = \{4, 24, 5, 2\}$, $b = \{4, 1, 6, 11\}$, then the answer is yes. We can proceed as follows:

Replace $1$ with $1 \cdot 2 = 2$. We get $b = \{4, 2, 6, 11\}$.

Replace $11$ with $\lfloor \frac{11}{2} \rfloor = 5$. We get $b = \{4, 2, 6, 5\}$.

Replace $6$ with $6 \cdot 2 = 12$. We get $b = \{4, 2, 12, 5\}$.

Replace $12$ with $12 \cdot 2 = 24$. We get $b = \{4, 2, 24, 5\}$.

Got equal multisets $a = \{4, 24, 5, 2\}$ and $b = \{4, 2, 24, 5\}$.


-----Input-----

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) —the number of test cases.

Each test case consists of three lines.

The first line of the test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) —the number of elements in the multisets $a$ and $b$.

The second line gives $n$ integers: $a_1, a_2, \dots, a_n$ ($1 \le a_1 \le a_2 \le \dots \le a_n \le 10^9$) —the elements of the multiset $a$. Note that the elements may be equal.

The third line contains $n$ integers: $b_1, b_2, \dots, b_n$ ($1 \le b_1 \le b_2 \le \dots \le b_n \le 10^9$) — 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 \cdot 10^5$.


-----Output-----

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).


-----Examples-----

Input
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
YES
NO
YES
YES
YES


-----Note-----

The first example is explained in the statement.

In the second example, it is impossible to get the value $31$ from the numbers of the multiset $b$ by available operations.

In the third example, we can proceed as follows:

Replace $2$ with $2 \cdot 2 = 4$. We get $b = \{4, 14, 14, 26, 42\}$.

Replace $14$ with $\lfloor \frac{14}{2} \rfloor = 7$. We get $b = \{4, 7, 14, 26, 42\}$.

Replace $26$ with $\lfloor \frac{26}{2} \rfloor = 13$. We get $b = \{4, 7, 14, 13, 42\}$.

Replace $42$ with $\lfloor \frac{42}{2} \rfloor = 21$. We get $b = \{4, 7, 14, 13, 21\}$.

Replace $21$ with $\lfloor \frac{21}{2} \rfloor = 10$. We get $b = \{4, 7, 14, 13, 10\}$.

Got equal multisets $a = \{4, 7, 10, 13, 14\}$ and $b = \{4, 7, 14, 13, 10\}$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Greedy algorithms

Number theory

Mathematics

Data structures


Solutions:
import collections
x = int(input())

def shr(a):
	while a % 2 == 0:
		a //= 2
	return a

def cal(n, ts, tt):
	d1 = collections.defaultdict(int)
	d2 = collections.defaultdict(int)
	for i in range(n):
		d1[shr(ts[i])] += 1
		d2[shr(tt[i])] += 1
	for i in d2.keys():
		t = d2[i]
		while i > 0:
			if i in d1:
				if t > d1[i]:
					t -= d1[i]
					del d1[i]
				elif t == d1[i]:
					del d1[i]
					t = 0
					break
				else:
					d1[i] -= t
					t = 0
					break
			i //= 2
		if t > 0:
			return False
	return True
for jj in range(x):
	n = int(input())
	ts = [int(i) for i in input().split(' ')]
	tt = [int(i) for i in input().split(' ')]
	if cal(n, ts, tt):
		print('YES')
	else:
		print('NO')


from functools import lru_cache

@lru_cache(None)
def get_odd(x):
	while x % 2 == 0:
		x //= 2
	return x
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	numbers = {}
	for x in a:
		numbers[get_odd(x)] = numbers.get(get_odd(x), 0) + 1
	for x in b:
		while x > 0 and x not in numbers:
			x //= 2
		if x in numbers:
			numbers[x] -= 1
			if numbers[x] == 0:
				numbers.pop(x)
	print('YES' if not len(numbers) else 'NO')


from collections import defaultdict

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a_f = defaultdict(int)
	for i in a:
		while i & 1 == 0:
			i //= 2
		a_f[i] += 1
	check = True
	for i in b:
		while i >= 1:
			if a_f[i] > 0:
				a_f[i] -= 1
				break
			i //= 2
		else:
			check = False
			break
	return 'YES' if check else 'NO'
t = int(input())
for _ in range(t):
	ans = solve()
	print(ans)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	d = dict()
	i = 0
	for x in map(int, inp().split()):
		while x % 2 == 0:
			x //= 2
		d[x] = d.get(x, 0) + 1
		i += 1
	for x in map(int, inp().split()):
		while x > 0:
			if d.get(x, 0) > 0:
				d[x] -= 1
				break
			x //= 2
		else:
			print('NO')
			return
	print('YES')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def num():
	c = int(input())
	return c

def stri():
	c = str(input())
	return c

def vector():
	c = list(map(int, input().split()))
	return c

def strvector():
	c = list(map(str, input().split()))
	return c
from collections import defaultdict
import math

def isprime(num):
	a = 2
	while a <= math.sqrt(num):
		if num % a < 1:
			return False
		a = a + 1
	return num > 1
t = num()
while t > 0:
	t -= 1
	n = num()
	a = vector()
	b = vector()
	h = {}
	for i in range(0, n):
		x = a[i]
		while x % 2 == 0:
			x = x // 2
		if x in h:
			h[x] += 1
		else:
			h[x] = 1
	for i in range(0, n):
		x = b[i]
		while x > 0:
			if x in h and h[x] != 0:
				h[x] -= 1
				break
			else:
				x = x // 2
	ans = 'YES'
	for i in h.keys():
		if h[i] != 0:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	nums = {}
	ans = 'YES'
	for i in list(map(int, input().split())):
		while not i % 2:
			i //= 2
		nums[i] = nums[i] + 1 if i in nums else 1
	for i in list(map(int, input().split())):
		while i > 0:
			if i in nums and nums[i] > 0:
				nums[i] -= 1
				break
			i //= 2
		else:
			ans = 'NO'
			break
	print(ans)


import sys
from collections import defaultdict
t = int(sys.stdin.readline().strip())
for _ in range(t):
	n = int(sys.stdin.readline().strip())
	a = list(map(int, sys.stdin.readline().split()))
	b = list(map(int, sys.stdin.readline().split()))
	da = defaultdict(int)
	for v in a:
		while v & 1 == 0:
			v >>= 1
		da[v] += 1
	res = 0
	for v in b:
		while v & 1 == 0:
			v >>= 1
		while v:
			if da[v] > 0:
				da[v] -= 1
				res += 1
				v = 0
			v >>= 1
	if res == n:
		print('YES')
	else:
		print('NO')


from collections import defaultdict, Counter
import math
import bisect
from itertools import accumulate
from math import ceil, log
from sys import stdin, stdout

def read():
	return stdin.readline().rstrip()
total = int(read())
for _ in range(total):
	s = read()
	a = [int(p) for p in input().split()]
	b = [int(p) for p in input().split()]
	c = defaultdict(lambda : 0)
	for i in a:
		while i % 2 == 0:
			i = i // 2
		c[i] += 1
	for z in b:
		if c[z] > 0:
			c[z] -= 1
		else:
			while z > 0:
				z = z // 2
				if c[z] > 0:
					c[z] -= 1
					break
	if sum(c.values()) == 0:
		print('YES')
	else:
		print('NO')


from collections import Counter

def f(s):
	x = int(s)
	while x % 2 == 0:
		x //= 2
	return x

def solve():
	n = int(input())
	m = Counter(map(f, input().split()))
	fail = 0
	for x in map(f, input().split()):
		while x > 0 and m[x] == 0:
			x //= 2
		if x == 0:
			fail = 1
		else:
			m[x] -= 1
	print('YES' if not fail else 'NO')
tn = int(input())
for _ in range(tn):
	solve()


from collections import Counter
from math import log2
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		a[i] = a[i] >> int(log2(a[i] & -a[i]))
	b.sort(reverse=True)
	d = Counter(a)
	for item in b:
		while item > 0 and d[item] == 0:
			item //= 2
		if d[item] > 0:
			d[item] -= 1
			if d[item] == 0:
				del d[item]
		else:
			break
	print('YES') if not d else print('NO')


import collections

def solve(counter):
	for x in map(int, input().split()):
		while not counter[x]:
			x //= 2
			if x == 0:
				return False
		counter[x] -= 1
	return True
for _ in range(int(input())):
	input()
	a = []
	for x in map(int, input().split()):
		while x % 2 == 0:
			x //= 2
		a.append(x)
	print('YES' if solve(collections.Counter(a)) else 'NO')


from collections import *
for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	bi = list(map(int, input().split()))
	dictt = defaultdict(int)
	for i in range(n):
		while ai[i] % 2 == 0:
			ai[i] //= 2
		dictt[ai[i]] += 1
	while bi:
		s = bi.pop()
		while s and (not dictt[s]):
			s //= 2
		if s == 0 or not dictt[s]:
			print('NO')
			break
		elif dictt[s]:
			dictt[s] -= 1
	else:
		print('YES')


from collections import defaultdict
for q in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	lis = [int(x) for x in input().split()]
	d = defaultdict(int)
	for item in arr:
		while item > 1 and item % 2 == 0:
			item //= 2
		d[item] += 1
	res = 0
	for item in lis:
		flag = 0
		while item > 0:
			if d[item]:
				flag = 1
				d[item] -= 1
				break
			item //= 2
		if flag == 0:
			res = 1
			break
	if res:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		while a[i] % 2 == 0:
			a[i] //= 2
	x = {}
	for i in a:
		if i in x:
			x[i] += 1
		else:
			x[i] = 1
	ans = 1
	for i in b:
		while not i in x or x[i] == 0:
			i //= 2
			if i == 0:
				ans = 0
				break
		if i == 0:
			break
		x[i] -= 1
	if ans == 1:
		print('YES')
	else:
		print('NO')


from collections import Counter
t = int(input())

def process_element_of_a(x):
	while x & 1 == 0:
		x >>= 1
	return x
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	set_a = Counter(map(process_element_of_a, a))
	ans = 'YES'
	for b_element in b:
		while b_element != 0:
			if set_a[b_element] > 0:
				break
			b_element >>= 1
		if set_a[b_element] > 0:
			set_a[b_element] -= 1
		else:
			ans = 'NO'
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	b = [int(x) for x in input().split(' ')]
	mp = {}
	for i in a:
		t = i
		while t % 2 == 0:
			t = t // 2
		if t not in mp.keys():
			mp[t] = 0
		mp[t] += 1
	for j in b:
		t = j
		flag = 0
		while t:
			if t in mp.keys() and mp[t] > 0:
				mp[t] -= 1
				break
			t = t // 2
	if sum(mp.values()) == 0:
		print('YES')
	else:
		print('NO')


import collections
for _ in range(int(input())):
	n = int(input())
	a = []
	for x in map(int, input().split()):
		while x % 2 == 0:
			x //= 2
		a.append(x)
	a = collections.Counter(a)
	for x in map(int, input().split()):
		while x > 0:
			if a[x]:
				a[x] -= 1
				break
			x //= 2
		else:
			print('NO')
			break
	else:
		print('YES')


from collections import Counter
MAX = int(1000000000.0) + 1
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	for i in range(len(a)):
		while a[i] % 2 == 0:
			a[i] //= 2
	c = Counter(a)
	flag = 0
	for x in b:
		flag = 0
		while x > 0:
			if x in c and c[x] > 0:
				c[x] -= 1
				flag = 1
				break
			else:
				x //= 2
		if flag == 0:
			print('NO')
			break
	if flag:
		print('YES')


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	oddValue = collections.defaultdict(int)
	for i in range(n):
		while A[i] % 2 == 0:
			A[i] = A[i] // 2
		oddValue[A[i]] += 1
	for i in range(n):
		while B[i] % 2 == 0:
			B[i] = B[i] // 2
	for i in range(n):
		ok = False
		while B[i] and ok == False:
			if oddValue[B[i]] > 0:
				oddValue[B[i]] -= 1
				ok = True
			else:
				B[i] = B[i] // 2
		if ok == False:
			print('NO')
			return
	print('YES')
	return
t = int(input())
while t != 0:
	solve()
	t -= 1


import sys
input = sys.stdin.readline
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = Counter()
	for i in a:
		while i % 2 == 0:
			i >>= 1
		d[i] += 1
	ans = 0
	for i in b:
		while not d[i]:
			i >>= 1
			if i == 0:
				ans = 1
				break
		d[i] -= 1
		if ans == 1:
			break
	print(['NO', 'YES'][ans == 0])


from collections import *

def main():
	for t in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		c = Counter()
		for i in range(n):
			while a[i] % 2 == 0:
				a[i] //= 2
			c[a[i]] += 1
		flag = True
		for i in range(n):
			while b[i] and c[b[i]] == 0:
				b[i] //= 2
			if c[b[i]] == 0:
				flag = False
				break
			c[b[i]] -= 1
		print('YES' if flag else 'NO')
main()