The supercomputer system L in the PCK Research Institute performs a variety of calculations upon request from external institutes, companies, universities and other entities. To use the L system, you have to reserve operation time by specifying the start and end time. No two reservation periods are allowed to overlap each other.

Write a program to report if a new reservation overlaps with any of the existing reservations. Note that the coincidence of start and end times is not considered to constitute an overlap. All the temporal data is given as the elapsed time from the moment at which the L system starts operation.



Input

The input is given in the following format.


a b
N
s_1 f_1
s_2 f_2
:
s_N f_N


The first line provides new reservation information, i.e., the start time a and end time b (0 ≤ a < b ≤ 1000) in integers. The second line specifies the number of existing reservations N (0 ≤ N ≤ 100). Subsequent N lines provide temporal information for the i-th reservation: start time s_i and end time f_i (0 ≤ s_i < f_i ≤ 1000) in integers. No two existing reservations overlap.

Output

Output "1" if the new reservation temporally overlaps with any of the existing ones, or "0" otherwise.

Examples

Input

5 7
3
1 4
4 5
7 10


Output

0


Input

3 7
3
7 10
1 4
4 5


Output

1

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(a, b) = map(int, input().split())
N = int(input())
judge = 0
for i in range(N):
	(rs, re) = map(int, input().split())
	if judge == 0:
		if a <= rs and b > rs:
			judge = 1
		elif a > rs and a < re:
			judge = 1
print(judge)


(a, b) = map(int, input().split())
n = int(input())
flag = True
for i in range(n):
	(aa, bb) = map(int, input().split())
	if bb <= a or aa >= b:
		pass
	else:
		flag = False
if flag == True:
	print('0')
else:
	print('1')


(A, B) = map(int, input().split())
N = int(input())
SF = [[0, 0], [1000, 1000]]
for _ in range(N):
	SF.append(list(map(int, input().split())))
SF.sort()
R = 1
for i in range(N + 1):
	if SF[i][1] <= A and B <= SF[i + 1][0]:
		R = 0
		break
print(R)


import itertools
(a, b) = map(int, input().split())
N = int(input())
reserved = [0] * 1001
for _ in range(N):
	(s, f) = map(int, input().split())
	reserved[s] += 1
	reserved[f] -= 1
cumsum = list(itertools.accumulate(reserved))
if sum(cumsum[a:b]):
	print(1)
else:
	print(0)


(a, b) = map(int, input().split())
n = int(input())
l = sorted([list(map(int, input().split())) for _ in range(n)])
line = [0] * 1010
line[a] += 1
line[b] -= 1
for (a, b) in l:
	line[a] += 1
	line[b] -= 1
for i in range(1006):
	line[i + 1] += line[i]
if line.count(2):
	print(1)
else:
	print(0)


(x, y) = map(int, input().split())
n = int(input())
ans = 0
for _ in range(n):
	(a, b) = map(int, input().split())
	if x < b and a < y:
		ans = 1
print(ans)


def overlap(a, b, c, d):
	if d <= a:
		return False
	if b <= c:
		return False
	return True
(a, b) = map(int, input().split())
res = 0
for i in range(int(input())):
	(s, t) = map(int, input().split())
	if overlap(a, b, s, t):
		res = 1
print(res)


(a, b) = map(int, input().split())
c = 0
for i in range(int(input())):
	(s, t) = map(int, input().split())
	if not (t <= a or b <= s):
		c = 1
print(c)


(a, b) = [int(i) for i in input().split()]
N = int(input())
ans = 0
for l in range(N):
	(s, f) = [int(i) for i in input().split()]
	if a < f and s < b:
		ans = 1
		break
print(ans)


time = [0] * 1001
(a, b) = list(map(int, input().split()))
n = int(input())
for i in range(n):
	(s, f) = list(map(int, input().split()))
	time[s:f] = [1] * (f - s)
if sum(time[a:b]) == 0:
	print('0')
else:
	print('1')


def main():
	(a, b) = map(int, input().split())
	n = int(input())
	(s, f) = ([], [])
	for i in range(n):
		(ss, ff) = map(int, input().split())
		s.append(ss)
		f.append(ff)
	for i in range(n):
		if f[i] <= a or b <= s[i]:
			continue
		else:
			return 1
	return 0
print(main())


import sys
(a, b) = map(int, sys.stdin.readline().split())
N = int(sys.stdin.readline())
sf = tuple((tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)))
M = 1000
imos = [0] * (M + 1)
imos[a] += 1
imos[b] -= 1
for (s, f) in sf:
	imos[s] += 1
	imos[f] -= 1
for i in range(M):
	imos[i + 1] += imos[i]
for i in range(a, b + 1):
	if imos[i] > 1:
		print('1')
		exit()
print('0')


(a, b) = map(int, input().split())
N = int(input())
books = []
for i in range(N):
	books.append(list(map(int, input().split())))
is_booked = 0
for i in range(len(books)):
	if books[i][0] <= a < books[i][1]:
		is_booked = 1
	elif a < books[i][0] < b:
		is_booked = 1
print(is_booked)


(n, m) = map(int, input().split())
a = int(input())
for i in range(a):
	(a, b) = map(int, input().split())
	if b <= n or m <= a:
		continue
	else:
		print('1')
		exit()
print('0')


(a, b) = map(int, input().split())
N = int(input())
T = [0] * 1001
ok = 0
for i in range(N):
	(s, f) = map(int, input().split())
	if s < b and a < f:
		ok = 1
print(ok)


(b, e) = map(int, input().split())
r = [0] * 1000
for _ in range(int(input())):
	(b1, e2) = map(int, input().split())
	for x in range(b1, e2):
		r[x] = 1

def check():
	for x in range(b, e):
		if r[x] == 1:
			return 1
	return 0
print(check())


(a, b) = map(int, input().split())
N = int(input())
n = 1009
reserve = [0] * n
b = b - 1
reserve[a] += 1
reserve[b + 1] -= 1
for i in range(N):
	(s, f) = map(int, input().split())
	f = f - 1
	reserve[s] += 1
	reserve[f + 1] -= 1
judge = 0
for i in range(n):
	if i != 0:
		reserve[i] += reserve[i - 1]
	if reserve[i] >= 2:
		judge = 1
print(judge)


def solve():
	from sys import stdin
	f_i = stdin
	(a, b) = map(int, f_i.readline().split())
	N = int(f_i.readline())
	for i in range(N):
		(s, f) = map(int, f_i.readline().split())
		if b <= s or f <= a:
			pass
		else:
			print(1)
			break
	else:
		print(0)
solve()


def check(a, b, lst):
	for (s, f) in lst:
		if not (b <= s or f <= a):
			return 1
	return 0
(a, b) = map(int, input().split())
n = int(input())
lst = [tuple(map(int, input().split())) for _ in range(n)]
print(check(a, b, lst))


(a, b) = map(int, input().split())
n = int(input())
booking = True
for i in range(n):
	(s, f) = map(int, input().split())
	if f <= a or b <= s:
		continue
	else:
		booking = False
print(int(not booking))


(a, b) = map(int, input().split())
n = int(input())
res = []
for _ in range(n):
	(s, f) = map(int, input().split())
	res.append([s, f])
for r in res:
	if r[1] > a and r[0] < b:
		print(1)
		break
else:
	print(0)


(a, b) = map(int, list(input().split(' ')))
n = int(input())
c = [0 for i in range(1002)]
ans = 0
c[a] += 1
c[b] -= 1
for i in range(n):
	(s, f) = map(int, list(input().split(' ')))
	c[s] += 1
	c[f] -= 1
for i in range(1001):
	c[i + 1] += c[i]
	if c[i] > 1:
		ans = 1
print(ans)


(a, b) = map(int, input().split())
t = []
for _ in range(int(input())):
	t += list(map(int, input().split()))
print(1 if sum((i <= a for i in t)) % 2 or sum((i >= b for i in t)) % 2 or sum((a < i and i < b for i in t)) else 0)


(a, b) = map(int, input().split())
n = int(input())
t = 0
for i in range(n):
	(s, f) = map(int, input().split())
	if s < b <= f or s <= a < f:
		t = 1
	elif a <= s and b >= f:
		t = 1
print(t)


time = []
(a, b) = map(int, input().split())
N = int(input())
for i in range(N):
	(s, f) = map(int, input().split())
	for i in range(s, f):
		time.append(i)
for i in range(a, b):
	if i in time:
		print(1)
		break
	elif i == b - 1:
		print(0)


(a, b) = map(int, input().split())
n = int(input())
ans = 0
for i in range(n):
	(A, B) = map(int, input().split())
	if not (A >= b or B <= a):
		ans = 1
print(ans)


def ans(res, L, N):
	for i in range(N):
		count = 0
		for new in res:
			for k in L[i]:
				if new == k:
					count += 1
		if count >= 2:
			return 1
	return 0
(a, b) = map(int, input().split())
res = []
for i in range(a, b + 1, 1):
	res.append(i)
N = int(input())
L = []
for i in range(N):
	l = []
	(s, f) = map(int, input().split())
	for i in range(s, f + 1, 1):
		l.append(i)
	L.append(l)
print(ans(res, L, N))


(a, b) = map(int, input().split())
N = int(input())
s = []
f = []
h = 0
for i in range(N):
	(int_s, int_f) = map(int, input().split())
	s.append(int_s)
	f.append(int_f)
for j in range(N):
	if s[j] <= a and b <= f[j]:
		h += 1
		break
	elif a <= s[j] and f[j] <= b:
		h += 1
		break
	elif s[j] < b < f[j]:
		h += 1
		break
	elif s[j] < a < f[j]:
		h += 1
		break
print(h)


(a, b) = map(int, input().split())
N = int(input())
flag = 0
for _ in range(N):
	(s, f) = map(int, input().split())
	if not (f <= a or b <= s):
		flag = 1
		break
print(1 if flag else 0)


(a, b) = map(int, input().split())
n = int(input())
m = 0
for i in range(n):
	(c, d) = map(int, input().split())
	if d <= a or c >= b:
		pass
	else:
		m = m + 1
if m != 0:
	print(1)
else:
	print(0)


(a, b) = list(map(int, input().split()))
n = int(input())
sf = [list(map(int, input().split())) for _ in range(n)]
ans = 0
li = [True] * 1000
sf.sort()
for i in sf:
	for j in range(i[0], i[1]):
		li[j] = False
for i in range(a, b):
	if li[i] == False:
		ans = 1
		break
print(ans)


(a, b) = map(int, input().split())
N = int(input())
for i in range(N):
	(c, d) = map(int, input().split())
	if d <= a or b <= c:
		continue
	else:
		print('1')
		exit()
print('0')