Alice got a new doll these days. It can even walk!

Alice has built a maze for the doll and wants to test it. The maze is a grid with n rows and m columns. There are k obstacles, the i-th of them is on the cell (x_i, y_i), which means the cell in the intersection of the x_i-th row and the y_i-th column.

However, the doll is clumsy in some ways. It can only walk straight or turn right at most once in the same cell (including the start cell). It cannot get into a cell with an obstacle or get out of the maze.

More formally, there exist 4 directions, in which the doll can look:

  1. The doll looks in the direction along the row from the first cell to the last. While moving looking in this direction the doll will move from the cell (x, y) into the cell (x, y + 1); 
  2. The doll looks in the direction along the column from the first cell to the last. While moving looking in this direction the doll will move from the cell (x, y) into the cell (x + 1, y); 
  3. The doll looks in the direction along the row from the last cell to first. While moving looking in this direction the doll will move from the cell (x, y) into the cell (x, y - 1); 
  4. The doll looks in the direction along the column from the last cell to the first. While moving looking in this direction the doll will move from the cell (x, y) into the cell (x - 1, y). 

.

Standing in some cell the doll can move into the cell in the direction it looks or it can turn right once. Turning right once, the doll switches it's direction by the following rules: 1 → 2, 2 → 3, 3 → 4, 4 → 1. Standing in one cell, the doll can make at most one turn right.

Now Alice is controlling the doll's moves. She puts the doll in of the cell (1, 1) (the upper-left cell of the maze). Initially, the doll looks to the direction 1, so along the row from the first cell to the last. She wants to let the doll walk across all the cells without obstacles exactly once and end in any place. Can it be achieved?

Input

The first line contains three integers n, m and k, separated by spaces (1 ≤ n,m ≤ 10^5, 0 ≤ k ≤ 10^5) — the size of the maze and the number of obstacles.

Next k lines describes the obstacles, the i-th line contains two integer numbers x_i and y_i, separated by spaces (1 ≤ x_i ≤ n,1 ≤ y_i ≤ m), which describes the position of the i-th obstacle.

It is guaranteed that no two obstacles are in the same cell and no obstacle is in cell (1, 1).

Output

Print 'Yes' (without quotes) if the doll can walk across all the cells without obstacles exactly once by the rules, described in the statement.

If it is impossible to walk across the maze by these rules print 'No' (without quotes).

Examples

Input


3 3 2
2 2
2 1


Output


Yes

Input


3 3 2
3 1
2 2


Output


No

Input


3 3 8
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3


Output


Yes

Note

Here is the picture of maze described in the first example:

<image>

In the first example, the doll can walk in this way:

  * The doll is in the cell (1, 1), looks to the direction 1. Move straight; 
  * The doll is in the cell (1, 2), looks to the direction 1. Move straight; 
  * The doll is in the cell (1, 3), looks to the direction 1. Turn right; 
  * The doll is in the cell (1, 3), looks to the direction 2. Move straight; 
  * The doll is in the cell (2, 3), looks to the direction 2. Move straight; 
  * The doll is in the cell (3, 3), looks to the direction 2. Turn right; 
  * The doll is in the cell (3, 3), looks to the direction 3. Move straight; 
  * The doll is in the cell (3, 2), looks to the direction 3. Move straight; 
  * The doll is in the cell (3, 1), looks to the direction 3. The goal is achieved, all cells of the maze without obstacles passed exactly once.

Difficulty: HARD
Tags: Complete search

Data structures

Implementation

Greedy algorithms
Skill types: Complete search

Data structures

Greedy algorithms

Starter code:

Solutions:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
DBG = True and False
BIG = 999999999
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)
(n, m, k) = inm()
hx = {}
hy = {}
cnt = 0
for i in range(k):
	(x, y) = inm()
	x -= 1
	y -= 1
	cnt += 1
	if x in hx:
		hx[x].append(y)
	else:
		hx[x] = [y]
	if y in hy:
		hy[y].append(x)
	else:
		hy[y] = [x]
ddprint(hx)
ddprint(hy)
(x, y) = (0, 0)
dir = 1
if m == 1 or (m > 1 and 0 in hx and (1 in hx[0])):
	dir = 2
minx = miny = -1
maxx = n
maxy = m
while True:
	nx = x
	ny = y
	if dir == 1:
		a = [z for z in hx[x] if y < z and z < maxy] if x in hx else []
		if len(a) == 0:
			ny = maxy - 1
		else:
			a.sort()
			ny = a[0] - 1
		if ny == y:
			break
		cnt += ny - y
		y = ny
		minx = x
		dir = 2
	elif dir == 2:
		a = [z for z in hy[y] if x < z and z < maxx] if y in hy else []
		if len(a) == 0:
			nx = maxx - 1
		else:
			a.sort()
			nx = a[0] - 1
		if nx == x:
			break
		cnt += nx - x
		x = nx
		maxy = y
		dir = 3
	elif dir == 3:
		a = [z for z in hx[x] if miny < z and z < y] if x in hx else []
		if len(a) == 0:
			ny = miny + 1
		else:
			a.sort(reverse=True)
			ny = a[0] + 1
		if ny == y:
			break
		cnt += y - ny
		y = ny
		maxx = x
		dir = 4
	elif dir == 4:
		a = [z for z in hy[y] if minx < z and z < x] if y in hy else []
		if len(a) == 0:
			nx = minx + 1
		else:
			a.sort(reverse=True)
			nx = a[0] + 1
		if nx == x:
			break
		cnt += x - nx
		x = nx
		miny = y
		dir = 1
print('Yes' if cnt == n * m - 1 else 'No')


import sys
(n, m, k) = map(int, input().split())
dr = {}
dc = {}
for i in range(n):
	dr[i] = []
for i in range(m):
	dc[i] = []
for i in range(k):
	(r, c) = map(int, input().split())
	dr[r - 1].append(c - 1)
	dc[c - 1].append(r - 1)
for i in range(n):
	dr[i].sort()
for i in range(m):
	dc[i].sort()

def findDown(r, c, mx):
	global dc
	res = mx
	(lf, rg) = (0, len(dc[c]) - 1)
	while lf <= rg:
		mid = (lf + rg) // 2
		if dc[c][mid] < r:
			lf = mid + 1
		else:
			res = dc[c][mid] - 1
			rg = mid - 1
	return min(res, mx)

def findUp(r, c, mx):
	global dc
	res = mx
	(lf, rg) = (0, len(dc[c]) - 1)
	while lf <= rg:
		mid = (lf + rg) // 2
		if dc[c][mid] > r:
			rg = mid - 1
		else:
			res = dc[c][mid] + 1
			lf = mid + 1
	return max(res, mx)

def findRight(r, c, mx):
	global dr
	res = mx
	(lf, rg) = (0, len(dr[r]) - 1)
	while lf <= rg:
		mid = (lf + rg) // 2
		if dr[r][mid] < c:
			lf = mid + 1
		else:
			res = dr[r][mid] - 1
			rg = mid - 1
	return min(res, mx)

def findLeft(r, c, mx):
	global dr
	res = mx
	(lf, rg) = (0, len(dr[r]) - 1)
	while lf <= rg:
		mid = (lf + rg) // 2
		if dr[r][mid] > c:
			rg = mid - 1
		else:
			res = dr[r][mid] + 1
			lf = mid + 1
	return max(res, mx)
(lb, rb) = (0, m - 1)
(ub, db) = (1, n - 1)
direct = 0
visited = 1
(r, c) = (0, 0)
while True:
	(nr, nc) = (r, c)
	if direct == 0:
		nc = findRight(r, c, rb)
		rb = nc - 1
	elif direct == 1:
		nr = findDown(r, c, db)
		db = nr - 1
	elif direct == 2:
		nc = findLeft(r, c, lb)
		lb = nc + 1
	elif direct == 3:
		nr = findUp(r, c, ub)
		ub = nr + 1
	steps = abs(r - nr) + abs(c - nc)
	if steps == 0 and (r != 0 or c != 0 or direct != 0):
		break
	direct = (direct + 1) % 4
	visited += steps
	(r, c) = (nr, nc)
print('Yes' if n * m - k == visited else 'No')


import sys

def I():
	return sys.stdin.readline().rstrip()
(n, m, k) = map(int, I().split())
(r, c) = (dict(), dict())
for _ in range(k):
	(x, y) = map(int, I().split())
	if x not in r:
		r[x] = []
	r[x].append(y)
	if y not in c:
		c[y] = []
	c[y].append(x)
for v in r.values():
	v.sort()
for v in c.values():
	v.sort()

def bin(a, x):
	i = -1
	j = 1
	while j <= len(a):
		j *= 2
	j //= 2
	while j:
		if i + j < len(a) and a[i + j] <= x:
			i += j
		j //= 2
	return i
dx = [m + 1, n + 1, 0, 0]

def next(x, y, d):
	if d == 0:
		if x in r:
			a = r[x]
			i = bin(a, y) + 1
			if i < len(a):
				dx[d] = min(dx[d], a[i])
		y = dx[d] - 1
		dx[d - 1] = x
	elif d == 1:
		if y in c:
			a = c[y]
			i = bin(a, x) + 1
			if i < len(a):
				dx[d] = min(dx[d], a[i])
		x = dx[d] - 1
		dx[d - 1] = y
	elif d == 2:
		if x in r:
			a = r[x]
			i = bin(a, y)
			if i >= 0:
				dx[d] = max(dx[d], a[i])
		y = dx[d] + 1
		dx[d - 1] = x
	else:
		if y in c:
			a = c[y]
			i = bin(a, x)
			if i >= 0:
				dx[d] = max(dx[d], a[i])
		x = dx[d] + 1
		dx[d - 1] = y
	return (x, y, (d + 1) % 4)
(x, y, d) = (1, 0, 0)
while True:
	(xx, yy, d) = next(x, y, d)
	if x == xx and y == yy:
		break
	k += abs(xx - x) + abs(yy - y)
	(x, y) = (xx, yy)
if k == n * m:
	print('Yes')
else:
	print('No')


(c, r, k) = list(map(int, input().split()))
rows = [[] for i in range(r)]
columns = [[] for i in range(c)]
for i in range(k):
	(x, y) = list(map(int, input().split()))
	x -= 1
	y -= 1
	rows[y].append(x)
	columns[x].append(y)
for v in rows:
	v.sort()
for v in columns:
	v.sort()

def firstGreaterThan(listlist, num, low, high):
	if low > high:
		return -1
	if low == high:
		if listlist[low] > num:
			return listlist[low]
		else:
			return -1
	mid = (low + high) // 2
	if listlist[mid] > num:
		high = mid
	else:
		low = mid + 1
	return firstGreaterThan(listlist, num, low, high)

def lastLessThan(listlist, num, low, high):
	if low > high:
		return -1
	if low == high:
		if listlist[low] < num:
			return listlist[low]
		else:
			return -1
	mid = (low + high + 1) // 2
	if listlist[mid] < num:
		low = mid
	else:
		high = mid - 1
	return lastLessThan(listlist, num, low, high)
xpos = 0
ypos = 0
cellsCovered = 1
dir = 1
firstStep = True
xmin = 0
xmax = c - 1
ymin = 0
ymax = r - 1
while xmin <= xmax and ymin <= ymax:
	targetSquare = -1
	if dir == 1:
		targetSquare = firstGreaterThan(columns[xpos], ypos, 0, len(columns[xpos]) - 1)
	elif dir == 2:
		targetSquare = firstGreaterThan(rows[ypos], xpos, 0, len(rows[ypos]) - 1)
	elif dir == 3:
		targetSquare = lastLessThan(columns[xpos], ypos, 0, len(columns[xpos]) - 1)
	else:
		targetSquare = lastLessThan(rows[ypos], xpos, 0, len(rows[ypos]) - 1)
	if targetSquare == -1:
		if dir == 1:
			targetSquare = ymax
		elif dir == 2:
			targetSquare = xmax
		elif dir == 3:
			targetSquare = ymin
		else:
			targetSquare = xmin
	elif dir == 1:
		targetSquare -= 1
		if targetSquare > ymax:
			targetSquare = ymax
	elif dir == 2:
		targetSquare -= 1
		if targetSquare > xmax:
			targetSquare = xmax
	elif dir == 3:
		targetSquare += 1
		if targetSquare < ymin:
			targetSquare = ymin
	else:
		targetSquare += 1
		if targetSquare < xmin:
			targetSquare = xmin
	if dir % 2 == 0 and targetSquare == xpos or (dir % 2 == 1 and targetSquare == ypos):
		if firstStep:
			firstStep = False
			dir += 1
			if dir == 5:
				dir = 1
			continue
		break
	firstStep = False
	if dir == 1:
		cellsCovered += targetSquare - ypos
		ypos = targetSquare
		ymax = ypos
		xmin += 1
	elif dir == 2:
		cellsCovered += targetSquare - xpos
		xpos = targetSquare
		xmax = xpos
		ymax -= 1
	elif dir == 3:
		cellsCovered += ypos - targetSquare
		ypos = targetSquare
		ymin = ypos
		xmax -= 1
	else:
		cellsCovered += xpos - targetSquare
		xpos = targetSquare
		xmin = xpos
		ymin += 1
	dir += 1
	if dir == 5:
		dir = 1
if cellsCovered == r * c - k:
	print('Yes')
else:
	print('No')


import sys
from collections import deque
(a, b, k) = map(int, input().split())
obsa = [[] for _ in range(a)]
obsb = [[] for _ in range(b)]
for _ in range(k):
	(x, y) = map(int, input().split())
	obsa[x - 1].append(y - 1)
	obsb[y - 1].append(x - 1)
for l in obsa:
	l.sort()
for l in obsb:
	l.sort()
obsa = list(map(deque, obsa))
obsb = list(map(deque, obsb))
totals = a * b - k
bordera = [0, a - 1]
borderb = [0, b - 1]
state = 0
discs = 0
discnew = 0
broken = False
ff = 0
while discs < a * b - k and (not broken):
	if state == 0:
		ff = -1
		while len(obsa[bordera[0]]) > 0:
			f = obsa[bordera[0]].popleft()
			if f >= borderb[0] and f <= borderb[1]:
				ff = f
				break
		if ff > -1:
			borderb[1] = ff - 1
		discnew = borderb[1] - borderb[0] + 1
		bordera[0] += 1
	elif state == 1:
		ff = -1
		while len(obsb[borderb[1]]) > 0:
			f = obsb[borderb[1]].popleft()
			if f >= bordera[0] and f <= bordera[1]:
				ff = f
				break
			if f > bordera[1]:
				break
		if ff > -1:
			bordera[1] = ff - 1
		discnew = bordera[1] - bordera[0] + 1
		borderb[1] -= 1
	elif state == 2:
		ff = -1
		while len(obsa[bordera[1]]) > 0:
			f = obsa[bordera[1]].pop()
			if f >= borderb[0] and f <= borderb[1]:
				ff = f
				break
		if ff > -1:
			borderb[0] = ff + 1
		discnew = borderb[1] - borderb[0] + 1
		bordera[1] -= 1
	elif state == 3:
		ff = -1
		while len(obsb[borderb[0]]) > 0:
			f = obsb[borderb[0]].pop()
			if f >= bordera[0] and f <= bordera[1]:
				ff = f
				break
		if ff > -1:
			bordera[0] = ff + 1
		discnew = bordera[1] - bordera[0] + 1
		borderb[0] += 1
	state = (state + 1) % 4
	if discnew == 0:
		broken = True
	discs += discnew
if broken or discs < a * b - k:
	print('No')
else:
	print('Yes')


def tr(n, m, inp):
	xa = n
	xi = yi = 1
	ya = m
	while True:
		while (xi, ya) in inp:
			for x in range(xi, xa + 1):
				inp.remove((x, ya))
			ya -= 1
			if ya < yi:
				return
		xi += 1
		if xa < xi:
			return
		while (xa, ya) in inp:
			for y in range(yi, ya + 1):
				inp.remove((xa, y))
			xa -= 1
			if xa < xi:
				return
		ya -= 1
		if ya < yi:
			return
		while (xa, yi) in inp:
			for x in range(xi, xa + 1):
				inp.remove((x, yi))
			yi += 1
			if ya < yi:
				return
		xa -= 1
		if xa < xi:
			return
		while (xi, yi) in inp:
			for y in range(yi, ya + 1):
				inp.remove((xi, y))
			xi += 1
			if xa < xi:
				return
		yi += 1
		if ya < yi:
			return
(n, m, k) = map(int, input().split())
inp = {tuple(map(int, input().split())) for _ in range(k)}
try:
	tr(n, m, inp)
	assert not inp
	print('Yes')
except (AssertionError, KeyError):
	print('No')


import sys, math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())
t = 1

def qw(n, m, inp):
	xa = n
	xi = yi = 1
	ya = m
	while True:
		while (xi, ya) in inp:
			for x in range(xi, xa + 1):
				inp.remove((x, ya))
			ya = ya - 1
			if ya < yi:
				return
		xi += 1
		if xa < xi:
			return
		while (xa, ya) in inp:
			for y in range(yi, ya + 1):
				inp.remove((xa, y))
			xa -= 1
			if xa < xi:
				return
		ya -= 1
		if ya < yi:
			return
		while (xa, yi) in inp:
			for x in range(xi, xa + 1):
				inp.remove((x, yi))
			yi += 1
			if ya < yi:
				return
		xa -= 1
		if xa < xi:
			return
		while (xi, yi) in inp:
			for y in range(yi, ya + 1):
				inp.remove((xi, y))
			xi += 1
			if xa < xi:
				return
		yi += 1
		if ya < yi:
			return
for tt in range(t):
	(n, m, k) = invr()
	a = {tuple(invr()) for i in range(k)}
	try:
		qw(n, m, a)
		assert not a
		if k < 1 and n < 1:
			print('No')
		else:
			print('Yes')
	except:
		print('No')


import sys
from bisect import bisect
input = sys.stdin.readline

def r1():
	return int(input())

def rm():
	return map(int, input().split())
(n, m, k) = rm()
(rw, cl) = ({}, {})
for i in range(k):
	(x, y) = rm()
	if x not in rw:
		rw[x] = []
	rw[x].append(y)
	if y not in cl:
		cl[y] = []
	cl[y].append(x)
for v in rw.values():
	v.sort()
for v in cl.values():
	v.sort()
(l, r, u, d) = (1, m, 1, n)
dr = 1
(x, y) = (1, 1)
s = 1
while l <= r and u <= d:
	if dr == 1:
		if x in rw:
			f = bisect(rw[x], y)
			if f < len(rw[x]):
				r = min(r, rw[x][f] - 1)
		s += r - y
		y = r
		u += 1
	elif dr == 3:
		if x in rw:
			f = bisect(rw[x], y)
			if f > 0:
				l = max(l, rw[x][f - 1] + 1)
		s += y - l
		y = l
		d -= 1
	elif dr == 2:
		if y in cl:
			f = bisect(cl[y], x)
			if f < len(cl[y]):
				d = min(d, cl[y][f] - 1)
		s += d - x
		x = d
		r -= 1
	elif dr == 0:
		if y in cl:
			f = bisect(cl[y], x)
			if f > 0:
				u = max(u, cl[y][f - 1] + 1)
		s += x - u
		x = u
		l += 1
	dr = (dr + 1) % 4
print('YES' if s == n * m - k else 'NO')