Fishingprince is playing with an array $[a_1,a_2,\dots,a_n]$. He also has a magic number $m$.

He can do the following two operations on it:

Select $1\le i\le n$ such that $a_i$ is divisible by $m$ (that is, there exists an integer $t$ such that $m \cdot t = a_i$). Replace $a_i$ with $m$ copies of $\frac{a_i}{m}$. The order of the other elements doesn't change. For example, when $m=2$ and $a=[2,3]$ and $i=1$, $a$ changes into $[1,1,3]$.

Select $1\le i\le n-m+1$ such that $a_i=a_{i+1}=\dots=a_{i+m-1}$. Replace these $m$ elements with a single $m \cdot a_i$. The order of the other elements doesn't change. For example, when $m=2$ and $a=[3,2,2,3]$ and $i=2$, $a$ changes into $[3,4,3]$.

Note that the array length might change during the process. The value of $n$ above is defined as the current length of the array (might differ from the $n$ in the input).

Fishingprince has another array $[b_1,b_2,\dots,b_k]$. Please determine if he can turn $a$ into $b$ using any number (possibly zero) of operations.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1\le n\le 5\cdot 10^4$, $2\le m\le 10^9$).

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 third line of each test case contains one integer $k$ ($1\le k\le 5\cdot 10^4$).

The fourth line of each test case contains $k$ integers $b_1,b_2,\ldots,b_k$ ($1\le b_i\le 10^9$).

It is guaranteed that the sum of $n+k$ over all test cases does not exceed $2\cdot 10^5$.


-----Output-----

For each testcase, print Yes if it is possible to turn $a$ into $b$, and No otherwise. You can print each letter in any case (upper or lower).


-----Examples-----

Input
5
5 2
1 2 2 4 2
4
1 4 4 2
6 2
1 2 2 8 2 2
2
1 16
8 3
3 3 3 3 3 3 3 3
4
6 6 6 6
8 3
3 9 6 3 12 12 36 12
16
9 3 2 2 2 3 4 12 4 12 4 12 4 12 4 4
8 3
3 9 6 3 12 12 36 12
7
12 2 4 3 4 12 56
Output
Yes
Yes
No
Yes
No


-----Note-----

In the first test case of the sample, we can do the second operation with $i=2$: $[1,{2,2},4,2]\to [1,{4},4,2]$.

In the second testcase of the sample, we can:

do the second operation with $i=2$: $[1,{2,2},8,2,2]\to [1,{4},8,2,2]$.

do the second operation with $i=4$: $[1,4,8,{2,2}]\to [1,4,8,{4}]$.

do the first operation with $i=3$: $[1,4,{8},4]\to [1,4,{4,4},4]$.

do the second operation with $i=2$: $[1,{4,4},4,4]\to [1,{8},4,4]$.

do the second operation with $i=3$: $[1,8,{4,4}]\to [1,8,{8}]$.

do the second operation with $i=2$: $[1,{8,8}]\to [1,{16}]$.

Source: codeforces | Difficulty: MEDIUM
Tags: Mathematics

Greedy algorithms

Implementation

Constructive algorithms


Solutions:
def newList(nums, m, newnums):
	for num in nums:
		x = num
		while x % m == 0:
			x //= m
		if not newnums or newnums[-1][0] != x:
			newnums.append([x, num // x])
		else:
			newnums[-1][1] += num // x
	return newnums
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	nums = list(map(int, input().split()))
	k = int(input())
	nums1 = list(map(int, input().split()))
	if newList(nums, m, []) == newList(nums1, m, []):
		print('Yes')
	else:
		print('No')


def expand(a, m):
	b = []
	for x in a:
		t = x
		while t % m == 0:
			t //= m
		if b and b[-1][0] == t:
			b[-1][1] += x // t
		else:
			b.append([t, x // t])
	return b
for _ in range(int(input())):
	(_, m) = map(int, input().split())
	a = map(int, input().split())
	input()
	b = map(int, input().split())
	print('Yes' if expand(a, m) == expand(b, m) else 'No')


def int_input():
	a = int(input())
	return a

def int_list_input():
	a = list(map(int, input().split()))
	return a

def expand(a, m):
	b = []
	for i in a:
		x = i
		while x % m == 0:
			x = x // m
		if b and b[-1][0] == x:
			b[-1][1] += i // x
		else:
			b.append([x, i // x])
	return b

def solve():
	(n, m) = int_list_input()
	a = int_list_input()
	k = int_input()
	b = int_list_input()
	print('Yes' if expand(a, m) == expand(b, m) else 'No')
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	fl = True
	(pointer_n, pointer_k) = (0, 0)
	while pointer_n < n and pointer_k < k:
		if a[pointer_n] == b[pointer_k]:
			pointer_n += 1
			pointer_k += 1
		else:
			(sum_n, sum_k) = (0, 0)
			curr = a[pointer_n]
			while curr % m == 0:
				curr //= m
			rem = curr
			while pointer_n < n:
				curr = a[pointer_n]
				while curr % m == 0:
					curr //= m
				if curr == rem:
					sum_n += a[pointer_n]
				else:
					break
				pointer_n += 1
			while pointer_k < k:
				curr = b[pointer_k]
				while curr % m == 0:
					curr //= m
				if curr == rem:
					sum_k += b[pointer_k]
				else:
					break
				pointer_k += 1
			if sum_n != sum_k:
				fl = False
				print('No')
				break
	if fl:
		if pointer_n == n and pointer_k == k:
			print('Yes')
		else:
			print('No')


def solve():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	k = int(input())
	brr = list(map(int, input().split()))
	crr = []
	for num in arr:
		temp = num
		while num % m == 0:
			num //= m
		ext = 0
		if len(crr) > 0 and crr[-1][0] == num:
			ext += crr[-1][1]
			crr.pop()
		crr.append([num, ext + temp // num])
	drr = []
	for num in brr:
		temp = num
		while num % m == 0:
			num //= m
		ext = 0
		if len(drr) > 0 and drr[-1][0] == num:
			ext += drr[-1][1]
			drr.pop()
		drr.append([num, ext + temp // num])
	if crr == drr:
		print('Yes')
	else:
		print('No')
for i in range(int(input())):
	solve()


from os import remove
import sys

def expand_all(x, m):
	cnt = 1
	while x % m == 0:
		cnt *= m
		x //= m
	return (x, cnt)

def extract(array: list, value: int):
	res = []
	for i in range(len(array)):
		(x, y) = expand_all(array[i], value)
		if i == 0:
			res.append((x, y))
		else:
			(p, q) = res[-1]
			if x == p:
				res[-1] = (x, q + y)
			else:
				res.append((x, y))
	return res

def solve():
	input = sys.stdin.readline
	t = int(input())
	for _ in range(t):
		line = input().split(' ')
		n = int(line[0])
		m = int(line[1])
		a = list(map(int, input().split(' ')))
		k = int(input())
		b = list(map(int, input().split(' ')))
		if extract(a, m) == extract(b, m):
			print('Yes')
		else:
			print('No')
solve()


import sys

def solve1(a, m):
	r = []
	for x in a:
		z = 1
		while x % m == 0:
			z *= m
			x //= m
		if r and r[-1][0] == x:
			r[-1][1] += z
		else:
			r.append([x, z])
	return r

def solve():
	inp = sys.stdin.readline
	(n, m) = map(int, inp().split())
	a = list(map(int, inp().split()))
	k = int(inp())
	b = list(map(int, inp().split()))
	if solve1(a, m) == solve1(b, m):
		print('Yes')
	else:
		print('No')

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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))

	def expand(arr, z):
		e = []
		for x in arr:
			c = 1
			while x % z == 0:
				c *= z
				x = x // z
			if len(e) != 0 and e[-1][0] == x:
				e[-1][1] += c
			else:
				e.append([x, c])
		return e
	if expand(a, m) == expand(b, m):
		print('Yes')
	else:
		print('No')


def convert(arr, m):
	res = []
	for val in arr:
		num = 1
		while val % m == 0:
			val //= m
			num *= m
		if len(res) > 0 and res[-1][0] == val:
			res[-1][1] += num
		else:
			res.append([val, num])
	return res
for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	p = convert(a, m)
	l = convert(b, m)
	if p == l:
		print('Yes')
	else:
		print('No')


def listbreak(x, m):
	nt = 1
	while x % m == 0:
		x //= m
		nt *= m
	return [x, nt]
t = int(input())
for _ in range(t):
	(n1, m) = map(int, input().split())
	a = list(map(int, input().split()))
	n2 = int(input())
	b = list(map(int, input().split()))
	(na, nb) = ([listbreak(a[0], m)], [listbreak(b[0], m)])
	for i in range(1, n1):
		ret = listbreak(a[i], m)
		if ret[0] == na[-1][0]:
			na[-1][1] += ret[1]
		else:
			na.append(ret)
	for i in range(1, n2):
		ret = listbreak(b[i], m)
		if ret[0] == nb[-1][0]:
			nb[-1][1] += ret[1]
		else:
			nb.append(ret)
	if na == nb:
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline

def expand(lst, m):
	c = []
	for num in lst:
		cnt = 1
		while num % m == 0:
			num //= m
			cnt *= m
		if len(c) == 0:
			c.append([num, cnt])
		elif c[-1][0] == num:
			c[-1][1] += cnt
		else:
			c.append([num, cnt])
	return c
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	a = expand(a, m)
	b = expand(b, m)
	if a == b:
		print('Yes')
	else:
		print('No')


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def find(x, m):
	count = 0
	while x % m == 0:
		count += 1
		x //= m
	return (x, m ** count)

def check(a, m):
	new = [[0, 0]]
	for i in a:
		temp = find(i, m)
		if new[-1][0] != temp[0]:
			new.append([temp[0], 0])
		new[-1][1] += temp[1]
	return new
for t in range(int(input())):
	(n, m) = mi()
	a = li()
	k = ni()
	b = li()
	if check(a, m) == check(b, m):
		print('Yes')
	else:
		print('No')


def decom(a, m):
	c = 1
	while a % m == 0:
		a = a // m
		c = c * m
	return (a, c)
for time in range(int(input())):
	(t, m) = map(int, input().split())
	a = [int(k) for k in input().split()]
	t = input()
	b = [int(k) for k in input().split()]
	arep = ([], [])
	brep = ([], [])
	for j in a:
		(d, c) = decom(j, m)
		if len(arep[0]) > 0 and arep[0][-1] == d:
			arep[1][-1] += c
		else:
			arep[0].append(d)
			arep[1].append(c)
	for j in b:
		(d, c) = decom(j, m)
		if len(brep[0]) > 0 and brep[0][-1] == d:
			brep[1][-1] += c
		else:
			brep[0].append(d)
			brep[1].append(c)
	if brep == arep:
		print('Yes')
	else:
		print('No')


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	k = int(input())
	B = list(map(int, input().split()))
	if abs(n - k) % (m - 1) > 0:
		return 'No'
	arr1 = []
	arr2 = []
	for i in range(n):
		v1 = A[i]
		cnt = 0
		while v1 > 0 and v1 % m == 0:
			v1 //= m
			cnt += 1
		if not arr1:
			arr1.append([v1, m ** cnt])
		elif arr1[-1][0] == v1:
			arr1[-1][1] += m ** cnt
		else:
			arr1.append([v1, m ** cnt])
	for j in range(k):
		v2 = B[j]
		cnt = 0
		while v2 > 0 and v2 % m == 0:
			v2 //= m
			cnt += 1
		if not arr2:
			arr2.append([v2, m ** cnt])
		elif arr2[-1][0] == v2:
			arr2[-1][1] += m ** cnt
		else:
			arr2.append([v2, m ** cnt])
	(u, v) = (len(arr1), len(arr2))
	if u != v:
		return 'No'
	for i in range(u):
		if arr1[i] != arr2[i]:
			return 'No'
	return 'Yes'
for _ in range(int(input())):
	print(solve())


from itertools import repeat

def expand(l, m):
	expL = []
	for elm in l:
		t = 1
		while elm % m == 0:
			t = t * m
			elm = elm / m
		if expL and expL[-1][0] == elm:
			expL[-1][1] = expL[-1][1] + int(t)
		else:
			expL.append([int(elm), int(t)])
	return expL
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	expA = expand(a, m)
	expB = expand(b, m)
	if expA == expB:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[1, int(x)] for x in input().split()]
	k = int(input())
	b = [[1, int(x)] for x in input().split()]
	while True:
		while a and b and (a[-1][1] == b[-1][1]):
			t = min(a[-1][0], b[-1][0])
			a[-1][0] -= t
			b[-1][0] -= t
			if not a[-1][0]:
				a.pop()
			if not b[-1][0]:
				b.pop()
		if not a or not b:
			break
		while (t := a[-1][1]) % m == 0:
			if a[-1][0] > 1:
				a[-1][0] -= 1
			else:
				a.pop()
			a.append([m, t // m])
		while (t := b[-1][1]) % m == 0:
			if b[-1][0] > 1:
				b[-1][0] -= 1
			else:
				b.pop()
			b.append([m, t // m])
		if a[-1][1] != b[-1][1]:
			break
	print('No' if a or b else 'Yes')


for _ in range(int(input())):
	(na, x) = map(int, input().split())
	a = (*map(int, input().split()),)
	nb = int(input())
	b = (*map(int, input().split()),)
	x_to_the = [1]
	mx = max(max(a), max(b))
	while x_to_the[-1] <= mx:
		x_to_the.append(x_to_the[-1] * x)
	m = len(x_to_the)
	A = [[1, 0]]
	for num in a:
		for i in range(m):
			if num % x_to_the[i]:
				break
		count = x_to_the[i - 1]
		new = num // count
		if new == A[-1][0]:
			A[-1][-1] += count
		else:
			A.append([new, count])
	B = [[1, 0]]
	for num in b:
		for i in range(m):
			if num % x_to_the[i]:
				break
		count = x_to_the[i - 1]
		new = num // count
		if new == B[-1][0]:
			B[-1][-1] += count
		else:
			B.append([new, count])
	if A == B:
		print('Yes')
	else:
		print('No')


def f(arr, n, m):
	ar = []
	for i in range(n):
		p = 1
		x = arr[i]
		while x % m == 0:
			x = x // m
			p *= m
		tm = [x, p]
		ar.append(tm)
	li = []
	i = 0
	while i < len(ar):
		li.append(ar[i])
		j = i + 1
		while j < len(ar) and ar[i][0] == ar[j][0]:
			li[len(li) - 1][1] += ar[j][1]
			j += 1
		i = j
	return li
t = int(input())
for i in range(t):
	(n, g) = map(int, input().split())
	arr = list(map(int, input().split()))
	m = int(input())
	ar = list(map(int, input().split()))
	smarr = sum(arr)
	smar = sum(ar)
	if smarr != smar:
		print('No')
	else:
		a = f(arr, n, g)
		b = f(ar, m, g)
		if a == b:
			print('Yes')
		else:
			print('No')


t = int(input())

def my_reduce(s, m):
	extras = []
	for k in s:
		time = 1
		while k % m == 0:
			time *= m
			k /= m
		time = max(time, 1)
		extras += [[int(k), time]]
	i = 1
	typer = extras[0][0]
	prev = 0
	while i < len(extras):
		if extras[i][0] == typer:
			extras[prev][1] += extras[i][1]
			extras[i] = 0
		else:
			typer = extras[i][0]
			prev = i
		i += 1
	return [x for x in extras if x]
for i in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	a = my_reduce(a, m)
	b = my_reduce(b, m)
	if a == b:
		print('Yes')
	else:
		print('No')


def cal(n, a, m):
	(c, d) = ([], [])
	for i in range(n):
		e = 1
		while a[i] % m == 0:
			a[i] //= m
			e *= m
		if len(c) == len(d) and len(d) == 0 or c[len(c) - 1] != a[i]:
			c.append(a[i])
			d.append(e)
		else:
			d[len(d) - 1] += e
	return (c, d)
for p in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	(c, d) = cal(n, a, m)
	(f, g) = cal(k, b, m)
	if c == f and d == g:
		print('Yes')
	else:
		print('No')


def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = list(map(int, input().split()))
		k = int(input())
		b = list(map(int, input().split()))
		(aa, bb) = ([], [])
		for i in range(n):
			c = 1
			while a[i] % m == 0:
				a[i] //= m
				c *= m
			if len(aa) != 0 and aa[-1][0] == a[i]:
				aa[-1][1] += c
			else:
				aa.append([a[i], c])
		for i in range(k):
			c = 1
			while b[i] % m == 0:
				b[i] //= m
				c *= m
			if len(bb) != 0 and bb[-1][0] == b[i]:
				bb[-1][1] += c
			else:
				bb.append([b[i], c])
		if aa == bb:
			print('Yes')
		else:
			print('No')
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arra = list(map(int, input().split()))
	k = map(int, input().split())
	arrb = list(map(int, input().split()))
	v = []
	for q in [arra, arrb]:
		r = []
		for i in q:
			tms = 1
			vl = i
			while vl % m == 0:
				tms *= m
				vl //= m
			if len(r) > 0 and r[-1][0] == vl:
				r[-1][1] += tms
			else:
				r.append([vl, tms])
		v.append(r)
	print('Yes' if v[0] == v[1] else 'No')


def spread(num):
	times = 0
	while num % m == 0:
		times += 1
		num = int(num / m)
	return (num, m ** times)

def append(arr, x, times=1):
	if not arr or arr[-1][0] != x:
		arr.append([x, times])
	else:
		arr[-1][1] += times

def flatten(a):
	new_a = []
	for x in a:
		if x % m == 0:
			(num, times) = spread(x)
			append(new_a, num, times)
		else:
			append(new_a, x, 1)
	return new_a
tests = int(input())
for _ in range(tests):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	a = flatten(a)
	b = flatten(b)
	print('Yes' if a == b else 'No')


T = int(input())
for i in range(T):
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr_2 = arr.copy()
	k = int(input())
	brr = list(map(int, input().split()))
	brr_2 = brr.copy()
	for i in range(n):
		while arr_2[i] % m == 0:
			arr_2[i] //= m
	for i in range(k):
		while brr_2[i] % m == 0:
			brr_2[i] //= m
	pos_a = 0
	stats_a = []
	last = -1
	for i in range(n):
		if arr_2[i] != last:
			last = arr_2[i]
			stats_a.append([last, arr[i]])
		else:
			stats_a[-1][1] += arr[i]
	stats_b = []
	last = -1
	for i in range(k):
		if brr_2[i] != last:
			last = brr_2[i]
			stats_b.append([last, brr[i]])
		else:
			stats_b[-1][1] += brr[i]
	if stats_b == stats_a:
		print('Yes')
	else:
		print('No')


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	a0 = [int(x) for x in input().split()]
	k = int(input())
	b0 = [int(x) for x in input().split()]
	a = []
	b = []
	for i in range(n):
		q = a0[i]
		j = 1
		while q % m == 0:
			j *= m
			q //= m
		if i > 0 and q == a[-1][0]:
			a[-1][1] += j
		else:
			a.append([q, j])
	for i in range(k):
		q = b0[i]
		j = 1
		while q % m == 0:
			j *= m
			q //= m
		if i > 0 and q == b[-1][0]:
			b[-1][1] += j
		else:
			b.append([q, j])
	if len(a) == len(b):
		s = True
		for i in range(len(a)):
			if (a[i][0] == b[i][0] and a[i][1] == b[i][1]) == False:
				s = False
				break
		if s:
			print('Yes')
		else:
			print('No')
	else:
		print('No')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	nls = []
	top = -1
	for i in lst:
		cnt = 1
		while i % m == 0:
			i //= m
			cnt *= m
		if nls and nls[top][0] == i:
			nls[top][1] += cnt
		else:
			top += 1
			nls.append([i, cnt])
	k = int(input())
	lt = list(map(int, input().split()))
	nl = []
	top = -1
	for i in lt:
		cnt = 1
		while i % m == 0:
			i //= m
			cnt *= m
		if nl and nl[top][0] == i:
			nl[top][1] += cnt
		else:
			top += 1
			nl.append([i, cnt])
	if nls == nl:
		print('Yes')
	else:
		print('No')


def reduce(l, m):
	d = []
	last = l[0]
	c = 1
	for i in l[1:]:
		if i != last:
			d.append([last, c])
			last = i
			c = 1
		else:
			c += 1
	d.append([last, c])
	for i in range(len(d)):
		while d[i][0] % m == 0:
			d[i] = [d[i][0] // m, d[i][1] * m]
	r = [d[0]]
	for i in range(1, len(d)):
		if d[i][0] == r[-1][0]:
			r[-1][1] += d[i][1]
		else:
			r.append(d[i])
	return r
for case in range(int(input())):
	(_, m) = [int(j) for j in input().split()]
	a = [int(j) for j in input().split()]
	input()
	b = [int(j) for j in input().split()]
	print(['No', 'Yes'][reduce(a, m) == reduce(b, m)])


t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	a1 = []
	for i in range(n):
		q = a[i]
		x = 1
		while q % m == 0:
			x *= m
			q //= m
		a1 += [[q, x]]
	b1 = []
	for j in range(k):
		p = b[j]
		y = 1
		while p % m == 0:
			y *= m
			p //= m
		b1 += [[p, y]]
	e = 0
	f = 0
	while e < n and f < k:
		if a1[e] == b1[f]:
			e += 1
			f += 1
		elif a1[e][0] == b1[f][0]:
			if a1[e][1] > b1[f][1]:
				a1[e][1] -= b1[f][1]
				f += 1
			else:
				b1[f][1] -= a1[e][1]
				e += 1
		else:
			print('No')
			break
	else:
		if e == n and f == k:
			print('Yes')
		else:
			print('No')


t = int(input())
for jkjk in range(t):
	(n, m) = tuple(map(int, input().split()))
	arr = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	a_mod = []
	b_mod = []
	for i in range(len(arr)):
		p = 1
		while arr[i] % m == 0:
			arr[i] = arr[i] // m
			p = p * m
		a_mod.append(p)
	for i in range(len(b)):
		p = 1
		while b[i] % m == 0:
			b[i] = b[i] // m
			p = p * m
		b_mod.append(p)
	(i, j) = (0, 0)
	while 1:
		if i >= n and j >= k:
			print('Yes')
			break
		if i >= n or j >= k:
			print('No')
			break
		if arr[i] != b[j]:
			print('No')
			break
		else:
			jin = min(a_mod[i], b_mod[j])
			a_mod[i] -= jin
			b_mod[j] -= jin
			if a_mod[i] == 0:
				i += 1
			if b_mod[j] == 0:
				j += 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	cpt = 0
	crem = a[0]
	ok = True
	mstep = a.copy()
	ac = [None] * n
	bc = [None] * k
	for i in range(n):
		q = divmod(mstep[i], m)
		cnt = 1
		while not q[1]:
			mstep[i] //= m
			cnt *= m
			q = divmod(mstep[i], m)
		ac[i] = [mstep[i], cnt]
	mstep = b.copy()
	for i in range(k):
		q = divmod(mstep[i], m)
		cnt = 1
		while not q[1]:
			mstep[i] //= m
			cnt *= m
			q = divmod(mstep[i], m)
		bc[i] = [mstep[i], cnt]
	for i in range(len(ac) - 2, -1, -1):
		if ac[i][0] == ac[i + 1][0]:
			ac[i][1] += ac[i + 1][1]
			ac[i + 1][0] = 0
	ac = [x for x in ac if x[0]]
	for i in range(len(bc) - 2, -1, -1):
		if bc[i][0] == bc[i + 1][0]:
			bc[i][1] += bc[i + 1][1]
			bc[i + 1][0] = 0
	bc = [x for x in bc if x[0]]
	print('Yes' if ac == bc else 'No')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	k = int(input())
	b = list(map(int, input().split()))
	i = 0
	c = [1] * n
	while i < n:
		if a[i] % m == 0:
			temp = a[i] // m
			a[i] = temp
			c[i] = c[i] * m
		else:
			i += 1
	i = 0
	d = [1] * k
	while i < k:
		if b[i] % m == 0:
			temp = b[i] // m
			b[i] = temp
			d[i] = d[i] * m
		else:
			i += 1
	i = 1
	while i < n:
		if a[i] == a[i - 1]:
			c[i] = c[i] + c[i - 1]
			a.pop(i - 1)
			c.pop(i - 1)
			n -= 1
		else:
			i += 1
	i = 1
	while i < k:
		if b[i] == b[i - 1]:
			d[i] = d[i] + d[i - 1]
			b.pop(i - 1)
			d.pop(i - 1)
			k -= 1
		else:
			i += 1
	if n != k:
		print('No')
	else:
		flag = True
		for i in range(n):
			if a[i] != b[i] or c[i] != d[i]:
				flag = False
				break
		if flag:
			print('Yes')
		else:
			print('No')