For given two sequneces $A = \\{a_0, a_1, ..., a_{n-1}\\}$ and $B = \\{b_0, b_1, ..., b_{m-1}\\}$, determine whether all elements of $B$ are included in $A$. Note that, elements of $A$ and $B$ are sorted by ascending order respectively.

Constraints

* $1 \leq n, m \leq 200,000$
* $-1,000,000,000 \leq a_0 < a_1 < ... < a_{n-1} \leq 1,000,000,000$
* $-1,000,000,000 \leq b_0 < b_1 < ... < b_{m-1} \leq 1,000,000,000$

Input

The input is given in the following format.


$n$
$a_0 \; a_1 \; ,..., \; a_{n-1}$
$m$
$b_0 \; b_1 \; ,..., \; b_{m-1}$


The number of elements in $A$ and its elements $a_i$ are given in the first and second lines respectively. The number of elements in $B$ and its elements $b_i$ are given in the third and fourth lines respectively.

Output

Print 1, if $A$ contains all elements of $B$, otherwise 0.

Examples

Input

4
1 2 3 4
2
2 4


Output

1


Input

4
1 2 3 4
3
1 2 5


Output

0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
n = int(input())
a = set(map(int, input().split()))
m = int(input())
print(+a.issuperset(set(map(int, input().split()))))


input()
A = set(map(int, input().split()))
int(input())
B = set(map(int, input().split()))
if B <= A:
	print('1')
else:
	print('0')


input()
arr1 = input().split()
input()
arr2 = input().split()
not_in_arr1 = set(arr2) - set(arr1)
print(int(len(not_in_arr1) == 0))


_ = input()
A = set(input().split())
_ = input()
B = set(input().split())
print(int(A & B == B))


input()
A = set(input().split())
input()
B = set(input().split())
print(1 if B <= A else 0)


n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))
if set(A) & set(B) == set(B):
	print('1')
else:
	print('0')


readline = open(0).readline
N = int(readline())
A = set(map(int, readline().split()))
M = int(readline())
B = set(map(int, readline().split()))
print(+(len(A & B) == M))


n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
if set(b).issubset(set(a)):
	print(1)
else:
	print(0)


n = int(input())
A = set(map(int, input().split()))
n = int(input())
B = set(map(int, input().split()))
if B <= A:
	print(1)
else:
	print(0)


n = int(input())
a = set(map(int, input().split()))
m = int(input())
b = set(map(int, input().split()))
if b - a:
	print(0)
else:
	print(1)


def main():
	m = int(input())
	a = list(map(int, input().split()))
	n = int(input())
	b = list(map(int, input().split()))
	if len(a) < len(b):
		print(0)
	elif b[0] < a[0]:
		print(0)
	elif a[-1] < b[-1]:
		print(0)
	else:
		print(hoge(a, b))

def hoge(a, b):
	i = j = 0
	while 1:
		if len(b) <= j:
			return 1
		elif len(a) <= i:
			return 0
		itema = a[i]
		itemb = b[j]
		if itema == itemb:
			i += 1
			j += 1
			continue
		elif itema < itemb:
			i += 1
			continue
		else:
			return 0
main()


n = int(input())
a = list(map(int, input().split(' ')))
m = int(input())
b = list(map(int, input().split(' ')))
if set(b).issubset(set(a)):
	print(1)
else:
	print(0)


n = int(input())
A = set([int(x) for x in input().split()])
m = int(input())
B = set([int(x) for x in input().split()])
ans = 0
if A.issuperset(B):
	ans = 1
print(ans)


def solve():
	from sys import stdin
	f_i = stdin
	n = int(f_i.readline())
	A = map(int, f_i.readline().split())
	m = int(f_i.readline())
	B = tuple(map(int, f_i.readline().split()))
	i = 0
	for a in A:
		if a == B[i]:
			i += 1
			if i == m:
				print(1)
				break
	else:
		print(0)
solve()


import bisect

def main():
	n = int(input())
	A = list(map(int, input().split()))
	m = int(input())
	B = list(map(int, input().split()))
	(left, right) = (0, n)
	for i in range(m):
		mid = bisect.bisect_left(A, B[i], left, right)
		if mid < left or right == mid or A[mid] != B[i]:
			print(0)
			return
		left = mid + 1
	print(1)
main()


n = int(input())
a = set(map(int, input().split()))
m = int(input())
b = set(map(int, input().split()))
if b <= a:
	print(1)
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
da = {}
db = {}
if n < m:
	bul = 0
else:
	bul = 1
for i in a:
	da[i] = 1
for j in b:
	db[j] = 1
for i in db:
	if not i in da or bul == 0:
		bul = 0
		break
	else:
		del da[i]
print(bul)


import sys
n = int(input())
a = tuple(map(int, sys.stdin.readline().split()))
m = int(input())
b = tuple(map(int, sys.stdin.readline().split()))
if set(a) >= set(b):
	print('1')
else:
	print('0')


n = int(input())
num = list(map(int, input().split()))
m = int(input())
num2 = list(map(int, input().split()))
for k in num2:
	low = 0
	high = len(num)
	t = (low + high) // 2
	if k > num[-1]:
		print(0)
		break
	while low <= high:
		if k == num[t]:
			break
		elif k > num[t]:
			low = t + 1
		elif k < num[t]:
			high = t - 1
		t = (low + high) // 2
	if k != num[t]:
		print(0)
		break
else:
	print(1)


n = int(input())
A = frozenset(map(int, input().split()))
m = int(input())
B = frozenset(map(int, input().split()))
if A.issuperset(B):
	print(1)
else:
	print(0)


def main():
	n = int(input())
	in1 = [int(a) for a in input().split()]
	m = int(input())
	in2 = [int(a) for a in input().split()]
	a = set(in1)
	b = set(in2)
	if a >= b:
		print('1')
	else:
		print('0')
main()


n = int(input())
a = set(map(lambda x: int(x), input().split()))
m = int(input())
b = set(map(lambda x: int(x), input().split()))
if b <= a:
	print(1)
else:
	print(0)


input()
a = set([int(x) for x in input().split()])
input()
b = set([int(x) for x in input().split()])
if b <= a:
	print(1)
else:
	print(0)


def includes(li1, li2):

	def partition(li, x):
		if len(li) == 0:
			return 0
		mid = len(li) // 2
		if li[mid] < x:
			return mid + 1 + partition(li[mid + 1:], x)
		elif li[mid] > x:
			return partition(li[:mid], x)
		else:
			return mid

	def binsearch(li, x):
		i = partition(li, x)
		if 0 <= i < len(li):
			return li[i] == x
		else:
			return False
	if len(li1) < len(li2):
		return False
	if len(li2) > 1:
		mid = len(li2) // 2
		i = partition(li1, li2[mid])
		if i >= len(li1) or li2[mid] != li1[i]:
			return False
		else:
			return includes(li1[:i], li2[:mid]) and includes(li1[i + 1:], li2[mid + 1:])
	elif len(li2) == 1:
		return binsearch(li1, li2[0])
	else:
		return True

def run():
	n = int(input())
	la = [int(x) for x in input().split()]
	assert n == len(la)
	m = int(input())
	lb = [int(x) for x in input().split()]
	assert m == len(lb)
	if includes(la, lb):
		print(1)
	else:
		print(0)
run()


n = int(input())
lia = set(map(int, input().split()))
m = int(input())
lib = set(map(int, input().split()))
if lib <= lia:
	print(1)
else:
	print(0)


n = int(input())
listA = list(map(int, input().split()))
m = int(input())
listB = list(map(int, input().split()))
listC = list(set(listB) & set(listA))
if set(listB) == set(listC):
	print(1)
else:
	print(0)


n = int(input())
a = set(list(map(int, input().split())))
m = int(input())
b = set(list(map(int, input().split())))
print(1 if b.issubset(a) else 0)


from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.append(1000000001)
m = int(input())
b = list(map(int, input().split()))
if len(b) > len(a):
	print(0)
else:
	(p, f) = (0, 1)
	for k in b:
		p = bisect_left(a, k, p)
		if a[p] != k:
			f = 0
			break
	print(f)


input()
a = list(map(int, input().split()))
input()
b = list(map(int, input().split()))
A = set(a)
B = set(b)
print(1 if B <= A else 0)


import bisect
n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))
minA = A[0]
maxA = A[-1]
answer = False
for i in range(m):
	if B[i] < minA or maxA < B[i]:
		answer = False
		break
	elif A[bisect.bisect_left(A, B[i])] == B[i]:
		answer = True
	else:
		answer = False
		break
if answer:
	print(1)
else:
	print(0)


n = int(input())
a = set(list(map(int, input().split())))
m = int(input())
b = set(list(map(int, input().split())))
print(1 if b.issubset(a) else 0)


input()
a = set(input().split())
input()
b = set(input().split())
print(1 if b.issubset(a) else 0)


n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
a = set(a)
b = set(b)
print(1 if b <= a else 0)


n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
a.sort()
b.sort()
ans = [0] * m
i = 0
j = 0
while i < m and j < n:
	if b[i] < a[j]:
		i += 1
	elif b[i] == a[j]:
		ans[i] = 1
		j += 1
	else:
		j += 1
flag = 1
for i in range(m):
	if ans[i] == 0:
		flag = 0
print(flag)


n = int(input())
lista = list(map(int, input().split()))
m = int(input())
listb = list(map(int, input().split()))
i = 0
j = 0
while True:
	if lista[n - 1] < listb[m - 1]:
		print('0')
		break
	if lista[i] > listb[j]:
		print('0')
		break
	elif listb[j] == listb[m - 1] == lista[i]:
		print('1')
		break
	elif lista[i] < listb[j]:
		i += 1
	elif lista[i] == listb[j]:
		j += 1
		i += 1


n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))
include = len(set(A) ^ set(B))
if include == abs(len(A) - len(B)) and len(A) >= len(B):
	print(1)
else:
	print(0)


def binarySearch(n, a):
	ok = -1
	ng = len(a)
	while abs(ok - ng) > 1:
		mid = (ok + ng) // 2
		if a[mid] == n:
			return 1
		elif a[mid] < n:
			ok = mid
		else:
			ng = mid
	return 0

def resolve():
	import sys
	input = sys.stdin.readline
	n = int(input())
	a = [int(i) for i in input().split()]
	q = int(input())
	kk = [int(i) for i in input().split()]
	for k in kk:
		if 0 == binarySearch(k, a):
			print(0)
			return
	print(1)
resolve()


n_a = int(input())
a = [int(i) for i in input().split()]
n_b = int(input())
b = [int(j) for j in input().split()]
if set(a) & set(b) == set(b):
	print('1')
else:
	print('0')


import sys
input = sys.stdin.readline

def binsearch(d, l):
	max = len(l) - 1
	min = 0
	mid = max // 2
	while True:
		if l[mid] > d:
			max = mid
		elif l[mid] == d:
			return True
		else:
			min = mid
		mid = (max + min) // 2
		if mid == max or mid == min:
			if l[mid] == d or l[max] == d:
				return True
			return False

def main():
	n1 = int(input())
	l1 = list(map(int, input().split()))
	n2 = int(input())
	l2 = list(map(int, input().split()))
	for i in l2:
		result = binsearch(i, l1)
		if result == False:
			print(0)
			return
	else:
		print(1)
main()


input()
a = set(input().split())
input()
b = set(input().split())
print(1 if len(b - a) == 0 else 0)