Read problems statements in Mandarin Chinese  and Russian. 

Once Chef decided to divide the tangerine into several parts. At first, he numbered tangerine's segments from 1 to n in the clockwise order starting from some segment. Then he intended to divide the fruit into several parts. In order to do it he planned to separate the neighbouring segments in k places, so that he could get k parts: the 1^{st} - from segment l_{1} to segment r_{1} (inclusive), the 2^{nd} - from l_{2} to r_{2}, ..., the k^{th} - from l_{k} to r_{k} (in all cases in the clockwise order). Suddenly, when Chef was absent, one naughty boy came and divided the tangerine into p parts (also by separating the neighbouring segments one from another): the 1^{st} - from segment a_{1} to segment b_{1}, the 2^{nd} - from a_{2} to b_{2}, ..., the p^{th} - from a_{p} to b_{p} (in all cases in the clockwise order). Chef became very angry about it! But maybe little boy haven't done anything wrong, maybe everything is OK? Please, help Chef to determine whether he is able to obtain the parts he wanted to have (in order to do it he can divide p current parts, but, of course, he can't join several parts into one).
Please, note that parts are not cyclic. That means that even if the tangerine division consists of only one part, but that part include more than one segment, there are two segments which were neighbouring in the initial tangerine but are not neighbouring in the division. See the explanation of example case 2 to ensure you understood that clarification.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains three space separated integers n, k, p, denoting the number of tangerine's segments and number of parts in each of the two divisions. The next k lines contain pairs of space-separated integers l_{i} and r_{i}. The next p lines contain pairs of space-separated integers a_{i} and b_{i}.

It is guaranteed that each tangerine's segment is contained in exactly one of the first k parts and in exactly one of the next p parts.

------ Output ------ 

For each test case, output a single line containing either "Yes" or "No" (without the quotes), denoting whether Chef is able to obtain the parts he wanted to have.
 
------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ n ≤ 5 * 10^{7}$
$1 ≤ k ≤ min(500, n)$
$1 ≤ p ≤ min(500, n)$
$1 ≤ l_{i}, r_{i}, a_{i}, b_{i} ≤ n$
 
----- Sample Input 1 ------ 
2
10 3 2
1 4
5 5
6 10
1 5
6 10
10 3 1
2 5
10 1
6 9
1 10
----- Sample Output 1 ------ 
Yes
No
----- explanation 1 ------ 
Example case 1: To achieve his goal Chef should divide the first part (1-5) in two by separating segments 4 and 5 one from another.
Example case 2: The boy didn't left the tangerine as it was (though you may thought that way), he separated segments 1 and 10 one from another. But segments 1 and 10 are in one part in Chef's division, so he is unable to achieve his goal.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
def snek(c, k):
	if len(u) > len(c):
		return False
	c.sort()
	u.sort()
	(x, y) = (0, 0)
	while x < len(c) and y < len(u):
		if c[x][0] == k[y][0]:
			x += 1
			y += 1
		elif c[x][0] < k[y][0]:
			x += 1
		else:
			return False
	return y == len(u)
t = int(input())
for i in range(t):
	(n, k, p) = map(int, input().split())
	c = []
	u = []
	for j in range(k):
		c.append(list(map(int, input().split())))
	for z in range(p):
		u.append(list(map(int, input().split())))
	if snek(c, u):
		r = 'Yes'
	else:
		r = 'No'
	print(r)


t = int(input())
for ii in range(t):
	d_chef = {}
	d_boy = {}
	(n, k, p) = map(int, input().split())
	d_chef = set({int(input().split()[1]) for j in range(k)})
	d_boy = set({int(input().split()[1]) for j in range(p)})
	r = 'Yes'
	if not d_boy.issubset(d_chef):
		r = 'No'
	print(r)


def solution(chefsdiv, kidsdiv):
	if len(kidsdiv) > len(chefsdiv):
		return False
	chefsdiv.sort()
	kidsdiv.sort()
	(i, j) = (0, 0)
	while i < len(chefsdiv) and j < len(kidsdiv):
		if chefsdiv[i][0] == kidsdiv[j][0]:
			i += 1
			j += 1
		elif chefsdiv[i][0] < kidsdiv[j][0]:
			i += 1
		else:
			return False
	return j == len(kidsdiv)
t = int(input())
while t:
	(n, k, p) = map(int, input().split())
	chefsdiv = []
	kidsdiv = []
	for _ in range(k):
		chefsdiv.append(list(map(int, input().split())))
	for _ in range(p):
		kidsdiv.append(list(map(int, input().split())))
	res = 'Yes' if solution(chefsdiv, kidsdiv) else 'No'
	print(res)
	t -= 1


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(n, k, p) = list(map(int, sys.stdin.readline().split()))
	k_cuts = set((int(sys.stdin.readline().split()[0]) for _ in range(k)))
	p_cuts = set((int(sys.stdin.readline().split()[0]) for _ in range(p)))
	print('Yes' if len(p_cuts - k_cuts) == 0 else 'No')


for _ in range(int(input())):
	(n, k, p) = map(int, input().split())
	s = set()
	t = set()
	f = True
	for i in range(k):
		(x, y) = map(int, input().split())
		s.add(x)
	for i in range(p):
		(x, y) = map(int, input().split())
		t.add(x)
	ans = 'Yes' if len(t - s) == 0 else 'No'
	print(ans)