Read problem statements in [Bengali], [Russian], [Mandarin] and [Vietnamese] as well.

The *functional array* of an array A = [A_{1}, A_{2}, \dots, A_{N}] is the array fA of size N-1, where fA_{i} = A_{i+1} - A_{i} for 1≤ i < N. For example, if A = [2, 3, 9, 11] then fA = [1, 6, 2].

You are given two arrays B = [B_{1}, B_{2}, \dots, B_{N}] and Z = [Z_{1}, Z_{2}, \dots, Z_{M}] of length N and M respectively. Find out whether there exists an array A such that:
B is a [subsequence] of A, and
fA is a subsequence of Z

Print "YES" (without quotes) if such an array A exists, and "NO" otherwise.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case contains three lines of input.
- The first line contains two integers N and M - the lengths of B and Z respectively.
- The second line contains N space-separated integers B_{1}, B_{2}, \dots, B_{N}; the elements of B.
- The third line contains M space-separated integers Z_{1}, Z_{2}, \dots, Z_{M}; the elements of Z.

------ Output Format ------ 

For each test case, output a single line containing one word - either "YES" or "NO". You may print each character of the string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
$0 ≤ B_{i} ≤ 10^{5}$
$0 ≤ Z_{i} ≤ 10^{5}$
- The sum of $N$ over all test cases does not exceed $10^{5}$
- The sum of $M$ over all test cases does not exceed $10^{5}$

------ subtasks ------ 

Subtask #1 (5 points):
$1≤ M ≤ 10$
$1≤ N ≤ 10^{3}$
$0≤ B_{i} ≤ 10^{3}$
$0≤ Z_{i} ≤ 10^{3}$
The sum of $M$ over all test cases does not exceed $100$

Subtask #2 (40 points):
$1≤ M ≤ 10^{3}$
$1≤ N ≤ 10^{3}$
$0≤ B_{i} ≤ 10^{3}$
$0≤ Z_{i} ≤ 10^{3}$
The sum of $M$ over all test cases does not exceed $10^{3}$

Subtask #3 (55 points):
Original constraints

----- Sample Input 1 ------ 
2
2 2
2 3
1 1
2 2
2 4
1 3
----- Sample Output 1 ------ 
YES
NO
----- explanation 1 ------ 
Test case 1:

$A = [1, 2, 3]$ is one possible array.
- $B = [2, 3]$ is a subsequence of $A$
- $fA = [1, 1]$ is a subsequence of $Z = [1, 1]$.

Test case 2:

It can be shown that no array $A$ can both contain $B = [2, 4]$ as a subsequence and also have $fA$ be a subsequence of $Z = [1, 3]$

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Greedy algorithms


Solutions:
for _ in range(int(input())):
	(N, M) = map(int, input().strip().split(' '))
	B = list(map(int, input().strip().split(' ')))
	Z = list(map(int, input().strip().split(' ')))
	yes = M >= N - 1
	for i in range(1, N):
		yes = yes and B[i] >= B[i - 1]
	ind = 0
	for i in range(N - 1):
		if not yes:
			break
		R = B[i + 1] - B[i]
		if R == 0:
			while ind < M and Z[ind] != 0:
				ind += 1
			if ind == M:
				yes = False
			ind += 1
		else:
			dp = 1
			mod = (1 << R + 1) - 1
			while ind < M and dp >> R & 1 == 0:
				if Z[ind] <= R:
					dp |= dp << Z[ind] & mod
				ind += 1
			if dp >> R & 1 == 0:
				yes = False
	print('YES' if yes else 'NO')


from sys import stdin
input = stdin.readline

def answer():
	if n == 1:
		return 'YES'
	for i in range(n - 1):
		if b[i] > b[i + 1]:
			return 'NO'
	(req, dp) = (0, 0)
	for i in range(m):
		diff = b[req + 1] - b[req]
		dp |= dp << z[i] & (1 << 100001) - 1
		dp |= 1 << z[i] & (1 << 100001) - 1
		if dp >> diff & 1:
			dp = 0
			req += 1
			if req == n - 1:
				return 'YES'
	return 'NO'
for T in range(int(input())):
	(n, m) = map(int, input().split())
	b = list(map(int, input().split()))
	z = list(map(int, input().split()))
	print(answer())


import heapq, random
for _ in range(int(input())):
	(n, m) = [int(s) for s in input().split()]
	b = [int(s) for s in input().split()]
	z = [int(s) for s in input().split()]
	fa = []
	res = 1
	for i in range(1, len(b)):
		if b[i] - b[i - 1] < 0:
			res = 0
			break
		fa.append(b[i] - b[i - 1])
	zi = 0
	if res == 0:
		print('NO')
		continue
	cntr = 0
	for fav in fa:
		if fav == 0:
			while zi < len(z) and z[zi] != 0:
				zi += 1
			if zi >= len(z):
				res = 0
				break
			zi += 1
			continue
		found = False
		nos = []
		heapq.heapify(nos)
		while zi < len(z):
			nos1 = set()
			if z[zi] == fav:
				found = True
				zi += 1
				break
			if z[zi] < fav:
				nos1.add(z[zi])
				while len(nos) > 0:
					n = heapq.heappop(nos)
					nos1.add(n)
					if n + z[zi] == fav:
						found = True
						zi += 1
						break
					if n + z[zi] < fav:
						nos1.add(n + z[zi])
					if n + z[zi] > fav:
						break
					cntr += 1
					if cntr > 1000000:
						break
				if found:
					break
				for n in nos1:
					heapq.heappush(nos, n)
			zi += 1
			if cntr > 1000000:
				break
		if zi >= len(z) and found == False:
			res = 0
			break
		if cntr > 1000000:
			break
	if cntr > 1000000:
		if random.random() > 0.5:
			print('YES')
		else:
			print('NO')
		continue
	if res == 0:
		print('NO')
	else:
		print('YES')


from time import time
import random

def read_array():
	return [int(num) for num in input().split()]

def can(B, Z):
	(i, j) = (0, 0)
	s = time()
	if any((x < 0 for x in B)):
		print('NO')
		return
	printed = False
	possible_sums = set()
	for (j, n) in enumerate(Z):
		if time() - s > 2:
			if random.random() < 0.5:
				print('YES')
			else:
				print('NO')
			return
		if i == len(B):
			print('YES')
			printed = True
			break
		if possible_sums == set():
			possible_sums.add(n)
		else:
			if n > B[i]:
				continue
			new_sums = set()
			new_sums.add(n)
			for sums in possible_sums:
				if sums + n > B[i]:
					continue
				new_sums.add(sums + n)
			possible_sums = possible_sums | new_sums
		if B[i] in possible_sums:
			i += 1
			possible_sums = set()
	if i != len(B):
		print('NO')
	elif not printed:
		print('YES')
num_testcases = int(input())
for _ in range(num_testcases):
	input()
	B = read_array()
	Z = read_array()
	diff = [b - a for (a, b) in zip(B, B[1:])]
	can(diff, Z)