You will be given a square chess board with one queen and a number of obstacles placed on it.  Determine how many squares the queen can attack.  

A queen is standing on an $n\times n$ chessboard. The chess board's rows are numbered from $\mbox{I}$ to $n$, going from bottom to top.  Its columns are numbered from $\mbox{I}$ to $n$, going from left to right. Each square is referenced by a tuple, $(r,c)$, describing the row, $\textbf{r}$, and column, $\textbf{C}$, where the square is located.

The queen is standing at position $(r_q,c_q)$.  In a single move, she can attack any square in any of the eight directions (left, right, up, down, and the four diagonals). In the diagram below, the green circles denote all the cells the queen can attack from $(4,4)$: 

There are obstacles on the chessboard, each preventing the queen from attacking any square beyond it on that path. For example, an obstacle at location $(3,5)$ in the diagram above prevents the queen from attacking cells $(3,5)$, $(2,6)$, and $(1,7)$:

Given the queen's position and the locations of all the obstacles, find and print the number of squares the queen can attack from her position at $(r_q,c_q)$.  In the board above, there are $24$ such squares.

Function Description  

Complete the queensAttack function in the editor below.   

queensAttack has the following parameters: 

- int n: the number of rows and columns in the board 

- nt k: the number of obstacles on the board 

- int r_q: the row number of the queen's position 

- int c_q: the column number of the queen's position 

- int obstacles[k][2]: each element is an array of $2$ integers, the row and column of an obstacle  

Returns 

- int: the number of squares the queen can attack   

Input Format

The first line contains two space-separated integers $n$ and $\boldsymbol{\mbox{k}}$, the length of the board's sides and the number of obstacles. 

The next line contains two space-separated integers $r_q$ and $c_{q}$, the queen's row and column position. 

Each of the next $\boldsymbol{\mbox{k}}$ lines contains two space-separated integers $r[i]$ and $c[i]$, the row and column position of $obstacle[i]$.       

Constraints

$0<n\leq10^5$
$0\leq k\leq10^5$
A single cell may contain more than one obstacle.
There will never be an obstacle at the position where the queen is located.

Subtasks

For $30\%$ of the maximum score: 

$0<n\leq100$
$0\leq k\leq100$

For $55\%$ of the maximum score: 

$0<n\leq1000$
$0\leq k\leq10^5$

Sample Input 0
4 0
4 4

Sample Output 0
9

Explanation 0

The queen is standing at position $(4,4)$ on a $4\times4$ chessboard with no obstacles:

Sample Input 1
5 3
4 3
5 5
4 2
2 3

Sample Output 1
10

Explanation 1

The queen is standing at position $(4,3)$ on a $5\times5$ chessboard with $k=3$ obstacles:

The number of squares she can attack from that position is $10$.

Sample Input 2
1 0
1 1

Sample Output 2
0

Explanation 2

Since there is only one square, and the queen is on it, the queen can move 0 squares.

Difficulty: MEDIUM
Tags: Implementation

Starter code:

Solutions:
(n, k) = map(int, input().split())
(rQueen, cQueen) = map(int, input().split())
obstacles = set()
for _ in range(k):
	(rObs, cObs) = map(int, input().split())
	obstacles.add((rObs, cObs))
ans = 0
(r, c) = (rQueen, cQueen - 1)
while c > 0:
	if (r, c) in obstacles:
		break
	(ans, c) = (ans + 1, c - 1)
(r, c) = (rQueen, cQueen + 1)
while c <= n:
	if (r, c) in obstacles:
		break
	(ans, c) = (ans + 1, c + 1)
(r, c) = (rQueen + 1, cQueen)
while r <= n:
	if (r, c) in obstacles:
		break
	(ans, r) = (ans + 1, r + 1)
(r, c) = (rQueen - 1, cQueen)
while r > 0:
	if (r, c) in obstacles:
		break
	(ans, r) = (ans + 1, r - 1)
(r, c) = (rQueen + 1, cQueen + 1)
while r <= n and c <= n:
	if (r, c) in obstacles:
		break
	(ans, r, c) = (ans + 1, r + 1, c + 1)
(r, c) = (rQueen + 1, cQueen - 1)
while r <= n and c > 0:
	if (r, c) in obstacles:
		break
	(ans, r, c) = (ans + 1, r + 1, c - 1)
(r, c) = (rQueen - 1, cQueen - 1)
while r > 0 and c > 0:
	if (r, c) in obstacles:
		break
	(ans, r, c) = (ans + 1, r - 1, c - 1)
(r, c) = (rQueen - 1, cQueen + 1)
while r > 0 and c <= n:
	if (r, c) in obstacles:
		break
	(ans, r, c) = (ans + 1, r - 1, c + 1)
print(ans)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
obs = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obs.add((rObstacle, cObstacle))
ans = 0
for dx in range(-1, 2, 1):
	for dy in range(-1, 2, 1):
		if dx == 0 and dy == 0:
			continue
		x = rQueen + dx
		y = cQueen + dy
		while x <= n and x > 0 and (y <= n) and (y > 0):
			if (x, y) in obs:
				break
			ans += 1
			x += dx
			y += dy
print(ans)


(n, k) = map(int, input().split())
(r, c) = map(int, input().split())
left = (r, 0)
right = (r, n + 1)
up = (n + 1, c)
down = (0, c)
ru = (r + n + 1 - c, n + 1) if r < c else (n + 1, c - r + n + 1)
rd = (r + c - n - 1, n + 1) if r + c > n else (0, c + r)
lu = (n + 1, c + r - n - 1) if r + c > n else (r + c, 0)
ld = (0, c - r) if r < c else (r - c, 0)
for _ in range(k):
	(x, y) = map(int, input().split())
	if y == c:
		if x < r:
			if down[0] < x:
				down = (x, y)
		elif up[0] > x:
			up = (x, y)
	elif x == r:
		if y < c:
			if left[1] < y:
				left = (x, y)
		elif right[1] > y:
			right = (x, y)
	elif r + c == x + y:
		if x < r:
			if rd[0] < x:
				rd = (x, y)
		elif lu[0] > x:
			lu = (x, y)
	elif r - c == x - y:
		if x < r:
			if ld[0] < x:
				ld = (x, y)
		elif ru[0] > x:
			ru = (x, y)
print(right[1] - left[1] + up[0] - down[0] + lu[0] - rd[0] + ru[0] - ld[0] - 8)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
ObList = []
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	ObList.append((rObstacle, cObstacle))
ObSet = set(ObList)
Delta = [(0, 1), (1, 1), (1, 0), (0, -1), (-1, -1), (-1, 0), (1, -1), (-1, 1)]
Count = 0
for shift in Delta:
	Pos = (rQueen, cQueen)
	while Pos[0] + shift[0] >= 1 and Pos[0] + shift[0] <= n and (Pos[1] + shift[1] >= 1) and (Pos[1] + shift[1] <= n):
		Pos = (Pos[0] + shift[0], Pos[1] + shift[1])
		if Pos in ObSet:
			break
		Count += 1
print(Count)


(n, obstacle_count) = [int(p) for p in input().split()]
(rows, cols) = (n, n)
(queen_row, queen_col) = [int(p) for p in input().split()]
obstacles = set()
for _ in range(obstacle_count):
	(x, y) = [int(p) for p in input().split()]
	obstacles.add((x, y))
moves = 0
for col in reversed(range(1, queen_col)):
	if (queen_row, col) in obstacles:
		break
	moves += 1
for col in range(queen_col + 1, rows + 1):
	if (queen_row, col) in obstacles:
		break
	moves += 1
for row in range(queen_row + 1, rows + 1):
	if (row, queen_col) in obstacles:
		break
	moves += 1
for row in reversed(range(1, queen_row)):
	if (row, queen_col) in obstacles:
		break
	moves += 1
(cur_col, cur_row) = (queen_col, queen_row)
while True:
	cur_col -= 1
	cur_row -= 1
	if (cur_row, cur_col) in obstacles or cur_row < 1 or cur_col < 1:
		break
	moves += 1
(cur_col, cur_row) = (queen_col, queen_row)
while True:
	cur_col += 1
	cur_row -= 1
	if (cur_row, cur_col) in obstacles or cur_row < 1 or cur_col > cols:
		break
	moves += 1
(cur_col, cur_row) = (queen_col, queen_row)
while True:
	cur_col -= 1
	cur_row += 1
	if (cur_row, cur_col) in obstacles or cur_row > rows or cur_col < 1:
		break
	moves += 1
(cur_col, cur_row) = (queen_col, queen_row)
while True:
	cur_col += 1
	cur_row += 1
	if (cur_row, cur_col) in obstacles or cur_row > rows or cur_col > cols:
		break
	moves += 1
print(moves)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
(x, y) = (rQueen, cQueen)
x -= 1
y -= 1
ss = [min(y, x), x, min(n - y - 1, x), n - y - 1, min(n - y - 1, n - x - 1), n - x - 1, min(n - x - 1, y), y]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	(r, c) = (rObstacle - 1, cObstacle - 1)
	if r == x:
		if c < y:
			ss[7] = min(ss[7], y - c - 1)
		else:
			ss[3] = min(ss[3], c - y - 1)
	elif c == y:
		if r < x:
			ss[1] = min(ss[1], x - r - 1)
		else:
			ss[5] = min(ss[5], r - x - 1)
	elif x - r == y - c:
		if x > r:
			ss[0] = min(ss[0], x - r - 1)
		else:
			ss[4] = min(ss[4], r - x - 1)
	elif x - r == c - y:
		if x > r:
			ss[2] = min(ss[2], x - r - 1)
		else:
			ss[6] = min(ss[6], r - x - 1)
print(sum(ss))


(n, k) = map(int, input().split())
(a, b) = map(int, input().split())
block = {}
for i in range(k):
	(x, y) = map(int, input().split())
	block[x, y] = True
dx = [0, 1, 1, 1, 0, -1, -1, -1]
dy = [1, 1, 0, -1, -1, -1, 0, 1]
ans = 0
for d in range(8):
	(x, y) = (a, b)
	while 1 <= x and x <= n and (1 <= y) and (y <= n):
		ans += 1
		x += dx[d]
		y += dy[d]
		if (x, y) in block:
			break
print(ans - 8)


(n, k) = [int(a) for a in input().split()]
(r, c) = [int(a) for a in input().split()]
(n, e, s, w) = (n - r, n - c, r - 1, c - 1)
(ne, se, sw, nw) = (min(n, e), min(s, e), min(s, w), min(n, w))
for _ in range(k):
	(ro, co) = [int(a) for a in input().split()]
	if ro == r:
		if co < c:
			w = min(w, c - co - 1)
		else:
			e = min(e, co - c - 1)
	elif co == c:
		if ro < r:
			s = min(s, r - ro - 1)
		else:
			n = min(n, ro - r - 1)
	elif ro - co == r - c:
		if ro < r:
			sw = min(sw, r - ro - 1)
		else:
			ne = min(ne, ro - r - 1)
	elif ro + co == r + c:
		if ro < r:
			se = min(se, r - ro - 1)
		else:
			nw = min(nw, ro - r - 1)
print(n + e + s + w + ne + se + sw + nw)


(n, k) = list(map(int, input().split()))
(r, c) = list(map(int, input().split()))
obs = set()
for _ in range(k):
	(a, b) = list(map(int, input().split()))
	obs.add((a, b))
ct = 0
for i in range(-1, 2):
	for j in range(-1, 2):
		if i == 0 and j == 0:
			continue
		x = r + i
		y = c + j
		while x >= 1 and y >= 1 and (x <= n) and (y <= n) and ((x, y) not in obs):
			ct += 1
			x += i
			y += j
print(ct)


import sys
(n, k) = input().strip().split(' ')
(n, k) = (int(n), int(k))
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = (int(rQueen), int(cQueen))
L = 0
R = 1
U = 2
D = 3
LD = 4
LU = 5
RU = 6
RD = 7
dist = [cQueen - 1, n - cQueen, n - rQueen, rQueen - 1]
dist.append(min(dist[L], dist[D]))
dist.append(min(dist[L], dist[U]))
dist.append(min(dist[R], dist[U]))
dist.append(min(dist[R], dist[D]))
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = (int(rObstacle), int(cObstacle))
	idx = None
	if rObstacle == rQueen:
		if cObstacle > cQueen:
			idx = R
			val = cObstacle - cQueen - 1
		else:
			idx = L
			val = cQueen - cObstacle - 1
	elif cObstacle == cQueen:
		if rObstacle > rQueen:
			idx = U
			val = rObstacle - rQueen - 1
		else:
			idx = D
			val = rQueen - rObstacle - 1
	else:
		dr = rObstacle - rQueen
		dc = cObstacle - cQueen
		val = abs(dr)
		if val == abs(dc):
			val -= 1
			if dr > 0:
				if dc > 0:
					idx = RU
				else:
					idx = LU
			elif dc > 0:
				idx = RD
			else:
				idx = LD
	if idx is not None:
		dist[idx] = min(dist[idx], val)
print(sum(dist))


(n, k) = (int(x) for x in input().split())
(rQ, cQ) = (int(x) for x in input().split())
(left, right) = (cQ - 1, n - cQ)
(top, bottom) = (n - rQ, rQ - 1)
(topleft, bottomright) = (min(top, left), min(bottom, right))
(topright, bottomleft) = (min(top, right), min(bottom, left))
for _ in range(k):
	(r, c) = (int(x) for x in input().split())
	if r == rQ:
		if c < cQ:
			left = min(left, cQ - c - 1)
		else:
			right = min(right, c - cQ - 1)
	if c == cQ:
		if r < rQ:
			bottom = min(bottom, rQ - r - 1)
		else:
			top = min(top, r - rQ - 1)
	if r - rQ == cQ - c:
		if r < rQ:
			bottomright = min(bottomright, rQ - r - 1)
		else:
			topleft = min(topleft, r - rQ - 1)
	if r - rQ == c - cQ:
		if r < rQ:
			bottomleft = min(bottomleft, rQ - r - 1)
		else:
			topright = min(topright, r - rQ - 1)
print(top + bottom + left + right + topleft + bottomright + topright + bottomleft)


(n, k) = map(int, input().strip().split(' '))
(rQueen, cQueen) = map(int, input().strip().split(' '))
obs = [list(map(int, input().strip().split(' '))) for i in range(k)]

def lim(i):
	if i < 0:
		return 0
	else:
		return n + 1

def border(i, j, rQueen, cQueen):
	res = []
	if i == 0:
		res.append([rQueen, lim(j)])
	elif j == 0:
		res.append([lim(i), cQueen])
	else:
		res.append([lim(i), cQueen + (lim(i) - rQueen) * i * j])
		res.append([rQueen + (lim(j) - cQueen) * i * j, lim(j)])
	return res

def test(i, j, x1, y1, x2, y2):
	if i == 0:
		ifx = x2 == x1
		ify = (y2 - y1) * j > 0
	elif j == 0:
		ifx = (x2 - x1) * i > 0
		ify = y2 == y1
	else:
		ifx = (x2 - x1) * i > 0
		ify = (y2 - y1) * j == (x2 - x1) * i
		ifz = True
	return ifx and ify

def delta(x1, y1, x2, y2):
	return max(abs(x2 - x1), abs(y2 - y1))

def count(i, j):
	temp = list(filter(lambda z: test(i, j, rQueen, cQueen, z[0], z[1]), obs))
	temp.extend(border(i, j, rQueen, cQueen))
	d = min(map(lambda z: delta(rQueen, cQueen, z[0], z[1]), temp))
	return d - 1
print(sum([count(i, j) for i in range(-1, 2) for j in range(-1, 2) if i or j]))


import sys

def onDiago(x1, y1, x2, y2):
	if abs(y1 - y2) == abs(x1 - x2):
		return True
	else:
		return False
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
res = cQueen - 1
res += n - cQueen
res += n - rQueen
res += rQueen - 1
res += min(cQueen - 1, n - rQueen)
res += min(cQueen - 1, rQueen - 1)
res += min(n - cQueen, n - rQueen)
res += min(n - cQueen, rQueen - 1)
queriesToDo = {}
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle < cQueen:
			if 'left' in queriesToDo:
				if cObstacle > queriesToDo['left'][1]:
					queriesToDo['left'] = [rObstacle, cObstacle]
			else:
				queriesToDo['left'] = [rObstacle, cObstacle]
		elif 'right' in queriesToDo:
			if cObstacle < queriesToDo['right'][1]:
				queriesToDo['right'] = [rObstacle, cObstacle]
		else:
			queriesToDo['right'] = [rObstacle, cObstacle]
	elif cObstacle == cQueen:
		if rObstacle < rQueen:
			if 'down' in queriesToDo:
				if rObstacle > queriesToDo['down'][0]:
					queriesToDo['down'] = [rObstacle, cObstacle]
			else:
				queriesToDo['down'] = [rObstacle, cObstacle]
		elif 'up' in queriesToDo:
			if rObstacle < queriesToDo['up'][0]:
				queriesToDo['up'] = [rObstacle, cObstacle]
		else:
			queriesToDo['up'] = [rObstacle, cObstacle]
	elif onDiago(rQueen, cQueen, rObstacle, cObstacle):
		if rObstacle > rQueen and cObstacle < cQueen:
			if 'leftUp' in queriesToDo:
				if cObstacle > queriesToDo['leftUp'][1]:
					queriesToDo['leftUp'] = [rObstacle, cObstacle]
			else:
				queriesToDo['leftUp'] = [rObstacle, cObstacle]
		if rObstacle < rQueen and cObstacle < cQueen:
			if 'leftDown' in queriesToDo:
				if cObstacle > queriesToDo['leftDown'][1]:
					queriesToDo['leftDown'] = [rObstacle, cObstacle]
			else:
				queriesToDo['leftDown'] = [rObstacle, cObstacle]
		if rObstacle > rQueen and cObstacle > cQueen:
			if 'rightUp' in queriesToDo:
				if cObstacle < queriesToDo['rightUp'][1]:
					queriesToDo['rightUp'] = [rObstacle, cObstacle]
			else:
				queriesToDo['rightUp'] = [rObstacle, cObstacle]
		if rObstacle < rQueen and cObstacle > cQueen:
			if 'rightDown' in queriesToDo:
				if cObstacle < queriesToDo['rightDown'][1]:
					queriesToDo['rightDown'] = [rObstacle, cObstacle]
			else:
				queriesToDo['rightDown'] = [rObstacle, cObstacle]
for toDo in queriesToDo.keys():
	(rObstacle, cObstacle) = (queriesToDo[toDo][0], queriesToDo[toDo][1])
	if toDo == 'right':
		res -= n - cObstacle + 1
	if toDo == 'left':
		res -= cObstacle
	if toDo == 'up':
		res -= n - rObstacle + 1
	if toDo == 'down':
		res -= rObstacle
	if toDo == 'leftUp':
		res -= min(cQueen - 1, n - rQueen) - abs(rObstacle - rQueen) + 1
	if toDo == 'rightUp':
		res -= min(n - cQueen, n - rQueen) - abs(rObstacle - rQueen) + 1
	if toDo == 'leftDown':
		res -= min(cQueen - 1, rQueen - 1) - abs(rObstacle - rQueen) + 1
	if toDo == 'rightDown':
		res -= min(n - cQueen, rQueen - 1) - abs(rObstacle - rQueen) + 1
print(res)


import sys

def isOnBoard(n, pos):
	if 1 <= pos[0] <= n and 1 <= pos[1] <= n:
		return True
	else:
		return False
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
queenpos = (int(rQueen), int(cQueen))
obstacles = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	pair = (int(rObstacle), int(cObstacle))
	obstacles.add(pair)
count = 0
directions = ([0, 1], [0, -1], [1, 0], [1, 1], [1, -1], [-1, -1], [-1, 0], [-1, 1])
for d in directions:
	pos = queenpos
	while True:
		pos = (pos[0] + d[0], pos[1] + d[1])
		if not isOnBoard(n, pos) or pos in obstacles:
			break
		count += 1
print(count)


(n, k) = map(int, input().split())
(rq, cq) = map(int, input().split())
moves = {'n': n - rq, 'nw': min(n - rq, cq - 1), 'ne': min(n - rq, n - cq), 's': rq - 1, 'sw': min(rq - 1, cq - 1), 'se': min(rq - 1, n - cq), 'w': cq - 1, 'e': n - cq}
for _ in range(k):
	(r, c) = map(int, input().split())
	if c == cq:
		if r > rq:
			moves['n'] = min(r - rq - 1, moves['n'])
		else:
			moves['s'] = min(rq - r - 1, moves['s'])
	elif r == rq:
		if c > cq:
			moves['e'] = min(c - cq - 1, moves['e'])
		else:
			moves['w'] = min(cq - c - 1, moves['w'])
	elif c - r == cq - rq:
		if c < cq and r < rq:
			moves['sw'] = min(min(cq - c - 1, rq - r - 1), moves['sw'])
		elif c > cq and r > rq:
			moves['ne'] = min(min(c - cq - 1, r - rq - 1), moves['ne'])
	elif c + r == cq + rq:
		if c < cq and r > rq:
			moves['nw'] = min(min(r - rq - 1, cq - c - 1), moves['nw'])
		elif c > cq and r < rq:
			moves['se'] = min(min(rq - r - 1, c - cq - 1), moves['se'])
print(sum(moves.values()))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
mem = [cQueen - 1, min(cQueen - 1, n - rQueen), n - rQueen, min(n - cQueen, n - rQueen), n - cQueen, min(n - cQueen, rQueen - 1), rQueen - 1, min(rQueen - 1, cQueen - 1)]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle < cQueen:
			if cQueen - cObstacle - 1 < mem[0]:
				mem[0] = cQueen - cObstacle - 1
		elif cObstacle - cQueen - 1 < mem[4]:
			mem[4] = cObstacle - cQueen - 1
	if cObstacle == cQueen:
		if rObstacle < rQueen:
			if rQueen - rObstacle - 1 < mem[6]:
				mem[6] = rQueen - rObstacle - 1
		elif rObstacle - rQueen - 1 < mem[2]:
			mem[2] = rObstacle - rQueen - 1
	if abs(cObstacle - cQueen) == abs(rObstacle - rQueen):
		tmp = abs(cObstacle - cQueen) - 1
		if cObstacle > cQueen:
			if rObstacle > rQueen:
				if tmp < mem[3]:
					mem[3] = tmp
			elif tmp < mem[5]:
				mem[5] = tmp
		elif rObstacle > rQueen:
			if tmp < mem[1]:
				mem[1] = tmp
		elif tmp < mem[7]:
			mem[7] = tmp
print(sum(mem))


(size, num_obstacles) = [int(x) for x in input().split()]
queen = [int(x) for x in input().split()]
obstacles = set()
for _ in range(num_obstacles):
	obstacles.add(tuple([int(x) for x in input().split()]))
attacks = 0
for dir in [[-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1]]:
	q2 = tuple(queen)
	for _ in range(size):
		q2 = (q2[0] + dir[0], q2[1] + dir[1])
		if not (0 < q2[0] <= size and 0 < q2[1] <= size):
			break
		if q2 in obstacles:
			break
		attacks += 1
print(attacks)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
queen = {}
queen['L'] = cQueen - 1
queen['R'] = n - cQueen
queen['D'] = rQueen - 1
queen['U'] = n - rQueen
queen['UL'] = min(queen['L'], queen['U'])
queen['DL'] = min(queen['L'], queen['D'])
queen['UR'] = min(queen['R'], queen['U'])
queen['DR'] = min(queen['R'], queen['D'])
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle < cQueen:
			queen['L'] = min(queen['L'], cQueen - cObstacle - 1)
		else:
			queen['R'] = min(queen['R'], cObstacle - cQueen - 1)
	elif cObstacle == cQueen:
		if rObstacle < rQueen:
			queen['D'] = min(queen['D'], rQueen - rObstacle - 1)
		else:
			queen['U'] = min(queen['U'], rObstacle - rQueen - 1)
	elif cObstacle - cQueen == rObstacle - rQueen:
		if rObstacle < rQueen:
			queen['DL'] = min(queen['DL'], rQueen - rObstacle - 1)
		else:
			queen['UR'] = min(queen['UR'], rObstacle - rQueen - 1)
	elif cObstacle - cQueen == rQueen - rObstacle:
		if rObstacle < rQueen:
			queen['DR'] = min(queen['DR'], rQueen - rObstacle - 1)
		else:
			queen['UL'] = min(queen['UL'], rObstacle - rQueen - 1)
print(sum(queen.values()))


import sys

def get_queen_moves(r, c, n):
	moves = set()
	for i in range(1, n):
		if r + i < n:
			moves.add((r + i, c))
		else:
			break
	for i in range(1, n):
		if r - i > -1:
			moves.add((r - i, c))
		else:
			break
	for i in range(1, n):
		if c + i < n:
			moves.add((r, c + i))
		else:
			break
	for i in range(1, n):
		if c - i > -1:
			moves.add((r, c - i))
		else:
			break
	for i in range(1, n):
		if r + i < n and c + i < n:
			moves.add((r + i, c + i))
		else:
			break
	for i in range(1, n):
		if r - i > -1 and c - i > -1:
			moves.add((r - i, c - i))
		else:
			break
	for i in range(1, n):
		if r + i < n and c - i > -1:
			moves.add((r + i, c - i))
		else:
			break
	for i in range(1, n):
		if r - i > -1 and c + i < n:
			moves.add((r - i, c + i))
		else:
			break
	return moves

def remove_blocked_cells(r, c, rb, cb, n, moves):
	if (rb, cb) in moves:
		if rb == r and cb > c:
			for i in range(cb, n):
				if (r, i) in moves:
					moves.remove((r, i))
				else:
					break
		elif rb == r and cb < c:
			for i in range(cb, -1, -1):
				if (r, i) in moves:
					moves.remove((r, i))
				else:
					break
		elif cb == c and rb > r:
			for i in range(rb, n):
				if (i, c) in moves:
					moves.remove((i, c))
				else:
					break
		elif cb == c and rb < r:
			for i in range(rb, -1, -1):
				if (i, c) in moves:
					moves.remove((i, c))
				else:
					break
		elif cb > c and rb > r:
			for i in range(n):
				if (rb + i, cb + i) in moves:
					moves.remove((rb + i, cb + i))
				else:
					break
		elif cb < c and rb < r:
			for i in range(n):
				if (rb - i, cb - i) in moves:
					moves.remove((rb - i, cb - i))
				else:
					break
		elif cb > c and rb < r:
			for i in range(n):
				if (rb - i, cb + i) in moves:
					moves.remove((rb - i, cb + i))
				else:
					break
		elif cb < c and rb > r:
			for i in range(n):
				if (rb + i, cb - i) in moves:
					moves.remove((rb + i, cb - i))
				else:
					break
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen) - 1, int(cQueen) - 1]
moves = get_queen_moves(rQueen, cQueen, n)
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle) - 1, int(cObstacle) - 1]
	remove_blocked_cells(rQueen, cQueen, rObstacle, cObstacle, n, moves)
	if not moves:
		break
print(len(moves))


(n, obs) = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
board = {}
for i in range(obs):
	(x, y) = [int(x) for x in input().split()]
	board[x, y] = 1
c = 0
(x, y) = (q[0], q[1])
while x + 1 <= n:
	if (x + 1, y) not in board:
		x += 1
		c += 1
	else:
		break
(x, y) = (q[0], q[1])
while x - 1 > 0:
	if (x - 1, y) not in board:
		x -= 1
		c += 1
	else:
		break
(x, y) = (q[0], q[1])
while y - 1 > 0:
	if (x, y - 1) not in board:
		y -= 1
		c += 1
	else:
		break
(x, y) = (q[0], q[1])
while y + 1 <= n:
	if (x, y + 1) not in board:
		y += 1
		c += 1
	else:
		break
(x, y) = (q[0], q[1])
while x + 1 <= n and y - 1 > 0:
	if (x + 1, y - 1) not in board:
		x += 1
		y -= 1
		c += 1
	else:
		break
(x, y) = (q[0], q[1])
while x + 1 <= n and y + 1 <= n:
	if (x + 1, y + 1) not in board:
		x += 1
		y += 1
		c += 1
	else:
		break
(x, y) = (q[0], q[1])
while x - 1 > 0 and y - 1 > 0:
	if (x - 1, y - 1) not in board:
		x -= 1
		y -= 1
		c += 1
	else:
		break
(x, y) = (q[0], q[1])
while x - 1 > 0 and y + 1 <= n:
	if (x - 1, y + 1) not in board:
		x -= 1
		y += 1
		c += 1
	else:
		break
print(c)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
l = cQueen - 1
r = n - cQueen
d = rQueen - 1
u = n - rQueen
ur = min(u, r)
ul = min(u, l)
dl = min(d, l)
dr = min(d, r)
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle > cQueen:
			r = min(cObstacle - cQueen - 1, r)
		else:
			l = min(cQueen - cObstacle - 1, l)
	if cObstacle == cQueen:
		if rObstacle > rQueen:
			u = min(rObstacle - rQueen - 1, u)
		else:
			d = min(rQueen - rObstacle - 1, d)
	if abs(rObstacle - rQueen) == abs(cObstacle - cQueen):
		if rObstacle > rQueen:
			if cObstacle > cQueen:
				ur = min(ur, rObstacle - rQueen - 1)
			else:
				ul = min(ul, rObstacle - rQueen - 1)
		elif cObstacle > cQueen:
			dr = min(dr, rQueen - rObstacle - 1)
		else:
			dl = min(dl, rQueen - rObstacle - 1)
print(l + r + d + u + dl + dr + ul + ur)


import sys

def solve(inp, n, k):
	(q_x, q_y) = [int(x) for x in inp.readline().strip().split()]
	closest = {'N': n, 'S': n, 'E': n, 'W': n, 'NE': n, 'NW': n, 'SE': n, 'SW': n}
	default_value = {'N': n - q_y, 'S': q_y - 1, 'E': n - q_x, 'W': q_x - 1, 'SW': min(q_y - 1, q_x - 1), 'NW': min(n - q_y, q_x - 1), 'SE': min(q_y - 1, n - q_x), 'NE': min(n - q_y, n - q_x)}
	for obstacle in range(k):
		(x, y) = [int(x) for x in inp.readline().strip().split()]
		if x == q_x and y > q_y and (y - q_y < closest['N']):
			closest['N'] = y - q_y
		if x == q_x and y < q_y and (q_y - y < closest['S']):
			closest['S'] = q_y - y
		if y == q_y and x < q_x and (q_x - x < closest['W']):
			closest['W'] = q_x - x
		if y == q_y and x > q_x and (x - q_x < closest['E']):
			closest['E'] = x - q_x
		if q_x + q_y == x + y and x > q_x and (x - q_x < closest['SE']):
			closest['SE'] = x - q_x
		if q_x + q_y == x + y and q_x > x and (q_x - x < closest['NW']):
			closest['NW'] = q_x - x
		if q_x - q_y == x - y and q_x > x and (q_x - x < closest['SW']):
			closest['SW'] = q_x - x
		if q_x - q_y == x - y and x > q_x and (x - q_x < closest['NE']):
			closest['NE'] = x - q_x
	sum = 0
	for direction in closest:
		if closest[direction] < n:
			sum += closest[direction] - 1
		else:
			sum += default_value[direction]
	print(sum)

def main(inp=sys.stdin):
	(n, k) = [int(x) for x in inp.readline().strip().split()]
	solve(inp, n, k)
main()


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
NV = n - rQueen
EV = n - cQueen
SV = rQueen - 1
WV = cQueen - 1
NEV = min(NV, EV)
SEV = min(SV, EV)
SWV = min(SV, WV)
NWV = min(NV, WV)
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle < cQueen:
			WV = min(WV, cQueen - cObstacle - 1)
		elif cObstacle > cQueen:
			EV = min(EV, cObstacle - cQueen - 1)
	elif cObstacle == cQueen:
		if rObstacle < rQueen:
			SV = min(SV, rQueen - rObstacle - 1)
		elif rObstacle > rQueen:
			NV = min(NV, rObstacle - rQueen - 1)
	elif cObstacle - rObstacle == cQueen - rQueen:
		if rObstacle < rQueen:
			SWV = min(SWV, rQueen - rObstacle - 1)
		elif rObstacle > rQueen:
			NEV = min(NEV, rObstacle - rQueen - 1)
	elif cObstacle + rObstacle == cQueen + rQueen:
		if rObstacle < rQueen:
			SEV = min(SEV, rQueen - rObstacle - 1)
		elif rObstacle > rQueen:
			NWV = min(NWV, rObstacle - rQueen - 1)
print(sum([NV, EV, SV, WV, NEV, SEV, SWV, NWV]))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
sag = n - cQueen
yukari = n - rQueen
sol = cQueen - 1
asagi = rQueen - 1
SagYukari = min(sag, yukari)
SolYukari = min(sol, yukari)
SolAsagi = min(sol, asagi)
SagAsagi = min(sag, asagi)
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen and cObstacle > cQueen:
		if cObstacle - cQueen - 1 < sag:
			sag = cObstacle - cQueen - 1
	elif (rObstacle > rQueen and cObstacle > cQueen) and rObstacle - rQueen == cObstacle - cQueen:
		if rObstacle - rQueen - 1 < SagYukari:
			SagYukari = rObstacle - rQueen - 1
	elif cObstacle == cQueen and rObstacle > rQueen:
		if rObstacle - rQueen - 1 < yukari:
			yukari = rObstacle - rQueen - 1
	elif (rObstacle > rQueen and cObstacle < cQueen) and rObstacle - rQueen == cQueen - cObstacle:
		if rObstacle - rQueen - 1 < SolYukari:
			SolYukari = rObstacle - rQueen - 1
	elif rObstacle == rQueen and cObstacle < cQueen:
		if cQueen - cObstacle - 1 < sol:
			sol = cQueen - cObstacle - 1
	elif (rObstacle < rQueen and cObstacle < cQueen) and rQueen - rObstacle == cQueen - cObstacle:
		if rQueen - rObstacle - 1 < SolAsagi:
			SolAsagi = rQueen - rObstacle - 1
	elif cObstacle == cQueen and rObstacle < rQueen:
		if rQueen - rObstacle - 1 < asagi:
			asagi = rQueen - rObstacle - 1
	elif (rObstacle < rQueen and cObstacle > cQueen) and rQueen - rObstacle == cObstacle - cQueen:
		if rQueen - rObstacle - 1 < SagAsagi:
			SagAsagi = rQueen - rObstacle - 1
print(sag + SagYukari + yukari + SolYukari + sol + SolAsagi + asagi + SagAsagi)


import sys

def calc_diff(p1, p2):
	return [p1[0] - p2[0], p1[1] - p2[1]]

def is_reachable(diff):
	return abs(diff[0]) == abs(diff[1]) or diff[0] == 0 or diff[1] == 0

def calc_direction_and_distance(diff):
	direction = diff[:]
	for i in range(2):
		if direction[i] != 0:
			direction[i] //= abs(direction[i])
	return (tuple(direction), max([abs(part) for part in diff]))

def solve(n, k, q, obs):
	reachables = {}
	reachables[0, 1] = n - q[1]
	reachables[1, 1] = min(n - q[0], n - q[1])
	reachables[1, 0] = n - q[0]
	reachables[1, -1] = min(n - q[0], q[1] - 1)
	reachables[0, -1] = q[1] - 1
	reachables[-1, -1] = min(q[0] - 1, q[1] - 1)
	reachables[-1, 0] = q[0] - 1
	reachables[-1, 1] = min(q[0] - 1, n - q[1])
	for ob in obs:
		diff = calc_diff(ob, q)
		if is_reachable(diff):
			(direction, distance) = calc_direction_and_distance(diff)
			reachables[direction] = min(reachables[direction], distance - 1)
	return sum(reachables.values())
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
obs = []
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obs.append((rObstacle, cObstacle))
count = solve(n, k, (rQueen, cQueen), obs)
print(count)


def foo():
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	(rQueen, cQueen) = input().strip().split(' ')
	(rQueen, cQueen) = [int(rQueen), int(cQueen)]
	obstacles = set()
	moves = 0
	for a0 in range(k):
		(rObstacle, cObstacle) = input().strip().split(' ')
		(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
		obstacles.add((rObstacle, cObstacle))
	row_plus = list(range(rQueen + 1, n + 1))
	row_minus = list(range(rQueen - 1, 0, -1))
	col_plus = list(range(cQueen + 1, n + 1))
	col_minus = list(range(cQueen - 1, 0, -1))
	for i in row_plus:
		if (i, cQueen) in obstacles:
			break
		else:
			moves += 1
	for i in row_minus:
		if (i, cQueen) in obstacles:
			break
		else:
			moves += 1
	for i in col_plus:
		if (rQueen, i) in obstacles:
			break
		else:
			moves += 1
	for i in col_minus:
		if (rQueen, i) in obstacles:
			break
		else:
			moves += 1
	for i in zip(row_plus, col_plus):
		if i in obstacles:
			break
		else:
			moves += 1
	for i in zip(row_plus, col_minus):
		if i in obstacles:
			break
		else:
			moves += 1
	for i in zip(row_minus, col_plus):
		if i in obstacles:
			break
		else:
			moves += 1
	for i in zip(row_minus, col_minus):
		if i in obstacles:
			break
		else:
			moves += 1
	print(moves)
foo()


(n, k) = map(int, input().split())
(r, c) = map(int, input().split())
f = [c - 1, n - c, r - 1, n - r, min(c - 1, r - 1), min(r - 1, n - c), min(n - r, n - c), min(c - 1, n - r)]
for i in range(k):
	(ri, ci) = map(int, input().split())
	if ri == r and ci < c and (c - ci - 1 < f[0]):
		f[0] = c - ci - 1
	if ri == r and ci > c and (ci - c - 1 < f[1]):
		f[1] = ci - c - 1
	if ri < r and ci == c and (r - ri - 1 < f[2]):
		f[2] = r - ri - 1
	if ri > r and ci == c and (ri - r - 1 < f[3]):
		f[3] = ri - r - 1
	if ri < r and ci < c and (c - ci == r - ri) and (c - ci - 1 < f[4]):
		f[4] = c - ci - 1
	if ri < r and ci > c and (ci - c == r - ri) and (ci - c - 1 < f[5]):
		f[5] = ci - c - 1
	if ri > r and ci > c and (ci - c == ri - r) and (ci - c - 1 < f[6]):
		f[6] = ci - c - 1
	if ri > r and ci < c and (c - ci == ri - r) and (c - ci - 1 < f[7]):
		f[7] = c - ci - 1
print(sum(f))


def positionToBeRemoved(rQ, cQ, rO, cO, n):
	res = 0
	r_diff = abs(rQ - rO)
	c_diff = abs(cQ - cO)
	if rO == rQ:
		if cO > cQ:
			res = n - cO + 1
		elif cO < cQ:
			res = cO
	elif cO == cQ:
		if rO > rQ:
			res = n - rO + 1
		elif rO < rQ:
			res = rO
	elif rO > rQ and r_diff == c_diff:
		if cO > cQ:
			res = min(n - cO + 1, n - rO + 1)
		elif cO < cQ:
			res = min(cO, n - rO + 1)
	elif rO < rQ and r_diff == c_diff:
		if cO > cQ:
			res = min(n - cO + 1, rO)
		elif cO < cQ:
			res = min(cO, rO)
	return res

def pointNearToQueen(rQ, cQ, rO, cO, n, arr):
	r_diff = abs(rQ - rO)
	c_diff = abs(cQ - cO)
	if rO == rQ:
		if cO > cQ:
			if cO < arr[0]['c'] or arr[0]['c'] == -1:
				arr[0]['c'] = cO
				arr[0]['r'] = rO
		elif cO < cQ:
			if cO > arr[4]['c'] or arr[4]['c'] == -1:
				arr[4]['c'] = cO
				arr[4]['r'] = rO
	elif cO == cQ:
		if rO > rQ:
			if rO < arr[6]['r'] or arr[6]['c'] == -1:
				arr[6]['r'] = rO
				arr[6]['c'] = cO
		elif rO < rQ:
			if rO > arr[2]['r'] or arr[2]['c'] == -1:
				arr[2]['r'] = rO
				arr[2]['c'] = cO
	elif rO > rQ and r_diff == c_diff:
		if cO > cQ:
			if rO < arr[7]['r'] or arr[7]['c'] == -1:
				arr[7]['r'] = rO
				arr[7]['c'] = cO
		elif cO < cQ:
			if rO < arr[5]['r'] or arr[5]['c'] == -1:
				arr[5]['r'] = rO
				arr[5]['c'] = cO
	elif rO < rQ and r_diff == c_diff:
		if cO > cQ:
			if rO > arr[1]['r'] or arr[1]['c'] == -1:
				arr[1]['c'] = cO
				arr[1]['r'] = rO
		elif cO < cQ:
			if rO > arr[3]['r'] or arr[3]['c'] == -1:
				arr[3]['c'] = cO
				arr[3]['r'] = rO
	return arr
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
columns_right = n - cQueen
columns_left = cQueen - 1
rows_up = n - rQueen
rows_down = rQueen - 1
diagnol_top_right = min(columns_right, rows_up)
diagnol_bottom_right = min(columns_right, rows_down)
diagnol_bottom_left = min(rows_down, columns_left)
diagnol_top_left = min(columns_left, rows_up)
total_possibilities = columns_right + columns_left + rows_down + rows_up + diagnol_top_left + diagnol_top_right + diagnol_bottom_right + diagnol_bottom_left
arr = [{'r': -1, 'c': -1} for i in range(8)]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	arr = pointNearToQueen(rQueen, cQueen, rObstacle, cObstacle, n, arr)
if k > 0:
	for p in arr:
		if p['r'] != -1:
			total_possibilities -= positionToBeRemoved(rQueen, cQueen, p['r'], p['c'], n)
print(total_possibilities)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
obstacles = []
unblocked = []
blockedrow1 = []
blockedcol1 = []
blockedrow2 = []
blockedcol2 = []
blockeddiag1 = []
blockeddiag2 = []
blockeddiag3 = []
blockeddiag4 = []
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle > cQueen:
			blockedrow1.append((rObstacle, cObstacle))
		else:
			blockedrow2.append((rObstacle, cObstacle))
	elif cObstacle == cQueen:
		if rObstacle > rQueen:
			blockedcol1.append((rObstacle, cObstacle))
		else:
			blockedcol2.append((rObstacle, cObstacle))
	elif rObstacle > rQueen and cObstacle > cQueen and (rObstacle - rQueen == cObstacle - cQueen):
		blockeddiag1.append((rObstacle, cObstacle))
	elif rObstacle < rQueen and cObstacle < cQueen and (-rObstacle + rQueen == -cObstacle + cQueen):
		blockeddiag2.append((rObstacle, cObstacle))
	elif rObstacle < rQueen and cObstacle > cQueen and (-rObstacle + rQueen == cObstacle - cQueen):
		blockeddiag3.append((rObstacle, cObstacle))
	elif rObstacle > rQueen and cObstacle < cQueen and (rObstacle - rQueen == -cObstacle + cQueen):
		blockeddiag4.append((rObstacle, cObstacle))
if blockedrow1:
	blockedrow1 = min(blockedrow1)
else:
	blockedrow1 = None
if blockedrow2:
	blockedrow2 = max(blockedrow2)
else:
	blockedrow2 = None
if blockedcol1:
	blockedcol1 = min(blockedcol1)
else:
	blockedcol1 = None
if blockedcol2:
	blockedcol2 = max(blockedcol2)
else:
	blockedcol2 = None
if blockeddiag1:
	blockeddiag1 = min(blockeddiag1)
else:
	blockeddiag1 = None
if blockeddiag2:
	blockeddiag2 = max(blockeddiag2)
else:
	blockeddiag2 = None
if blockeddiag3:
	blockeddiag3 = max(blockeddiag3)
else:
	blockeddiag3 = None
if blockeddiag4:
	blockeddiag4 = min(blockeddiag4)
else:
	blockeddiag4 = None
for i in range(cQueen + 1, n + 1):
	if (rQueen, i) == blockedrow1:
		break
	else:
		unblocked.append((rQueen, i))
for i in range(cQueen - 1, 0, -1):
	if (rQueen, i) == blockedrow2:
		break
	else:
		unblocked.append((rQueen, i))
for i in range(rQueen + 1, n + 1):
	if (i, cQueen) == blockedcol1:
		break
	else:
		unblocked.append((i, cQueen))
for i in range(rQueen - 1, 0, -1):
	if (i, cQueen) == blockedcol2:
		break
	else:
		unblocked.append((i, cQueen))
z = 0
for i in range(rQueen + 1, n + 1):
	z += 1
	if cQueen + z > n or (i, cQueen + z) == blockeddiag1:
		break
	else:
		unblocked.append((i, cQueen + z))
z = 0
for i in range(rQueen - 1, 0, -1):
	z += 1
	if cQueen - z < 1 or (i, cQueen - z) == blockeddiag2:
		break
	else:
		unblocked.append((i, cQueen - z))
z = 0
for i in range(cQueen + 1, n + 1):
	z += 1
	if rQueen - z < 1 or (rQueen - z, i) == blockeddiag3:
		break
	else:
		unblocked.append((rQueen - z, i))
z = 0
for i in range(cQueen - 1, 0, -1):
	z += 1
	if rQueen + z > n or (rQueen + z, i) == blockeddiag4:
		break
	else:
		unblocked.append((rQueen + z, i))
print(len(unblocked))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
r = n - rQueen
l = rQueen - 1
t = n - cQueen
b = cQueen - 1
tr = min(n - rQueen, n - cQueen)
tl = min(rQueen - 1, n - cQueen)
br = min(n - rQueen, cQueen - 1)
bl = min(rQueen, cQueen) - 1
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rQueen == rObstacle:
		if cQueen > cObstacle:
			b = min(b, cQueen - cObstacle - 1)
		else:
			t = min(t, cObstacle - cQueen - 1)
	if cQueen == cObstacle:
		if rQueen > rObstacle:
			l = min(l, rQueen - rObstacle - 1)
		else:
			r = min(r, rObstacle - rQueen - 1)
	if cQueen - cObstacle == rQueen - rObstacle:
		if cQueen > cObstacle:
			bl = min(bl, cQueen - cObstacle - 1)
		else:
			tr = min(tr, cObstacle - cQueen - 1)
	if cQueen - cObstacle == rObstacle - rQueen:
		if cQueen > cObstacle:
			br = min(br, cQueen - cObstacle - 1)
		else:
			tl = min(tl, cObstacle - cQueen - 1)
print(sum([r, l, t, b, tr, tl, br, bl]))


(n, k) = map(int, input().split())
(r, c) = map(int, input().split())
ar = [(None, None) for __ in range(8)]
for i in range(k):
	(obr, obc) = map(int, input().split())
	if obr == r:
		if obc - c > 0:
			if ar[0][0] is None or obc - c < ar[0][1] - c:
				ar[0] = (obr, obc)
		elif ar[4][0] is None or c - obc < c - ar[4][1]:
			ar[4] = (obr, obc)
	elif obc == c:
		if obr - r > 0:
			if ar[2][0] is None or obr - r < ar[2][0] - r:
				ar[2] = (obr, obc)
		elif ar[6][0] is None or r - obr < r - ar[6][0]:
			ar[6] = (obr, obc)
	elif obc - c == obr - r:
		if obc - c > 0:
			if ar[1][0] is None or obc - c < ar[1][1] - c:
				ar[1] = (obr, obc)
		elif ar[5][0] is None or c - obc < c - ar[5][1]:
			ar[5] = (obr, obc)
	elif obc - c == -(obr - r):
		if obc - c > 0:
			if ar[7][0] is None or obc - c < ar[7][1] - c:
				ar[7] = (obr, obc)
		elif ar[3][0] is None or c - obc < c - ar[3][1]:
			ar[3] = (obr, obc)
ret = 0
ret += n - c if ar[0][0] is None else ar[0][1] - c - 1
ret += c - 1 if ar[4][0] is None else c - ar[4][1] - 1
ret += n - r if ar[2][0] is None else ar[2][0] - r - 1
ret += r - 1 if ar[6][0] is None else r - ar[6][0] - 1
ret += min(n - r, n - c) if ar[1][0] is None else ar[1][0] - r - 1
ret += min(r - 1, c - 1) if ar[5][0] is None else r - ar[5][0] - 1
ret += min(r - 1, n - c) if ar[7][0] is None else ar[7][1] - c - 1
ret += min(n - r, c - 1) if ar[3][0] is None else ar[3][0] - r - 1
print(ret)


(n, k) = map(int, input().split())
(qx, qy) = map(int, input().split())
obstacles = set([tuple(map(int, input().split())) for _ in range(k)])

def bound(a):
	return 1 <= a <= n
deltas = [(1, -1), (1, 0), (1, 1), (0, -1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]

def check_direction(delta, x, y):
	total = 0
	(cx, cy) = (x + delta[0], y + delta[1])
	while bound(cx) and bound(cy) and ((cx, cy) not in obstacles):
		total += 1
		cx += delta[0]
		cy += delta[1]
	return total

def solve():
	return sum((check_direction(delta, qx, qy) for delta in deltas))
print(solve())


import sys

def in_bounds(r, c, n):
	return r > 0 and c > 0 and (r <= n) and (c <= n)
move_offsets = ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, 1), (1, -1), (-1, -1))
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
obstacles = []
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obstacles.append((rObstacle, cObstacle))
obstacles = set(obstacles)
num_attacks = 0
for (r_off, c_off) in move_offsets:
	i = 1
	(new_r, new_c) = (rQueen + r_off * i, cQueen + c_off * i)
	while in_bounds(new_r, new_c, n) and (new_r, new_c) not in obstacles:
		num_attacks += 1
		i += 1
		(new_r, new_c) = (rQueen + r_off * i, cQueen + c_off * i)
print(num_attacks)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen) - 1, int(cQueen) - 1]
obstacles = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle) - 1, int(cObstacle) - 1]
	obstacles.add((rObstacle, cObstacle))
positions = 0
for rowDiff in [-1, 0, 1]:
	for colDiff in [-1, 0, 1]:
		if rowDiff == 0 and colDiff == 0:
			continue
		else:
			currRow = rQueen
			currCol = cQueen
			while True:
				newRow = currRow + rowDiff
				newCol = currCol + colDiff
				if newRow < 0 or newRow >= n or newCol < 0 or (newCol >= n):
					break
				elif (newRow, newCol) in obstacles:
					break
				else:
					positions += 1
					currRow = newRow
					currCol = newCol
print(positions)


import sys

def get_squares(n, hashset, rQueen, cQueen):
	squares = 0
	r = rQueen
	c = cQueen - 1
	while c > 0 and (r, c) not in hashset:
		squares += 1
		c -= 1
	r = rQueen + 1
	c = cQueen - 1
	while r <= n and c > 0 and ((r, c) not in hashset):
		squares += 1
		r += 1
		c -= 1
	r = rQueen + 1
	c = cQueen
	while r <= n and (r, c) not in hashset:
		squares += 1
		r += 1
	r = rQueen + 1
	c = cQueen + 1
	while r <= n and c <= n and ((r, c) not in hashset):
		squares += 1
		r += 1
		c += 1
	r = rQueen
	c = cQueen + 1
	while c <= n and (r, c) not in hashset:
		squares += 1
		c += 1
	r = rQueen - 1
	c = cQueen + 1
	while r > 0 and c <= n and ((r, c) not in hashset):
		squares += 1
		r -= 1
		c += 1
	r = rQueen - 1
	c = cQueen
	while r > 0 and (r, c) not in hashset:
		squares += 1
		r -= 1
	r = rQueen - 1
	c = cQueen - 1
	while r > 0 and c > 0 and ((r, c) not in hashset):
		squares += 1
		r -= 1
		c -= 1
	return squares
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
hashset = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	hashset.add((rObstacle, cObstacle))
print(get_squares(n, hashset, rQueen, cQueen))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
paths = {}
paths['top_left'] = min(n - rQueen, cQueen - 1)
paths['top'] = n - rQueen
paths['top_right'] = min(n - rQueen, n - cQueen)
paths['right'] = n - cQueen
paths['bottom_right'] = min(rQueen - 1, n - cQueen)
paths['bottom'] = rQueen - 1
paths['bottom_left'] = min(rQueen - 1, cQueen - 1)
paths['left'] = cQueen - 1
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	rows_diff = rQueen - rObstacle
	clmns_diff = cQueen - cObstacle
	if rows_diff == 0:
		if clmns_diff > 0:
			paths['left'] = min(paths.get('left'), clmns_diff - 1)
		else:
			paths['right'] = min(paths.get('right'), abs(clmns_diff) - 1)
	elif rows_diff < 0:
		if clmns_diff == 0:
			paths['top'] = min(paths.get('top'), abs(rows_diff) - 1)
		elif rows_diff / clmns_diff == -1.0:
			paths['top_left'] = min(paths.get('top_left'), clmns_diff - 1)
		elif rows_diff / clmns_diff == 1.0:
			paths['top_right'] = min(paths.get('top_right'), abs(clmns_diff) - 1)
	elif clmns_diff == 0:
		paths['bottom'] = min(paths.get('bottom'), rows_diff - 1)
	elif rows_diff / clmns_diff == -1.0:
		paths['bottom_right'] = min(paths.get('bottom_right'), abs(clmns_diff) - 1)
	elif rows_diff / clmns_diff == 1.0:
		paths['bottom_left'] = min(paths.get('bottom_left'), clmns_diff - 1)
all_sum = 0
for direction in paths:
	all_sum += paths[direction]
print(all_sum)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(q_r, q_c) = input().strip().split(' ')
(q_r, q_c) = [int(q_r), int(q_c)]
u_a = n - q_r
d_a = q_r - 1
r_a = n - q_c
l_a = q_c - 1
ur_a = u_a if u_a < r_a else r_a
ul_a = u_a if u_a < l_a else l_a
dr_a = d_a if d_a < r_a else r_a
dl_a = d_a if d_a < l_a else l_a
for i in range(k):
	(o_r, o_c) = input().strip().split(' ')
	(o_r, o_c) = [int(o_r), int(o_c)]
	d_r = o_r - q_r
	d_c = o_c - q_c
	if d_c == 0:
		if d_r > 0:
			u_a = d_r - 1 if d_r < u_a else u_a
			continue
		else:
			d_a = -d_r - 1 if -d_r < d_a else d_a
			continue
	if d_r == 0:
		if d_c > 0:
			r_a = d_c - 1 if d_c < r_a else r_a
			continue
		else:
			l_a = -d_c - 1 if -d_c < l_a else l_a
			continue
	if d_c == d_r:
		if d_c > 0:
			ur_a = d_c - 1 if d_c < ur_a else ur_a
			continue
		else:
			dl_a = -d_c - 1 if -d_c < dl_a else dl_a
			continue
	if d_c == -d_r:
		if d_c > 0:
			dr_a = d_c - 1 if d_c < dr_a else dr_a
			continue
		else:
			ul_a = -d_c - 1 if -d_c < ul_a else ul_a
			continue
print(u_a + d_a + r_a + l_a + ur_a + ul_a + dr_a + dl_a)


import sys
(n, k) = map(int, input().strip().split(' '))
(rq, cq) = map(int, input().strip().split(' '))
rq = n - rq
cq = cq - 1
ans = 0
maxl = -1
minr = n
maxu = -1
mind = n
minuld = n
minurd = n
mindld = n
mindrd = n
for _ in range(k):
	(ro, co) = map(int, input().strip().split(' '))
	ro = n - ro
	co = co - 1
	if ro == rq:
		if co < cq:
			if co > maxl:
				maxl = co
		elif co < minr:
			minr = co
	elif co == cq:
		if ro < rq:
			if ro > maxu:
				maxu = ro
		elif ro < mind:
			mind = ro
	elif ro < rq:
		if co < cq:
			x = rq - ro
			if cq - co == x:
				if x < minuld:
					minuld = x
		else:
			x = rq - ro
			if co - cq == x:
				if x < minurd:
					minurd = x
	elif ro > rq:
		if co < cq:
			x = ro - rq
			if cq - co == x:
				if x < mindld:
					mindld = x
		else:
			x = ro - rq
			if co - cq == x:
				if x < mindrd:
					mindrd = x
if maxl != -1:
	ans += cq - maxl - 1
else:
	ans += cq
if minr != n:
	ans += minr - cq - 1
else:
	ans += n - cq - 1
if maxu != -1:
	ans += rq - maxu - 1
else:
	ans += rq
if mind != n:
	ans += mind - rq - 1
else:
	ans += n - rq - 1
if minuld != n:
	ans += minuld - 1
else:
	i = rq - 1
	j = cq - 1
	while i >= 0 and j >= 0:
		ans += 1
		i -= 1
		j -= 1
if minurd != n:
	ans += minurd - 1
else:
	i = rq - 1
	j = cq + 1
	while i >= 0 and j < n:
		ans += 1
		i -= 1
		j += 1
if mindld != n:
	ans += mindld - 1
else:
	i = rq + 1
	j = cq - 1
	while i < n and j >= 0:
		ans += 1
		i += 1
		j -= 1
if mindrd != n:
	ans += mindrd - 1
else:
	i = rq + 1
	j = cq + 1
	while i < n and j < n:
		ans += 1
		i += 1
		j += 1
print(ans)


import sys

def isPositionValid(r, c, n):
	return 0 <= r < n and 0 <= c < n

def _getSolution(n, rQueen, cQueen, obstacles, directionDelta):
	newRQueen = rQueen + directionDelta[0]
	newCQueen = cQueen + directionDelta[1]
	acum = 0
	while isPositionValid(newRQueen, newCQueen, n) and (newRQueen, newCQueen) not in obstacles:
		acum += 1
		newRQueen = newRQueen + directionDelta[0]
		newCQueen = newCQueen + directionDelta[1]
	return acum

def getSolution(n, rQueen, cQueen, obstacles):
	directionDeltas = [(-1, -1), (-1, 0), (-1, 1), (0, 1), (0, -1), (1, -1), (1, 0), (1, 1)]
	solution = 0
	for direction in directionDeltas:
		solution += _getSolution(n, rQueen, cQueen, obstacles, direction)
	return solution
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
obstacles = {}
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen) - 1, int(cQueen) - 1]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle) - 1, int(cObstacle) - 1]
	obstacles[rObstacle, cObstacle] = True
print(getSolution(n, rQueen, cQueen, obstacles))


import sys
(n, k) = map(int, input().strip().split(' '))
board = [0 for _ in range(n)]
(r_q, c_q) = map(int, input().strip().split(' '))
r_q -= 1
c_q -= 1
lst = [max(r_q, 0), max(c_q, 0), max(n - r_q - 1, 0), max(n - c_q - 1, 0), max(min(r_q, c_q), 0), max(n - max(r_q, c_q) - 1, 0), max(min(r_q, n - c_q - 1), 0), max(min(n - r_q - 1, c_q), 0)]
for _ in range(k):
	(r_ob, c_ob) = map(int, input().strip().split(' '))
	r_ob -= 1
	c_ob -= 1
	if c_ob == c_q:
		if r_ob > r_q:
			if r_ob - r_q - 1 < lst[2]:
				lst[2] = r_ob - r_q - 1
		elif r_q - r_ob - 1 < lst[0]:
			lst[0] = r_q - r_ob - 1
	elif r_ob == r_q:
		if c_ob > c_q:
			if c_ob - c_q - 1 < lst[3]:
				lst[3] = c_ob - c_q - 1
		elif c_q - c_ob - 1 < lst[1]:
			lst[1] = c_q - c_ob - 1
	elif r_ob - c_ob == r_q - c_q:
		if c_ob > c_q:
			if c_ob - c_q - 1 < lst[5]:
				lst[5] = c_ob - c_q - 1
		elif c_q - c_ob - 1 < lst[4]:
			lst[4] = c_q - c_ob - 1
	elif r_ob + c_ob == r_q + c_q:
		if c_ob > c_q:
			if c_ob - c_q - 1 < lst[6]:
				lst[6] = c_ob - c_q - 1
		elif c_q - c_ob - 1 < lst[7]:
			lst[7] = c_q - c_ob - 1
print(sum(lst))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
obs = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obs.add((rObstacle, cObstacle))
res = 0
for dir in directions:
	(x, y) = (rQueen + dir[0], cQueen + dir[1])
	while x >= 1 and x <= n and (y >= 1) and (y <= n) and ((x, y) not in obs):
		res += 1
		(x, y) = (x + dir[0], y + dir[1])
print(res)


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
hor = [1] * (n + 1)
ver = [1] * (n + 1)
slop = [0] * (n + 1)
slon = [0] * (n + 1)
row = rQueen
col = cQueen
while row != 1 and col != 1:
	row -= 1
	col -= 1
	slop[row] = 1
row = rQueen
col = cQueen
while row != n and col != n:
	row += 1
	col += 1
	slop[row] = 1
row = rQueen
col = cQueen
while row != n and col != 1:
	row += 1
	col -= 1
	slon[row] = 1
row = rQueen
col = cQueen
while row != 1 and col != n:
	row -= 1
	col += 1
	slon[row] = 1
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle > cQueen:
			for i in range(cObstacle, n + 1):
				hor[i] = 0
		else:
			for i in range(cObstacle, 0, -1):
				hor[i] = 0
	elif cObstacle == cQueen:
		if rObstacle > rQueen:
			for i in range(rObstacle, n + 1):
				ver[i] = 0
		else:
			for i in range(rObstacle, 0, -1):
				ver[i] = 0
	elif abs(rObstacle - rQueen) == abs(cObstacle - cQueen):
		slope = (rObstacle - rQueen) // (cObstacle - cQueen)
		if slope == 1:
			if rObstacle > rQueen:
				for i in range(rObstacle, n + 1):
					slop[i] = 0
			else:
				for i in range(rObstacle, 0, -1):
					slop[i] = 0
		elif slope == -1:
			if rObstacle > rQueen:
				for i in range(rObstacle, n + 1):
					slon[i] = 0
			else:
				for i in range(rObstacle, 0, -1):
					slon[i] = 0
hor[cQueen] = 0
ver[rQueen] = 0
hor[0] = 0
ver[0] = 0
slop[0] = 0
slop[rQueen] = 0
slon[0] = 0
slon[rQueen] = 0
print(sum(hor) + sum(ver) + sum(slop) + sum(slon))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
O = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	O.add((rObstacle, cObstacle))
COUNT = 0
for (r, c) in [(r, c) for r in [-1, 0, 1] for c in [-1, 0, 1]]:
	if not (r == 0 and c == 0):
		cr = rQueen + r
		cc = cQueen + c
		while cr > 0 and cr <= n and (cc > 0) and (cc <= n) and ((cr, cc) not in O):
			cr += r
			cc += c
			COUNT += 1
print(COUNT)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
left = cQueen - 1
top = n - rQueen
right = n - cQueen
bottom = rQueen - 1
topleft = min(top, left)
topright = min(top, right)
bottomright = min(bottom, right)
bottomleft = min(bottom, left)
sum_all = left + top + right + bottom + topleft + topright + bottomright + bottomleft
directions = [[-n, 0], [n, 0], [n, 0], [n, 0], [n, 0], [-n, 0], [-n, 0], [-n, 0]]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	(rDiff, cDiff) = (rObstacle - rQueen, cObstacle - cQueen)
	newSum = 0
	if rDiff == 0:
		cNew = cQueen + cDiff
		if cDiff < 0:
			newSum = cNew + 1 - 1
			if cDiff > directions[0][0]:
				directions[0] = [cDiff, newSum]
		else:
			newSum = n + 1 - cNew
			if cDiff < directions[4][0]:
				directions[4] = [cDiff, newSum]
	elif cDiff == 0:
		rNew = rQueen + rDiff
		if rDiff < 0:
			newSum = rNew + 1 - 1
			if rDiff > directions[6][0]:
				directions[6] = [rDiff, newSum]
		else:
			newSum = n + 1 - rNew
			if rDiff < directions[2][0]:
				directions[2] = [rDiff, newSum]
	elif rDiff == cDiff or rDiff == -cDiff:
		rNewSum = 0
		cNewSum = 0
		rNew = rQueen + rDiff
		if rDiff < 0:
			rNewSum = rNew + 1 - 1
		else:
			rNewSum = n + 1 - rNew
		cNew = cQueen + cDiff
		if cDiff < 0:
			cNewSum = cNew + 1 - 1
		else:
			cNewSum = n + 1 - cNew
		newSum = min(rNewSum, cNewSum)
		if rDiff < 0:
			if cDiff < 0:
				if rDiff > directions[7][0]:
					directions[7] = [rDiff, newSum]
			elif rDiff > directions[5][0]:
				directions[5] = [rDiff, newSum]
		elif cDiff < 0:
			if rDiff < directions[1][0]:
				directions[1] = [rDiff, newSum]
		elif rDiff < directions[3][0]:
			directions[3] = [rDiff, newSum]
sum_blocked = 0
for direction in directions:
	sum_blocked = sum_blocked + direction[1]
print(sum_all - sum_blocked)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
obstacles = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	obstacles.add((int(rObstacle), int(cObstacle)))
total = 0
for x in range(rQueen - 1, 0, -1):
	if (x, cQueen) in obstacles:
		break
	total += 1
for x in range(rQueen + 1, n + 1):
	if (x, cQueen) in obstacles:
		break
	total += 1
for x in range(cQueen - 1, 0, -1):
	if (rQueen, x) in obstacles:
		break
	total += 1
for x in range(cQueen + 1, n + 1):
	if (rQueen, x) in obstacles:
		break
	total += 1
x = rQueen
y = cQueen
while True:
	x += 1
	y += 1
	if x > n or y > n or (x, y) in obstacles:
		break
	total += 1
x = rQueen
y = cQueen
while True:
	x += 1
	y -= 1
	if x > n or y < 1 or (x, y) in obstacles:
		break
	total += 1
x = rQueen
y = cQueen
while True:
	x -= 1
	y -= 1
	if x < 1 or y < 1 or (x, y) in obstacles:
		break
	total += 1
x = rQueen
y = cQueen
while True:
	x -= 1
	y += 1
	if x < 1 or y > n or (x, y) in obstacles:
		break
	total += 1
print(total)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rq, cq) = map(int, input().strip().split(' '))
obstacles = {}
for a0 in range(k):
	(ro, co) = input().strip().split(' ')
	obstacles[ro + '$' + co] = True
movements = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
result = 0
for m in movements:
	x = m[0]
	y = m[1]
	curx = rq
	cury = cq
	while True:
		curx += x
		cury += y
		if curx < 1 or curx > n or cury < 1 or (cury > n) or obstacles.get(str(curx) + '$' + str(cury), False):
			break
		result += 1
print(result)


import sys

def stepCheck(rObstacle, cObstacle):
	global rQueen, cQueen, step
	if rQueen == rObstacle:
		if cQueen < cObstacle:
			if step[0] > cObstacle:
				step[0] = cObstacle
		elif step[1] < cObstacle:
			step[1] = cObstacle
	elif cQueen == cObstacle:
		if rQueen < rObstacle:
			if step[2] > rObstacle:
				step[2] = rObstacle
		elif step[3] < rObstacle:
			step[3] = rObstacle
	else:
		cdiff = cObstacle - cQueen
		rdiff = rObstacle - rQueen
		abscdiff = abs(cdiff)
		if abscdiff == abs(rdiff):
			if rdiff > 0:
				if cdiff > 0:
					if step[4] > abscdiff:
						step[4] = abscdiff
				elif step[5] > abscdiff:
					step[5] = abscdiff
			elif cdiff > 0:
				if step[6] > abscdiff:
					step[6] = abscdiff
			elif step[7] > abscdiff:
				step[7] = abscdiff

def main():
	global rQueen, cQueen, step
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	(rQueen, cQueen) = input().strip().split(' ')
	(rQueen, cQueen) = [int(rQueen), int(cQueen)]
	n1 = n + 1
	NE = min(n1 - cQueen, n1 - rQueen)
	NW = min(cQueen, n1 - rQueen)
	SW = min(cQueen, rQueen)
	SE = min(n1 - cQueen, rQueen)
	step = [n1, 0, n1, 0, NE, NW, SE, SW]
	for i in range(k):
		(rObstacle, cObstacle) = input().strip().split(' ')
		(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
		stepCheck(rObstacle, cObstacle)
	Ek = step[0] - cQueen - 1
	Wk = cQueen - step[1] - 1
	Nk = step[2] - rQueen - 1
	Sk = rQueen - step[3] - 1
	sumKill = Ek + Wk + Sk + Nk
	for i in range(4, 8):
		sumKill += step[i] - 1
	print(sumKill)
main()


import sys
obst = set()
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
pos = 0
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obst.add((rObstacle, cObstacle))
for i in range(rQueen + 1, n + 1):
	if (i, cQueen) in obst:
		break
	else:
		pos += 1
for i in range(rQueen - 1, 0, -1):
	if (i, cQueen) in obst:
		break
	else:
		pos += 1
for i in range(cQueen + 1, n + 1):
	if (rQueen, i) in obst:
		break
	else:
		pos += 1
for i in range(cQueen - 1, 0, -1):
	if (rQueen, i) in obst:
		break
	else:
		pos += 1
x = min(cQueen, rQueen)
if x >= 1:
	a = rQueen
	b = cQueen
	for i in range(1, x):
		a -= 1
		b -= 1
		if (a, b) in obst:
			break
		elif a > 0 and a <= n and (b > 0) and (b <= n):
			pos += 1
x = min(n - cQueen, n - rQueen)
if x >= 1:
	a = rQueen
	b = cQueen
	for i in range(1, x + 1):
		a += 1
		b += 1
		if (a, b) in obst:
			break
		elif a > 0 and a <= n and (b > 0) and (b <= n):
			pos += 1
x = min(cQueen, n - rQueen)
if x >= 1:
	a = rQueen
	b = cQueen
	for i in range(1, x + 1):
		a += 1
		b -= 1
		if (a, b) in obst:
			break
		elif a > 0 and a <= n and (b > 0) and (b <= n):
			pos += 1
x = min(n - cQueen, rQueen)
if x >= 1:
	a = rQueen
	b = cQueen
	for i in range(1, x + 1):
		a -= 1
		b += 1
		if (a, b) in obst:
			break
		elif a > 0 and a <= n and (b > 0) and (b <= n):
			pos += 1
print(pos)


class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

class Dir:

	def __init__(self, x, y, closer, calcTotalFreeTiles, calcFreeTilesTillObstacle):
		self.closestObstacle = None
		self.x = x
		self.y = y
		self.closer = closer
		self.calcTotalFreeTiles = calcTotalFreeTiles
		self.calcFreeTilesTillObstacle = calcFreeTilesTillObstacle

	def checkForCloserObstacle(self, newObstacle):
		if self.closestObstacle is None:
			self.closestObstacle = newObstacle
			return
		if self.closer(self.closestObstacle.x, self.closestObstacle.y, newObstacle.x, newObstacle.y):
			self.closestObstacle = newObstacle

class QueensAttack:

	def __init__(self, gridSize, queen):
		self.gridSize = gridSize
		self.queen = queen
		self.obstacle = None
		self.dirs = {'tl': Dir(-1, 1, lambda cox, coy, nx, ny: ny < coy, lambda gridSize, qx, qy: qx - 1 if gridSize - qy >= qx - 1 else gridSize - qy, lambda ox, oy, qx, qy: qx - ox - 1), 't': Dir(0, 1, lambda cox, coy, nx, ny: ny < coy, lambda gridSize, qx, qy: gridSize - qy, lambda ox, oy, qx, qy: oy - qy - 1), 'tr': Dir(1, 1, lambda cox, coy, nx, ny: ny < coy, lambda gridSize, qx, qy: gridSize - qx if gridSize - qy >= gridSize - qx else gridSize - qy, lambda ox, oy, qx, qy: ox - qx - 1), 'r': Dir(1, 0, lambda cox, coy, nx, ny: nx < cox, lambda gridSize, qx, qy: gridSize - qx, lambda ox, oy, qx, qy: ox - qx - 1), 'br': Dir(1, -1, lambda cox, coy, nx, ny: ny > coy, lambda gridSize, qx, qy: gridSize - qx if qy - 1 >= gridSize - qx else qy - 1, lambda ox, oy, qx, qy: ox - qx - 1), 'b': Dir(0, -1, lambda cox, coy, nx, ny: ny > coy, lambda gridSize, qx, qy: qy - 1, lambda ox, oy, qx, qy: qy - oy - 1), 'bl': Dir(-1, -1, lambda cox, coy, nx, ny: ny > coy, lambda gridSize, qx, qy: qx - 1 if qy - 1 >= qx - 1 else qy - 1, lambda ox, oy, qx, qy: qx - ox - 1), 'l': Dir(-1, 0, lambda cox, coy, nx, ny: nx > cox, lambda gridSize, qx, qy: qx - 1, lambda ox, oy, qx, qy: qx - ox - 1)}
		self.dirs = {k: v for (k, v) in self.dirs.items() if self.dirIsValid(v.x, v.y)}

	def dirIsValid(self, xDiff, yDiff):
		nx = self.queen.x + xDiff
		ny = self.queen.y + yDiff
		return not (nx < 1 or nx > self.gridSize or ny < 1 or (ny > self.gridSize))

	def bottomOrTop(self):
		return 'b' if self.obstacle.y < self.queen.y else 't'

	def leftOrRight(self):
		return 'l' if self.obstacle.x < self.queen.x else 'r'

	def findDir(self):
		if self.queen.x != self.obstacle.x and self.queen.y == self.obstacle.y:
			return self.leftOrRight()
		if self.queen.x == self.obstacle.x and self.queen.y != self.obstacle.y:
			return self.bottomOrTop()
		if abs(self.queen.x - self.obstacle.x) == abs(self.queen.y - self.obstacle.y):
			return self.bottomOrTop() + self.leftOrRight()
		return None

	def addObstacle(self, obstacle):
		self.obstacle = obstacle
		dir = self.findDir()
		if not dir in self.dirs:
			return
		self.dirs[dir].checkForCloserObstacle(obstacle)

	def calcFreeTiles(self):
		freeTiles = 0
		for dirName in self.dirs:
			dir = self.dirs[dirName]
			if dir.closestObstacle is None:
				freeTiles += dir.calcTotalFreeTiles(self.gridSize, self.queen.x, self.queen.y)
			else:
				freeTiles += dir.calcFreeTilesTillObstacle(dir.closestObstacle.x, dir.closestObstacle.y, self.queen.x, self.queen.y)
		return freeTiles
(n, k) = map(int, input().strip().split(' '))
(yQueen, xQueen) = map(int, input().strip().split(' '))
queensAttack = QueensAttack(n, Point(xQueen, yQueen))
for a0 in range(k):
	(yObstacle, xObstacle) = map(int, input().strip().split(' '))
	queensAttack.addObstacle(Point(xObstacle, yObstacle))
print(queensAttack.calcFreeTiles())


import sys
(n, k) = input().split()
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().split()
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
Queenpos = tuple([rQueen, cQueen])
Obstacles = set()
Boundaries = [(n, n), (1, n), (1, 1), (n, 1)]
for a0 in range(k):
	(rObstacle, cObstacle) = input().split()
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	Obstacles.add(tuple([rObstacle, cObstacle]))
count = 0
for i in range(8):
	x = rQueen
	y = cQueen
	if i == 0:
		x = x - 1
		while (x >= 1) & (x <= n) & (y >= 1) & (y <= n):
			if tuple([x, y]) in Obstacles:
				break
			else:
				count += 1
				x = x - 1
	elif i == 1:
		x = x - 1
		y = y - 1
		while (x >= 1) & (x <= n) & (y >= 1) & (y <= n):
			if tuple([x, y]) in Obstacles:
				break
			else:
				count += 1
				x = x - 1
				y = y - 1
	elif i == 2:
		y = y - 1
		while (x >= 1) & (x <= n) & (y >= 1) & (y <= n):
			if tuple([x, y]) in Obstacles:
				break
			else:
				count += 1
				y = y - 1
	elif i == 3:
		x = x + 1
		y = y - 1
		while (x >= 1) & (x <= n) & (y >= 1) & (y <= n):
			if tuple([x, y]) in Obstacles:
				break
			else:
				count += 1
				x = x + 1
				y = y - 1
	elif i == 4:
		x = x + 1
		while (x >= 1) & (x <= n) & (y >= 1) & (y <= n):
			if tuple([x, y]) in Obstacles:
				break
			else:
				count += 1
				x = x + 1
	elif i == 5:
		x = x + 1
		y = y + 1
		while (x >= 1) & (x <= n) & (y >= 1) & (y <= n):
			if tuple([x, y]) in Obstacles:
				break
			else:
				count += 1
				x = x + 1
				y = y + 1
	elif i == 6:
		y = y + 1
		while (x >= 1) & (x <= n) & (y >= 1) & (y <= n):
			if tuple([x, y]) in Obstacles:
				break
			else:
				count += 1
				y = y + 1
	elif i == 7:
		x = x - 1
		y = y + 1
		while (x >= 1) & (x <= n) & (y >= 1) & (y <= n):
			if tuple([x, y]) in Obstacles:
				break
			else:
				count += 1
				x = x - 1
				y = y + 1
print(count)


def read_ints():
	return (int(x) for x in input().strip().split(' '))
NORTH = (1, 0)
NORTH_EAST = (1, 1)
EAST = (0, 1)
SOUTH_EAST = (-1, 1)
SOUTH = (0, -1)
SOUTH_WEST = (-1, -1)
WEST = (-1, 0)
NORTH_WEST = (1, -1)
possible_directions = (NORTH, NORTH_EAST, EAST, SOUTH_EAST, SOUTH, SOUTH_WEST, WEST, NORTH_WEST)

def get_next_move(position, direction, distance):
	shift = (direction[0] * distance, direction[1] * distance)
	next_position = (position[0] + shift[0], position[1] + shift[1])
	return next_position
(n, k) = read_ints()
(r_queen, c_queen) = read_ints()
queen = (r_queen, c_queen)

def on_board(position):
	return 1 <= position[0] <= n and 1 <= position[1] <= n
obstacles = {tuple(read_ints()) for ___ in range(k)}
squares = 0
for current_direction in possible_directions:
	current_distance = 1
	next_move = get_next_move(queen, current_direction, current_distance)
	while on_board(next_move) and next_move not in obstacles:
		squares += 1
		current_distance += 1
		next_move = get_next_move(queen, current_direction, current_distance)
print(squares)


import sys
queen_steps = {'se': (1, 1), 's': (1, 0), 'so': (1, -1), 'o': (0, -1), 'no': (-1, -1), 'n': (-1, 0), 'ne': (-1, 1), 'e': (0, 1)}
obstacles = dict()
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obstacles[rObstacle, cObstacle] = 1
moves = 0
for direction in queen_steps:
	for possible_step in range(1, n + 1):
		possible_move = (rQueen + queen_steps[direction][0] * possible_step, cQueen + queen_steps[direction][1] * possible_step)
		if possible_move not in obstacles and 0 < possible_move[0] <= n and (0 < possible_move[1] <= n):
			moves += 1
		else:
			break
print(moves)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
(l, r, u, d) = [cQueen - 1, n - cQueen, n - rQueen, rQueen - 1]
(ul, dl, ur, dr) = [min(u, l), min(d, l), min(u, r), min(d, r)]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if cQueen == cObstacle:
		if rQueen < rObstacle:
			if rObstacle - rQueen - 1 < u:
				u = rObstacle - rQueen - 1
		elif rQueen != rObstacle:
			if rQueen - rObstacle - 1 < d:
				d = rQueen - rObstacle - 1
	elif rQueen == rObstacle:
		if cQueen < cObstacle:
			if cObstacle - cQueen - 1 < r:
				r = cObstacle - cQueen - 1
		elif cQueen != cObstacle:
			if rQueen - rObstacle - 1 < l:
				l = cQueen - cObstacle - 1
	elif abs(rQueen - rObstacle) == abs(cQueen - cObstacle):
		if rQueen < rObstacle:
			if cQueen < cObstacle:
				if cObstacle - cQueen - 1 < ur:
					ur = cObstacle - cQueen - 1
			elif cQueen - cObstacle - 1 < ul:
				ul = cQueen - cObstacle - 1
		elif cQueen < cObstacle:
			if cObstacle - cQueen - 1 < dr:
				dr = cObstacle - cQueen - 1
		elif cQueen - cObstacle - 1 < dl:
			dl = cQueen - cObstacle - 1
print(l + r + d + u + ul + dl + ur + dr)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
d = {}
d['up'] = n - rQueen
d['down'] = rQueen - 1
d['left'] = cQueen - 1
d['right'] = n - cQueen
d['ur'] = min(d['up'], d['right'])
d['dr'] = min(d['down'], d['right'])
d['ul'] = min(d['up'], d['left'])
d['dl'] = min(d['down'], d['left'])
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if cObstacle == cQueen:
		if rObstacle > rQueen:
			d['up'] = min(d['up'], rObstacle - rQueen - 1)
		else:
			d['down'] = min(d['down'], rQueen - rObstacle - 1)
	elif rObstacle == rQueen:
		if cObstacle > cQueen:
			d['right'] = min(d['right'], cObstacle - cQueen - 1)
		else:
			d['left'] = min(d['left'], cQueen - cObstacle - 1)
	elif rObstacle - rQueen == cObstacle - cQueen:
		if rObstacle > rQueen:
			d['ur'] = min(d['ur'], rObstacle - rQueen - 1)
		else:
			d['dl'] = min(d['dl'], rQueen - rObstacle - 1)
	elif rObstacle - rQueen == -(cObstacle - cQueen):
		if rObstacle > rQueen:
			d['ul'] = min(d['ul'], rObstacle - rQueen - 1)
		else:
			d['dr'] = min(d['dr'], rQueen - rObstacle - 1)
print(sum(d.values()))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
l = [rQueen, 1]
r = [rQueen, n]
u = [n, cQueen]
d = [1, cQueen]
tr = rQueen
tc = cQueen
while 1 < tr <= n and 1 < tc <= n:
	tr -= 1
	tc -= 1
dl = [tr, tc]
tr = rQueen
tc = cQueen
while 1 < tr <= n and 1 <= tc < n:
	tr -= 1
	tc += 1
dr = [tr, tc]
tr = rQueen
tc = cQueen
while 1 <= tr < n and 1 < tc <= n:
	tr += 1
	tc -= 1
ul = [tr, tc]
tr = rQueen
tc = cQueen
while 1 <= tr < n and 1 <= tc < n:
	tr += 1
	tc += 1
ur = [tr, tc]
changed = [0] * 8
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle < cQueen and cObstacle > l[1]:
			changed[0] = 1
			l[1] = cObstacle
		elif cObstacle > cQueen and cObstacle < r[1]:
			changed[1] = 1
			r[1] = cObstacle
	elif cObstacle == cQueen:
		if rObstacle < rQueen and rObstacle > d[0]:
			changed[2] = 1
			d[0] = rObstacle
		elif rObstacle > rQueen and rObstacle < u[0]:
			changed[3] = 1
			u[0] = rObstacle
	else:
		dx = cQueen - cObstacle
		dy = rQueen - rObstacle
		if abs(dx) == abs(dy):
			if dx > 0 and dy > 0 and (rObstacle > dl[0]):
				changed[4] = 1
				dl[0] = rObstacle
				dl[1] = cObstacle
			elif dx > 0 and dy < 0 and (rObstacle < ul[0]):
				changed[5] = 1
				ul[0] = rObstacle
				ul[1] = cObstacle
			elif dx < 0 and dy > 0 and (rObstacle > dr[0]):
				changed[6] = 1
				dr[0] = rObstacle
				dr[1] = cObstacle
			elif dx < 0 and dy < 0 and (rObstacle < ur[0]):
				changed[7] = 1
				ur[0] = rObstacle
				ur[1] = cObstacle
result = r[1] - l[1] + (u[0] - d[0]) + (ul[0] - dr[0]) + (ur[0] - dl[0]) - sum(changed)
print(result)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
obs = []
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rO, cO) = [int(rObstacle), int(cObstacle)]
	obs.append([rO, cO])
ans = 0
(m, M) = (0, n + 1)
for i in range(k):
	if obs[i][0] == rQueen:
		if obs[i][1] < cQueen and obs[i][1] > m:
			m = obs[i][1]
		elif obs[i][1] > cQueen and obs[i][1] < M:
			M = obs[i][1]
ans += cQueen - m - 1 + (M - cQueen - 1)
(m, M) = (0, n + 1)
for i in range(k):
	if obs[i][1] == cQueen:
		if obs[i][0] < rQueen and obs[i][0] > m:
			m = obs[i][0]
		elif obs[i][0] > rQueen and obs[i][0] < M:
			M = obs[i][0]
ans += rQueen - m - 1 + (M - rQueen - 1)
(m, M) = (max(0, rQueen + cQueen - (n + 1)), min(n + 1, rQueen + cQueen))
for i in range(k):
	if sum(obs[i]) == cQueen + rQueen:
		if obs[i][1] < cQueen and obs[i][1] > m:
			m = obs[i][1]
		elif obs[i][1] > cQueen and obs[i][1] < M:
			M = obs[i][1]
ans += cQueen - m - 1 + (M - cQueen - 1)
(m, M) = (max(0, cQueen - rQueen), min(n + 1, cQueen - rQueen + (n + 1)))
for i in range(k):
	if obs[i][1] - obs[i][0] == cQueen - rQueen:
		if obs[i][1] < cQueen and obs[i][1] > m:
			m = obs[i][1]
		elif obs[i][1] > cQueen and obs[i][1] < M:
			M = obs[i][1]
ans += cQueen - m - 1 + (M - cQueen - 1)
print(ans)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen) - 1, int(cQueen) - 1]
attackedPositions = []
for i in range(3):
	attackedPositions.append([0] * 3)
attackedPositions[2][0] = min(n - 1 - rQueen, cQueen)
attackedPositions[1][0] = cQueen
attackedPositions[0][0] = min(rQueen, cQueen)
attackedPositions[2][1] = n - 1 - rQueen
attackedPositions[0][1] = rQueen
attackedPositions[2][2] = min(n - 1 - rQueen, n - 1 - cQueen)
attackedPositions[1][2] = n - 1 - cQueen
attackedPositions[0][2] = min(rQueen, n - 1 - cQueen)
for i in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle) - 1, int(cObstacle) - 1]
	if rObstacle == rQueen:
		if cObstacle < cQueen and cQueen - cObstacle - 1 < attackedPositions[1][0]:
			attackedPositions[1][0] = cQueen - cObstacle - 1
		elif cObstacle > cQueen and cObstacle - cQueen - 1 < attackedPositions[1][2]:
			attackedPositions[1][2] = cObstacle - cQueen - 1
	elif cObstacle == cQueen:
		if rObstacle < rQueen and rQueen - rObstacle - 1 < attackedPositions[0][1]:
			attackedPositions[0][1] = rQueen - rObstacle - 1
		elif rObstacle > rQueen and rObstacle - rQueen - 1 < attackedPositions[2][1]:
			attackedPositions[2][1] = rObstacle - rQueen - 1
	elif rObstacle < rQueen and cObstacle < cQueen:
		attacks = rQueen - rObstacle - 1
		if rQueen - rObstacle == cQueen - cObstacle and attacks < attackedPositions[0][0]:
			attackedPositions[0][0] = attacks
	elif rObstacle < rQueen and cObstacle > cQueen:
		attacks = rQueen - rObstacle - 1
		if rQueen - rObstacle == cObstacle - cQueen and attacks < attackedPositions[0][2]:
			attackedPositions[0][2] = attacks
	elif rObstacle > rQueen and cObstacle < cQueen:
		attacks = rObstacle - rQueen - 1
		if rObstacle - rQueen == cQueen - cObstacle and attacks < attackedPositions[2][0]:
			attackedPositions[2][0] = attacks
	elif rObstacle > rQueen and cObstacle > cQueen:
		attacks = rObstacle - rQueen - 1
		if rObstacle - rQueen == cObstacle - cQueen and attacks < attackedPositions[2][2]:
			attackedPositions[2][2] = attacks
attacks = 0
for i in range(3):
	for j in range(3):
		attacks += attackedPositions[i][j]
print(attacks)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
eightDirection = [0, [rQueen + min(n - rQueen, cQueen - 1), cQueen - min(n - rQueen, cQueen - 1)], [n, cQueen], [rQueen + min(n - rQueen, n - cQueen), cQueen + min(n - rQueen, n - cQueen)], [rQueen, 1], [rQueen, n], [rQueen - min(rQueen - 1, cQueen - 1), cQueen - min(rQueen - 1, cQueen - 1)], [1, cQueen], [rQueen - min(rQueen - 1, n - cQueen), cQueen + min(rQueen - 1, n - cQueen)]]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle > cQueen and cObstacle <= eightDirection[5][1]:
			eightDirection[5][1] = cObstacle - 1
		elif cObstacle < cQueen and cObstacle >= eightDirection[4][1]:
			eightDirection[4][1] = cObstacle + 1
	elif cObstacle == cQueen:
		if rObstacle > rQueen and rObstacle <= eightDirection[2][0]:
			eightDirection[2][0] = rObstacle - 1
		elif rObstacle < rQueen and rObstacle >= eightDirection[7][0]:
			eightDirection[7][0] = rObstacle + 1
	elif rObstacle - rQueen == cObstacle - cQueen:
		if rObstacle > rQueen and rObstacle <= eightDirection[3][0]:
			eightDirection[3] = [rObstacle - 1, cObstacle - 1]
		elif rObstacle < rQueen and rObstacle >= eightDirection[6][0]:
			eightDirection[6] = [rObstacle + 1, cObstacle + 1]
	elif rObstacle - rQueen == -(cObstacle - cQueen):
		if rObstacle > rQueen and rObstacle <= eightDirection[1][0]:
			eightDirection[1] = [rObstacle - 1, cObstacle + 1]
		elif rObstacle < rQueen and rObstacle >= eightDirection[8][0]:
			eightDirection[8] = [rObstacle + 1, cObstacle - 1]
res = eightDirection[5][1] - eightDirection[4][1] + eightDirection[2][0] - eightDirection[7][0] + eightDirection[8][1] - eightDirection[1][1] + eightDirection[3][0] - eightDirection[6][0]
print(res)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQ, cQ) = input().strip().split(' ')
(rQ, cQ) = [int(rQ), int(cQ)]
al = cQ - 1
ar = n - cQ
au = n - rQ
ad = rQ - 1
aul = al if al < au else au
aur = ar if ar < au else au
adl = al if al < ad else ad
adr = ar if ar < ad else ad
for a0 in range(k):
	(rH, cH) = input().strip().split(' ')
	(rH, cH) = [int(rH), int(cH)]
	if rH == rQ:
		absDist = abs(cH - cQ) - 1
		if cH < cQ:
			if absDist < al:
				al = absDist
		elif absDist < ar:
			ar = absDist
	elif cH == cQ:
		absDist = abs(rH - rQ) - 1
		if rH < rQ:
			if absDist < ad:
				ad = absDist
		elif absDist < au:
			au = absDist
	elif abs(cH - cQ) == abs(rH - rQ):
		if cH - cQ > 0:
			absDist = cH - cQ - 1
			if rH - rQ > 0:
				if absDist < aur:
					aur = absDist
			elif rH - rQ < 0:
				if absDist < adr:
					adr = absDist
		elif cH - cQ < 0:
			absDist = cQ - cH - 1
			if rH - rQ > 0:
				if absDist < aul:
					aul = absDist
			if rH - rQ < 0:
				if absDist < adl:
					adl = absDist
if al < 0:
	al = 0
if ar < 0:
	ar = 0
if au < 0:
	au = 0
if ad < 0:
	ad = 0
if aul < 0:
	aul = 0
if aur < 0:
	aur = 0
if adl < 0:
	adl = 0
if adr < 0:
	adr = 0
print(al + ar + au + ad + aul + aur + adl + adr)


import sys

def find_closest_obstacles(xq, yq, n, all_obstacles):
	left = xq - 1
	right = n - xq
	down = yq - 1
	up = n - yq
	left_down = min(left, down)
	left_up = min(left, up)
	right_down = min(right, down)
	right_up = min(right, up)
	for (xo, yo) in all_obstacles:
		if xo == xq:
			if yo > yq:
				up = min(up, yo - yq - 1)
			elif yo < yq:
				down = min(down, yq - yo - 1)
		elif yo == yq:
			if xo < xq:
				left = min(left, xq - xo - 1)
			elif xo > xq:
				right = min(right, xo - xq - 1)
		elif xo < xq and xq - xo == yq - yo:
			left_down = min(left_down, xq - xo - 1)
		elif xo < xq and xq - xo == yo - yq:
			left_up = min(left_up, xq - xo - 1)
		elif xo > xq and xo - xq == yq - yo:
			right_down = min(right_down, xo - xq - 1)
		elif xo > xq and xo - xq == yo - yq:
			right_up = min(right_up, xo - xq - 1)
	total = up + down + left + right + left_down + left_up + right_down + right_up
	return total
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
(yq, xq) = (rQueen, cQueen)
all_obstacles = []
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	all_obstacles.append([cObstacle, rObstacle])
res = find_closest_obstacles(xq, yq, n, all_obstacles)
print(res)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
attackRegion = [n - cQueen, cQueen - 1, n - rQueen, rQueen - 1, min(n - cQueen, n - rQueen), min(n - cQueen, rQueen - 1), min(cQueen - 1, n - rQueen), min(cQueen - 1, rQueen - 1)]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	cDiff = cObstacle - cQueen
	rDiff = rObstacle - rQueen
	if rDiff == 0:
		if cDiff > 0:
			attackRegion[0] = min(attackRegion[0], cDiff - 1)
		else:
			attackRegion[1] = min(attackRegion[1], -cDiff - 1)
	elif cDiff == 0:
		if rDiff > 0:
			attackRegion[2] = min(attackRegion[2], rDiff - 1)
		else:
			attackRegion[3] = min(attackRegion[3], -rDiff - 1)
	elif abs(cDiff) != abs(rDiff):
		continue
	elif cDiff > 0 and rDiff > 0:
		attackRegion[4] = min(attackRegion[4], cDiff - 1)
	elif cDiff > 0 and rDiff < 0:
		attackRegion[5] = min(attackRegion[5], cDiff - 1)
	elif cDiff < 0 and rDiff > 0:
		attackRegion[6] = min(attackRegion[6], rDiff - 1)
	else:
		attackRegion[7] = min(attackRegion[7], -rDiff - 1)
print(sum(attackRegion))


import sys
Obstacles = [0] * 8
(n, k) = [int(x) for x in input().split()]
(rQ, cQ) = [int(x) for x in input().split()]
for _ in range(k):
	obs = tuple([int(x) for x in input().split()])
	if obs[0] == rQ and obs[1] > cQ:
		if Obstacles[0] == 0:
			Obstacles[0] = obs
		elif obs[1] < Obstacles[0][1]:
			Obstacles[0] = obs
	elif obs[0] == rQ and obs[1] < cQ:
		if Obstacles[1] == 0:
			Obstacles[1] = obs
		elif obs[1] > Obstacles[1][1]:
			Obstacles[1] = obs
	elif obs[1] == cQ and obs[0] > rQ:
		if Obstacles[2] == 0:
			Obstacles[2] = obs
		elif obs[0] < Obstacles[2][0]:
			Obstacles[2] = obs
	elif obs[1] == cQ and obs[0] < rQ:
		if Obstacles[3] == 0:
			Obstacles[3] = obs
		elif obs[0] > Obstacles[3][0]:
			Obstacles[3] = obs
	elif obs[0] - rQ == obs[1] - cQ and obs[0] - rQ > 0:
		if Obstacles[4] == 0:
			Obstacles[4] = obs
		elif obs[0] - rQ < Obstacles[4][0] - rQ:
			Obstacles[4] = obs
	elif obs[0] - rQ == cQ - obs[1] and obs[0] - rQ > 0:
		if Obstacles[5] == 0:
			Obstacles[5] = obs
		elif obs[0] - rQ < Obstacles[5][0] - rQ:
			Obstacles[5] = obs
	elif rQ - obs[0] == cQ - obs[1] and rQ - obs[0] > 0:
		if Obstacles[6] == 0:
			Obstacles[6] = obs
		elif rQ - obs[0] < rQ - Obstacles[6][0]:
			Obstacles[6] = obs
	elif rQ - obs[0] == obs[1] - cQ and rQ - obs[0] > 0:
		if Obstacles[7] == 0:
			Obstacles[7] = obs
		elif rQ - obs[0] < rQ - Obstacles[7][0]:
			Obstacles[7] = obs
attacks = 0
if Obstacles[0] == 0:
	attacks += n - cQ
else:
	attacks += Obstacles[0][1] - cQ - 1
if Obstacles[1] == 0:
	attacks += cQ - 1
else:
	attacks += cQ - Obstacles[1][1] - 1
if Obstacles[2] == 0:
	attacks += n - rQ
else:
	attacks += Obstacles[2][0] - rQ - 1
if Obstacles[3] == 0:
	attacks += rQ - 1
else:
	attacks += rQ - Obstacles[3][0] - 1
if Obstacles[4] == 0:
	attacks += min(n - rQ, n - cQ)
else:
	attacks += Obstacles[4][0] - rQ - 1
if Obstacles[5] == 0:
	attacks += min(n - rQ, cQ - 1)
else:
	attacks += Obstacles[5][0] - rQ - 1
if Obstacles[6] == 0:
	attacks += min(rQ - 1, cQ - 1)
else:
	attacks += rQ - Obstacles[6][0] - 1
if Obstacles[7] == 0:
	attacks += min(rQ - 1, n - cQ)
else:
	attacks += rQ - Obstacles[7][0] - 1
print(attacks)


def queen_squares(n, queenR, queenC, ob_list):
	closeR = n - queenC
	closeL = queenC - 1
	closeU = n - queenR
	closeD = queenR - 1
	closeRU = min(closeR, closeU)
	closeLU = min(closeL, closeU)
	closeDR = min(closeR, closeD)
	closeDL = min(closeL, closeD)
	for tup in ob_list:
		r = tup[0]
		c = tup[1]
		if r == queenR and c > queenC:
			if c - queenC - 1 < closeR:
				closeR = c - queenC - 1
		elif r == queenR and c < queenC:
			if queenC - c - 1 < closeL:
				closeL = queenC - c - 1
		elif c == queenC and r > queenR:
			if r - queenR - 1 < closeU:
				closeU = r - queenR - 1
		elif c == queenC and r < queenR:
			if queenR - r - 1 < closeD:
				closeD = queenR - r - 1
		elif c - queenC == r - queenR and r > queenR:
			if r - queenR - 1 < closeRU:
				closeRU = r - queenR - 1
		elif c - queenC == r - queenR and r < queenR:
			if queenR - r - 1 < closeDL:
				closeDL = queenR - r - 1
		elif c + r == queenR + queenC and c < queenC:
			if queenC - c - 1 < closeLU:
				closeLU = queenC - c - 1
		elif c + r == queenR + queenC and c > queenC:
			if c - queenC - 1 < closeDR:
				closeDR = c - queenC - 1
		else:
			pass
	return closeR + closeL + closeU + closeD + closeRU + closeDL + closeLU + closeDR
board_obstacles = input()
bolist = board_obstacles.split()
n = int(bolist[0])
k = int(bolist[1])
queen_loc = input()
queenlist = queen_loc.split()
queenR = int(queenlist[0])
queenC = int(queenlist[1])
ob_list = []
for x in range(0, k):
	ob = input()
	obtup = ob.split()
	obtup = tuple(map(int, obtup))
	ob_list.append(obtup)
count = queen_squares(n, queenR, queenC, ob_list)
print(count)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
Queen = {}
Queen['u'] = n - rQueen
Queen['d'] = rQueen - 1
Queen['l'] = cQueen - 1
Queen['r'] = n - cQueen
Queen['ul'] = min(n - rQueen, cQueen - 1)
Queen['ur'] = min(n - rQueen, n - cQueen)
Queen['dl'] = min(rQueen - 1, cQueen - 1)
Queen['dr'] = min(rQueen - 1, n - cQueen)
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if cObstacle == cQueen:
		if rObstacle > rQueen:
			Queen['u'] = min(Queen['u'], rObstacle - rQueen - 1)
		elif rObstacle < rQueen:
			Queen['d'] = min(Queen['d'], rQueen - rObstacle - 1)
	elif rObstacle == rQueen:
		if cObstacle < cQueen:
			Queen['l'] = min(Queen['l'], cQueen - cObstacle - 1)
		elif cObstacle > cQueen:
			Queen['r'] = min(Queen['r'], cObstacle - cQueen - 1)
	elif abs(rObstacle - rQueen) == abs(cObstacle - cQueen):
		dist = abs(rObstacle - rQueen) - 1
		if rObstacle > rQueen:
			if cObstacle > cQueen:
				Queen['ur'] = min(Queen['ur'], cObstacle - cQueen - 1)
			elif cObstacle < cQueen:
				Queen['ul'] = min(Queen['ul'], cQueen - cObstacle - 1)
		elif rObstacle < rQueen:
			if cObstacle > cQueen:
				Queen['dr'] = min(Queen['dr'], cObstacle - cQueen - 1)
			elif cObstacle < cQueen:
				Queen['dl'] = min(Queen['dl'], cQueen - cObstacle - 1)
print(Queen['u'] + Queen['d'] + Queen['r'] + Queen['l'] + Queen['ul'] + Queen['ur'] + Queen['dl'] + Queen['dr'])


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQ, cQ) = input().strip().split(' ')
(rQ, cQ) = [int(rQ), int(cQ)]
obs = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obs.add((rObstacle, cObstacle))
ans = 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
for d in directions:
	(r, c) = (rQ, cQ)
	while 1 <= r and r <= n and (1 <= c) and (c <= n):
		if (r, c) in obs:
			break
		else:
			ans += 1
			r += d[0]
			c += d[1]
print(ans - 8)


import sys
import math
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(r, c) = input().strip().split(' ')
(r, c) = [int(r), int(c)]
moves = []
moves.append(n - r)
moves.append(n - max(r, c))
moves.append(n - c)
moves.append(n - max(c, n - r + 1))
moves.append(r - 1)
moves.append(n - max(n - c + 1, n - r + 1))
moves.append(c - 1)
moves.append(n - max(n - c + 1, r))
for a0 in range(k):
	(rO, cO) = input().strip().split(' ')
	(rO, cO) = [int(rO), int(cO)]
	if rO == r:
		if cO < c:
			if moves[6] > c - cO - 1:
				moves[6] = c - cO - 1
		elif c < cO:
			if moves[2] > cO - c - 1:
				moves[2] = cO - c - 1
	elif cO == c:
		if rO < r:
			if moves[4] > r - rO - 1:
				moves[4] = r - rO - 1
		elif r < rO:
			if moves[0] > rO - r - 1:
				moves[0] = rO - r - 1
	elif rO - r == cO - c and cO - c > 0:
		if rO > r and cO > c:
			if moves[1] > rO - r - 1:
				moves[1] = rO - r - 1
	elif rO - r == cO - c and cO - c < 0:
		if rO < r and cO < c:
			if moves[5] > r - rO - 1:
				moves[5] = r - rO - 1
	elif rO - r == c - cO and rO - r > 0:
		if cO < c and rO > r:
			if moves[7] > c - cO - 1:
				moves[7] = c - cO - 1
	elif rO - r == c - cO and rO - r < 0:
		if cO > c and rO < r:
			if moves[3] > cO - c - 1:
				moves[3] = cO - c - 1
print(sum(moves))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
rQueen -= 1
cQueen -= 1
obstacles = {}
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	rObstacle -= 1
	cObstacle -= 1
	if rObstacle not in obstacles:
		obstacles[rObstacle] = [cObstacle]
	else:
		obstacles[rObstacle].append(cObstacle)
spaceCount = 0
travelUp = rQueen
travelDown = n - 1 - rQueen
travelLeft = cQueen
travelRight = n - 1 - cQueen
travelLength = travelUp
for i in range(1, travelLength + 1):
	x = rQueen - i
	y = cQueen
	if x not in obstacles or y not in obstacles[x]:
		spaceCount += 1
	else:
		break
travelLength = travelDown
for i in range(1, travelLength + 1):
	x = rQueen + i
	y = cQueen
	if x not in obstacles or y not in obstacles[x]:
		spaceCount += 1
	else:
		break
travelLength = travelLeft
for i in range(1, travelLength + 1):
	x = rQueen
	y = cQueen - i
	if x not in obstacles or y not in obstacles[x]:
		spaceCount += 1
	else:
		break
travelLength = travelRight
for i in range(1, travelLength + 1):
	x = rQueen
	y = cQueen + i
	if x not in obstacles or y not in obstacles[x]:
		spaceCount += 1
	else:
		break
travelLength = min(travelRight, travelUp)
for i in range(1, travelLength + 1):
	x = rQueen - i
	y = cQueen + i
	if x not in obstacles or y not in obstacles[x]:
		spaceCount += 1
	else:
		break
travelLength = min(travelLeft, travelDown)
for i in range(1, travelLength + 1):
	x = rQueen + i
	y = cQueen - i
	if x not in obstacles or y not in obstacles[x]:
		spaceCount += 1
	else:
		break
travelLength = min(travelLeft, travelUp)
for i in range(1, travelLength + 1):
	x = rQueen - i
	y = cQueen - i
	if x not in obstacles or y not in obstacles[x]:
		spaceCount += 1
	else:
		break
travelLength = min(travelRight, travelDown)
for i in range(1, travelLength + 1):
	x = rQueen + i
	y = cQueen + i
	if x not in obstacles or y not in obstacles[x]:
		spaceCount += 1
	else:
		break
print(spaceCount)


import sys

def calcHoriLeft(posX):
	return posX - 1

def calcHoriRight(posX, size):
	return size - posX

def calcVertUp(posY, size):
	return size - posY

def calcVerDown(posY):
	return posY - 1

def calcDiagonal1Up(posX, posY, size):
	return min([size - posX, size - posY])

def calcDiagonal1Down(posX, posY):
	return min([posX - 1, posY - 1])

def calcDiagonal2Up(posX, posY, size):
	return min([size - posY, posX - 1])

def calcDiagonal2Down(posX, posY, size):
	return min([size - posX, posY - 1])

def yDiagonalPrincipal(posX, posY, x):
	num = posY - posX
	return x + num

def yDiagonalSecundaria(posX, posY, x):
	num = posX + posY
	return num - x
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
vertD = calcVerDown(rQueen)
vertU = calcVertUp(rQueen, n)
horiL = calcHoriLeft(cQueen)
horiR = calcHoriRight(cQueen, n)
diag1U = calcDiagonal1Up(cQueen, rQueen, n)
diag1D = calcDiagonal1Down(cQueen, rQueen)
diag2U = calcDiagonal2Up(cQueen, rQueen, n)
diag2D = calcDiagonal2Down(cQueen, rQueen, n)
total = vertD + vertU + horiL + horiR + diag1U + diag1D + diag2U + diag2D
closestVertD = None
closestVertU = None
closestHoriL = None
closestHoriR = None
closestDiag1U = None
closestDiag1D = None
closestDiag2U = None
closestDiag2D = None
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if cQueen == cObstacle:
		if rQueen < rObstacle:
			if closestVertU is None or closestVertU[1] > rObstacle:
				closestVertU = [cObstacle, rObstacle]
		elif closestVertD is None or closestVertD[1] < rObstacle:
			closestVertD = [cObstacle, rObstacle]
	elif rQueen == rObstacle:
		if cQueen > cObstacle:
			if closestHoriL is None or closestHoriL[0] < cObstacle:
				closestHoriL = [cObstacle, rObstacle]
		elif closestHoriR is None or closestHoriR[0] > cObstacle:
			closestHoriR = [cObstacle, rObstacle]
	elif rObstacle == yDiagonalPrincipal(cQueen, rQueen, cObstacle):
		if rObstacle > rQueen:
			if closestDiag1U is None or closestDiag1U[1] > rObstacle:
				closestDiag1U = [cObstacle, rObstacle]
		elif closestDiag1D is None or closestDiag1D[1] < rObstacle:
			closestDiag1D = [cObstacle, rObstacle]
	elif rObstacle == yDiagonalSecundaria(cQueen, rQueen, cObstacle):
		if rObstacle > rQueen:
			if closestDiag2U is None or closestDiag2U[1] > rObstacle:
				closestDiag2U = [cObstacle, rObstacle]
		elif closestDiag2D is None or closestDiag2D[1] < rObstacle:
			closestDiag2D = [cObstacle, rObstacle]
if closestVertU is not None:
	total -= 1 + calcVertUp(closestVertU[1], n)
if closestVertD is not None:
	total -= 1 + calcVerDown(closestVertD[1])
if closestHoriL is not None:
	total -= 1 + calcHoriLeft(closestHoriL[0])
if closestHoriR is not None:
	total -= 1 + calcHoriRight(closestHoriR[0], n)
if closestDiag1U is not None:
	total -= 1 + calcDiagonal1Up(closestDiag1U[0], closestDiag1U[1], n)
if closestDiag1D is not None:
	total -= 1 + calcDiagonal1Down(closestDiag1D[0], closestDiag1D[1])
if closestDiag2U is not None:
	total -= 1 + calcDiagonal2Up(closestDiag2U[0], closestDiag2U[1], n)
if closestDiag2D is not None:
	total -= 1 + calcDiagonal2Down(closestDiag2D[0], closestDiag2D[1], n)
print(total)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(r, c) = (int(rQueen), int(cQueen))
ls = []
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = (int(rObstacle), int(cObstacle))
	ls.append((rObstacle, cObstacle))
ls = set(ls)
ans = 0
x = r
while x < n:
	x += 1
	if (x, c) in ls:
		break
	ans += 1
x = r
while x > 1:
	x -= 1
	if (x, c) in ls:
		break
	ans += 1
y = c
while y < n:
	y += 1
	if (r, y) in ls:
		break
	ans += 1
y = c
while y > 1:
	y -= 1
	if (r, y) in ls:
		break
	ans += 1
(x, y) = (r, c)
while x < n and y < n:
	x += 1
	y += 1
	if (x, y) in ls:
		break
	ans += 1
(x, y) = (r, c)
while x < n and y > 1:
	x += 1
	y -= 1
	if (x, y) in ls:
		break
	ans += 1
(x, y) = (r, c)
while x > 1 and y < n:
	x -= 1
	y += 1
	if (x, y) in ls:
		break
	ans += 1
(x, y) = (r, c)
while x > 1 and y > 1:
	x -= 1
	y -= 1
	if (x, y) in ls:
		break
	ans += 1
print(ans)


temp = input().split()
n = int(temp[0])
k = int(temp[1])
temp = input().split()
qx = int(temp[0])
qy = int(temp[1])
cObs = []
cObs.append(n - qy)
cObs.append(min(n - qx, n - qy))
cObs.append(n - qx)
cObs.append(min(n - qx, qy - 1))
cObs.append(qy - 1)
cObs.append(min(qx - 1, qy - 1))
cObs.append(qx - 1)
cObs.append(min(qx - 1, n - qy))
for i in range(k):
	temp = input().split()
	ox = int(temp[0])
	oy = int(temp[1])
	dx = ox - qx
	dy = oy - qy
	if dx == 0:
		if dy > 0:
			cObs[2] = min(cObs[2], dy - 1)
		else:
			cObs[6] = min(cObs[6], -dy - 1)
	elif dy == 0:
		if dx > 0:
			cObs[0] = min(cObs[0], dx - 1)
		else:
			cObs[4] = min(cObs[4], -dx - 1)
	elif abs(dx) == abs(dy):
		if dx == dy:
			if dy > 0:
				cObs[1] = min(cObs[1], dy - 1)
			else:
				cObs[5] = min(cObs[5], -dy - 1)
		elif dx > 0:
			cObs[3] = min(cObs[3], dx - 1)
		else:
			cObs[7] = min(cObs[7], -dx - 1)
print(sum(cObs))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rq, cq) = input().strip().split(' ')
(rq, cq) = [int(rq), int(cq)]
up = 10 ** 6
down = 10 ** 6
left = 10 ** 6
right = 10 ** 6
ld = 10 ** 6
rd = 10 ** 6
lu = 10 ** 6
ru = 10 ** 6
for a0 in range(k):
	(ro, co) = input().strip().split(' ')
	(ro, co) = [int(ro), int(co)]
	if ro == rq:
		if co > cq:
			if co - cq < right:
				right = co - cq
		elif cq - co < left:
			left = cq - co
	elif co == cq:
		if ro > rq:
			if ro - rq < up:
				up = ro - rq
		elif rq - ro < down:
			down = rq - ro
	elif rq - cq == ro - co:
		if co > cq:
			if co - cq < ru:
				ru = co - cq
		elif cq - co < ld:
			ld = cq - co
	elif rq - cq == ro - co:
		if co > cq:
			if co - cq < ru:
				ru = co - cq
		elif cq - co < ld:
			ld = cq - co
	elif rq - ro == co - cq:
		if co > cq:
			if co - cq < rd:
				rd = co - cq
		elif cq - co < lu:
			lu = cq - co
total = 0
total = total + min(rq - 1, down - 1)
total = total + min(cq - 1, left - 1)
total = total + min(n - rq, up - 1)
total = total + min(n - cq, right - 1)
total = total + min(min(rq, cq) - 1, ld - 1)
total = total + min(min(rq - 1, n - cq), rd - 1)
total = total + min(min(n - rq, cq - 1), lu - 1)
total = total + min(min(n - cq, n - rq), ru - 1)
print(total)


(n, k) = map(int, input().split())
(qx, qy) = map(int, input().split())
N = n + 1 - qy
E = n + 1 - qx
S = qy
W = qx
NE = min(N, E)
SE = min(S, E)
NW = min(N, W)
SW = min(S, W)
for _ in range(k):
	(ox, oy) = map(int, input().split())
	ox -= qx
	oy -= qy
	if not ox:
		if 0 < oy < N:
			N = oy
		elif 0 < -oy < S:
			S = -oy
	elif not oy:
		if 0 < ox < E:
			E = ox
		elif 0 < -ox < W:
			W = -ox
	elif ox == oy:
		if 0 < ox < NE:
			NE = ox
		elif 0 < -ox < SW:
			SW = -ox
	elif ox == -oy:
		if 0 < ox < SE:
			SE = ox
		elif 0 < oy < NW:
			NW = oy
print(N + E + S + W + NE + SE + NW + SW - 8)


import sys
(n, k) = map(int, input().strip().split(' '))
obs = set()
num_moves = 0
(rq, cq) = map(int, input().strip().split(' '))
for a0 in range(k):
	(ro, co) = map(int, input().strip().split(' '))
	obs.add((ro, co))
for i in range(rq + 1, n + 1):
	if (i, cq) in obs:
		break
	else:
		num_moves += 1
for i in range(rq - 1, 0, -1):
	if (i, cq) in obs:
		break
	else:
		num_moves += 1
for j in range(cq + 1, n + 1):
	if (rq, j) in obs:
		break
	else:
		num_moves += 1
for j in range(cq - 1, 0, -1):
	if (rq, j) in obs:
		break
	else:
		num_moves += 1
i = rq + 1
j = cq + 1
while i <= n and j <= n:
	if (i, j) in obs:
		break
	else:
		num_moves += 1
	i += 1
	j += 1
i = rq - 1
j = cq - 1
while i > 0 and j > 0:
	if (i, j) in obs:
		break
	else:
		num_moves += 1
	i -= 1
	j -= 1
i = rq - 1
j = cq + 1
while i > 0 and j <= n:
	if (i, j) in obs:
		break
	else:
		num_moves += 1
	i -= 1
	j += 1
i = rq + 1
j = cq - 1
while i <= n and j > 0:
	if (i, j) in obs:
		break
	else:
		num_moves += 1
	i += 1
	j -= 1
print(num_moves)


(n, k) = map(int, input().split())
(qx, qy) = map(int, input().split())
obs = {}
for i in range(8):
	obs[i + 1] = []

def d(a, q):
	return abs(a[0] - q[0]) + abs(a[1] - q[1])

def h(a, b, q):
	if d(a, q) < d(b, q):
		return a
	else:
		return b

def update(q, i):
	if obs[i] == []:
		obs[i] = [q]
	else:
		obs[i] = [h(obs[i][0], q, (qx, qy))]
for _ in range(k):
	(ox, oy) = map(int, input().split())
	if ox == qx:
		if oy > qy:
			update((ox, oy), 2)
		else:
			update((ox, oy), 6)
	elif oy == qy:
		if ox > qx:
			update((ox, oy), 8)
		else:
			update((ox, oy), 4)
	elif abs(ox - qx) == abs(oy - qy):
		if ox > qx and oy > qy:
			update((ox, oy), 1)
		elif ox < qx and oy > qy:
			update((ox, oy), 3)
		elif ox < qx and oy < qy:
			update((ox, oy), 5)
		else:
			update((ox, oy), 7)
	else:
		pass
s = 0
s += min(abs(n - qx), abs(n - qy))
if obs[1] != []:
	(tx, ty) = obs[1][0]
	s -= min(abs(n - tx), abs(n - ty)) + 1
s += n - qy
if obs[2] != []:
	s -= n - obs[2][0][1] + 1
s += min(abs(qx - 1), abs(n - qy))
if obs[3] != []:
	(tx, ty) = obs[3][0]
	s -= min(abs(tx - 1), abs(n - ty)) + 1
s += qx - 1
if obs[4] != []:
	s -= obs[4][0][0]
s += min(abs(qx - 1), abs(qy - 1))
if obs[5] != []:
	(tx, ty) = obs[5][0]
	s -= min(abs(tx - 1), abs(ty - 1)) + 1
s += qy - 1
if obs[6] != []:
	s -= obs[6][0][1]
s += min(abs(n - qx), abs(qy - 1))
if obs[7] != []:
	(tx, ty) = obs[7][0]
	s -= min(abs(n - tx), abs(ty - 1)) + 1
s += n - qx
if obs[8] != []:
	s -= n - obs[8][0][0] + 1
print(s)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
queen_pos = [int(rQueen), int(cQueen)]
queen_diff = abs(queen_pos[0] - queen_pos[1])
queen_add = queen_pos[0] + queen_pos[1]

def num_check(input_list):
	if max(input_list) <= n:
		if min(input_list) >= 1:
			return input_list
vert_up = []
vert_down = []
horz_left = []
horz_right = []
q_up_right = []
q_down_left = []
q_up_left = []
q_down_right = []
for num in range(1, n + 1):
	input_coord1 = [queen_pos[0], num]
	if num < queen_pos[1]:
		horz_left.append(input_coord1)
	if num > queen_pos[1]:
		horz_right.append(input_coord1)
	input_coord2 = [num, queen_pos[1]]
	if num < queen_pos[0]:
		vert_down.append(input_coord2)
	if num > queen_pos[0]:
		vert_up.append(input_coord2)
	input_coord3 = num_check([queen_pos[0] + num, queen_pos[1] + num])
	if input_coord3 != None:
		q_up_right.append(input_coord3)
	input_coord4 = num_check([queen_pos[0] - num, queen_pos[1] - num])
	if input_coord4 != None:
		q_down_left.append(input_coord4)
	input_coord5 = num_check([queen_pos[0] + num, queen_pos[1] - num])
	if input_coord5 != None:
		q_up_left.append(input_coord5)
	input_coord6 = num_check([queen_pos[0] - num, queen_pos[1] + num])
	if input_coord6 != None:
		q_down_right.append(input_coord6)
horz_right.reverse()
vert_up.reverse()
q_up_right.reverse()
q_down_left.reverse()
q_up_left.reverse()
q_down_right.reverse()

def check(input_list):
	for (index, item) in enumerate(input_list):
		if item == obs_positions:
			input_list.pop(index)
			input_list = input_list[index:]
	return input_list
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obs_positions = [int(rObstacle), int(cObstacle)]
	obs_diff = abs(obs_positions[0] - obs_positions[1])
	obs_add = obs_positions[0] + obs_positions[1]
	if obs_positions[0] == queen_pos[0]:
		if obs_positions[1] < queen_pos[1]:
			horz_left = check(horz_left)
		if obs_positions[1] > queen_pos[1]:
			horz_right = check(horz_right)
	if obs_positions[1] == queen_pos[1]:
		if obs_positions[0] < queen_pos[0]:
			vert_down = check(vert_down)
		if obs_positions[0] > queen_pos[0]:
			vert_up = check(vert_up)
	if queen_diff == obs_diff:
		if obs_positions[0] < queen_pos[0]:
			q_down_left = check(q_down_left)
		if obs_positions[0] > queen_pos[0]:
			q_up_right = check(q_up_right)
	if queen_add == obs_add:
		if obs_positions[0] > queen_pos[0]:
			q_up_left = check(q_up_left)
		if obs_positions[0] < queen_pos[0]:
			q_down_right = check(q_down_right)
all_q_pos = []

def append_list(input_list):
	if input_list:
		for item in input_list:
			all_q_pos.append(item)
append_list(horz_left)
append_list(horz_right)
append_list(vert_up)
append_list(vert_down)
append_list(q_up_right)
append_list(q_down_left)
append_list(q_up_left)
append_list(q_down_right)
print(len(all_q_pos))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
ob = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	ob.add((rObstacle, cObstacle))
moves = [-1, 0, 1]
total = 0
for r in moves:
	for c in moves:
		if not (r == 0 and c == 0):
			rQ = rQueen + r
			cQ = cQueen + c
			while rQ in range(1, n + 1) and cQ in range(1, n + 1):
				if (rQ, cQ) in ob:
					rQ = rQueen
					cQ = cQueen
					break
				else:
					total += 1
					rQ = rQ + r
					cQ = cQ + c
print(total)


import sys
import math
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
t = []
g = 0
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	(r, c) = (rQueen - rObstacle, cQueen - cObstacle)
	if r == 0 or c == 0 or abs(r) == abs(c):
		t += [[rObstacle, cObstacle]]
r = 1
while rQueen - r > 0:
	if [rQueen - r, cQueen] not in t:
		g += 1
	else:
		break
	r += 1
r = 1
while rQueen + r <= n:
	if [rQueen + r, cQueen] not in t:
		g += 1
	else:
		break
	r += 1
c = 1
while cQueen - c > 0:
	if [rQueen, cQueen - c] not in t:
		g += 1
	else:
		break
	c += 1
c = 1
while cQueen + c <= n:
	if [rQueen, cQueen + c] not in t:
		g += 1
	else:
		break
	c += 1
(c, r) = (1, 1)
while cQueen - c > 0 and rQueen - r > 0:
	if [rQueen - r, cQueen - c] not in t:
		g += 1
	else:
		break
	c += 1
	r += 1
(r, c) = (1, 1)
while cQueen + c <= n and rQueen + r <= n:
	if [rQueen + r, cQueen + c] not in t:
		g += 1
	else:
		break
	c += 1
	r += 1
(c, r) = (1, 1)
while cQueen + c <= n and rQueen - r > 0:
	if [rQueen - r, cQueen + c] not in t:
		g += 1
	else:
		break
	c += 1
	r += 1
(c, r) = (1, 1)
while cQueen - c > 0 and rQueen + r <= n:
	if [rQueen + r, cQueen - c] not in t:
		g += 1
	else:
		break
	c += 1
	r += 1
print(g)


import sys
(n, k) = tuple(map(int, input().strip().split(' ')))
(qi, qj) = tuple(map(int, input().strip().split(' ')))
s = set()
for a0 in range(k):
	s.add(tuple(map(int, input().strip().split(' '))))
resCount = 0
for i in range(qi + 1, n + 1):
	if (i, qj) not in s:
		resCount += 1
	else:
		break
for i in range(qi - 1, 0, -1):
	if (i, qj) not in s:
		resCount += 1
	else:
		break
for j in range(qj - 1, 0, -1):
	if (qi, j) not in s:
		resCount += 1
	else:
		break
for j in range(qj + 1, n + 1):
	if (qi, j) not in s:
		resCount += 1
	else:
		break
for (i, j) in zip(range(qi + 1, n + 1), range(qj + 1, n + 1)):
	if (i, j) not in s:
		resCount += 1
	else:
		break
for (i, j) in zip(range(qi + 1, n + 1), range(qj - 1, 0, -1)):
	if (i, j) not in s:
		resCount += 1
	else:
		break
for (i, j) in zip(range(qi - 1, 0, -1), range(qj + 1, n + 1)):
	if (i, j) not in s:
		resCount += 1
	else:
		break
for (i, j) in zip(range(qi - 1, 0, -1), range(qj - 1, 0, -1)):
	if (i, j) not in s:
		resCount += 1
	else:
		break
print(resCount)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rq, cq) = input().strip().split(' ')
(rq, cq) = [int(rq), int(cq)]
top = (n + 1, cq)
bottom = (0, cq)
right = (rq, n + 1)
left = (rq, 0)
d = min(n + 1 - rq, n + 1 - cq)
top_right = (rq + d, cq + d)
d = min(n + 1 - rq, cq)
top_left = (rq + d, cq - d)
d = min(rq, n + 1 - cq)
bottom_right = (rq - d, cq + d)
d = min(rq, cq)
bottom_left = (rq - d, cq - d)
for a0 in range(k):
	(ro, co) = input().strip().split(' ')
	(ro, co) = [int(ro), int(co)]
	if co == cq:
		if ro > rq:
			top = (min(top[0], ro), cq)
		else:
			bottom = (max(bottom[0], ro), cq)
	elif co < cq:
		if ro == rq:
			left = (rq, max(left[1], co))
		elif cq - co == abs(rq - ro):
			if ro < rq:
				d = min(cq - bottom_left[1], cq - co)
				bottom_left = (rq - d, cq - d)
			else:
				d = min(cq - top_left[1], cq - co)
				top_left = (rq + d, cq - d)
	elif co > cq:
		if ro == rq:
			right = (rq, min(right[1], co))
		elif co - cq == abs(ro - rq):
			if ro < rq:
				d = min(bottom_right[1] - cq, co - cq)
				bottom_right = (rq - d, cq + d)
			else:
				d = min(top_right[1] - cq, co - cq)
				top_right = (rq + d, cq + d)
count = top[0] - rq - 1
count += rq - bottom[0] - 1
count += right[1] - cq - 1
count += cq - left[1] - 1
count += top_right[1] - cq - 1
count += bottom_right[1] - cq - 1
count += cq - top_left[1] - 1
count += cq - bottom_left[1] - 1
print(count)


import sys

def dfs(pos, num_squares, dir):
	while pos[0] >= 0 and pos[0] < n and (pos[1] < n) and (pos[1] >= 0):
		if (pos[0], pos[1]) in obstacles:
			break
		else:
			pos[0] += dir[0]
			pos[1] += dir[1]
			num_squares += 1
	return num_squares
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen) - 1, int(cQueen) - 1]
obstacles = {}
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obstacles[rObstacle - 1, cObstacle - 1] = True
result = dfs([rQueen - 1, cQueen - 1], 0, (-1, -1)) + dfs([rQueen - 1, cQueen], 0, (-1, 0)) + dfs([rQueen - 1, cQueen + 1], 0, (-1, 1)) + dfs([rQueen, cQueen + 1], 0, (0, 1)) + dfs([rQueen + 1, cQueen + 1], 0, (1, 1)) + dfs([rQueen + 1, cQueen], 0, (1, 0)) + dfs([rQueen + 1, cQueen - 1], 0, (1, -1)) + dfs([rQueen, cQueen - 1], 0, (0, -1))
print(result)


def check_block(q_pos, obs_pos):
	return q_pos[0] == obs_pos[0] or q_pos[1] == obs_pos[1] or abs(q_pos[0] - obs_pos[0]) == abs(q_pos[1] - obs_pos[1])
(n, k) = map(int, input().split())
queen_pos = list(map(int, input().split()))
obstacles = [list(map(int, input().split())) for a0 in range(k)]
blocks = [obs for obs in obstacles if check_block(queen_pos, obs)]
c = 0
for i in range(1, n):
	if queen_pos[0] - i >= 1 and [queen_pos[0] - i, queen_pos[1]] not in blocks:
		c += 1
	else:
		break
for i in range(1, n):
	if queen_pos[1] - i >= 1 and [queen_pos[0], queen_pos[1] - i] not in blocks:
		c += 1
	else:
		break
for i in range(1, n):
	if queen_pos[0] + i <= n and [queen_pos[0] + i, queen_pos[1]] not in blocks:
		c += 1
	else:
		break
for i in range(1, n):
	if queen_pos[1] + i <= n and [queen_pos[0], queen_pos[1] + i] not in blocks:
		c += 1
	else:
		break
for i in range(1, n):
	if queen_pos[0] + i <= n and queen_pos[1] + i <= n and ([queen_pos[0] + i, queen_pos[1] + i] not in blocks):
		c += 1
	else:
		break
for i in range(1, n):
	if queen_pos[0] - i >= 1 and queen_pos[1] - i >= 1 and ([queen_pos[0] - i, queen_pos[1] - i] not in blocks):
		c += 1
	else:
		break
for i in range(1, n):
	if queen_pos[0] + i <= n and queen_pos[1] - i >= 1 and ([queen_pos[0] + i, queen_pos[1] - i] not in blocks):
		c += 1
	else:
		break
for i in range(1, n):
	if queen_pos[0] - i >= 1 and queen_pos[1] + i <= n and ([queen_pos[0] - i, queen_pos[1] + i] not in blocks):
		c += 1
	else:
		break
print(c)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
a = [n + 1, 0, n + 1, 0, min(n + 1, rQueen + cQueen), max(0, rQueen + cQueen - n - 1), min(n + 1, n + 1 - rQueen + cQueen), max(0, -rQueen + cQueen)]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle > cQueen:
			a[0] = min(a[0], cObstacle)
		else:
			a[1] = max(a[1], cObstacle)
	elif cObstacle == cQueen:
		if rObstacle > rQueen:
			a[2] = min(a[2], rObstacle)
		else:
			a[3] = max(a[3], rObstacle)
	elif rObstacle + cObstacle == rQueen + cQueen:
		if cObstacle > cQueen:
			a[4] = min(a[4], cObstacle)
		else:
			a[5] = max(a[5], cObstacle)
	elif rObstacle - cObstacle == rQueen - cQueen:
		if cObstacle > cQueen:
			a[6] = min(a[6], cObstacle)
		else:
			a[7] = max(a[7], cObstacle)
print(-(a[1] - a[0] + a[3] - a[2] + a[5] - a[4] + a[7] - a[6]) - 8)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
arr = [min(n - rQueen, cQueen - 1), n - rQueen, min(n - rQueen, n - cQueen), cQueen - 1, n - cQueen, min(rQueen - 1, cQueen - 1), rQueen - 1, min(rQueen - 1, n - cQueen)]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle < cQueen:
			arr[3] = min(arr[3], abs(cObstacle - cQueen) - 1)
		else:
			arr[4] = min(arr[4], abs(cObstacle - cQueen) - 1)
	elif rObstacle > rQueen:
		if cObstacle > cQueen and abs(cObstacle - cQueen) == abs(rObstacle - rQueen):
			arr[2] = min(arr[2], abs(cObstacle - cQueen) - 1)
		elif cObstacle < cQueen and abs(cObstacle - cQueen) == abs(rObstacle - rQueen):
			arr[0] = min(arr[0], abs(cObstacle - cQueen) - 1)
		elif cObstacle == cQueen:
			arr[1] = min(arr[1], abs(rObstacle - rQueen) - 1)
	elif rObstacle < rQueen:
		if cObstacle > cQueen and abs(cObstacle - cQueen) == abs(rObstacle - rQueen):
			arr[7] = min(arr[7], abs(cObstacle - cQueen) - 1)
		elif cObstacle < cQueen and abs(cObstacle - cQueen) == abs(rObstacle - rQueen):
			arr[5] = min(arr[5], abs(cObstacle - cQueen) - 1)
		elif cObstacle == cQueen:
			arr[6] = min(arr[6], abs(rObstacle - rQueen) - 1)
print(sum(arr))


(n, k) = (int(x) for x in input().split())
(rq, cq) = (int(x) for x in input().split())
minLeftRow = cq - 1
minRightRow = n - cq
minTopCol = n - rq
minBotCol = rq - 1
minUpperLeftDia = min(minLeftRow, minBotCol)
minLowerLeftDia = min(minLeftRow, minTopCol)
minUpperRightDia = min(minRightRow, minTopCol)
minLowerRightDia = min(minRightRow, minBotCol)
for _ in range(k):
	(r, c) = (int(x) for x in input().split())
	if rq == r:
		v = cq - c
		if v >= 0:
			v -= 1
			if minLeftRow > v:
				minLeftRow = v
		else:
			v += 1
			v *= -1
			if minRightRow > v:
				minRightRow = v
	elif cq == c:
		v = rq - r
		if v >= 0:
			v -= 1
			if minBotCol > v:
				minBotCol = v
		else:
			v += 1
			v *= -1
			if minTopCol > v:
				minTopCol = v
	elif r - c == rq - cq:
		v = cq - c
		if v >= 0:
			v -= 1
			if minUpperLeftDia > v:
				minUpperLeftDia = v
		else:
			v += 1
			v *= -1
			if minUpperRightDia > v:
				minUpperRightDia = v
	elif rq - r == c - cq:
		v = cq - c
		if v >= 0:
			v -= 1
			if minLowerLeftDia > v:
				minLowerLeftDia = v
		else:
			v += 1
			v *= -1
			if minLowerRightDia > v:
				minLowerRightDia = v
print(minLeftRow + minRightRow + minTopCol + minBotCol + minUpperLeftDia + minUpperRightDia + minLowerRightDia + minLowerLeftDia)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQ, cQ) = input().strip().split(' ')
(rQ, cQ) = [int(rQ), int(cQ)]
if n in [0, 1]:
	print(0)
else:
	ctrN = n - rQ + 1
	ctrS = rQ
	ctrE = n - cQ + 1
	ctrW = cQ
	ctrNE = min(n - rQ, n - cQ) + 1
	ctrSE = min(rQ - 1, n - cQ) + 1
	ctrSW = min(rQ - 1, cQ - 1) + 1
	ctrNW = min(n - rQ, cQ - 1) + 1
	for a0 in range(k):
		(rO, cO) = input().strip().split(' ')
		(rO, cO) = [int(rO), int(cO)]
		if cO == cQ:
			rProx = abs(rQ - rO)
			if rO > rQ:
				ctrN = min(ctrN, rProx)
			else:
				ctrS = min(ctrS, rProx)
		elif rO == rQ:
			cProx = abs(cQ - cO)
			if cO < cQ:
				ctrW = min(ctrW, cProx)
			else:
				ctrE = min(ctrE, cProx)
		else:
			rProx = abs(rQ - rO)
			cProx = abs(cQ - cO)
			if rProx == cProx:
				if rQ < rO:
					if cQ < cO:
						ctrNE = min(ctrNE, rProx)
					else:
						ctrNW = min(ctrNW, rProx)
				elif rQ > rO:
					if cQ < cO:
						ctrSE = min(ctrSE, rProx)
					else:
						ctrSW = min(ctrSW, rProx)
	total = ctrN - 1 + (ctrS - 1) + (ctrE - 1) + (ctrW - 1) + (ctrNE - 1) + (ctrSE - 1) + (ctrNW - 1) + (ctrSW - 1)
	print(total)


import sys

def alg(n, k, rQueen, cQueen, obstables):
	total = 0
	obNS = [n + 1 - rQueen, 0 - rQueen] + [o[0] - rQueen for o in obstables if o[1] == cQueen]
	total += min([o for o in obNS if o > 0]) - 1
	total += -max([o for o in obNS if o < 0]) - 1
	obEW = [n + 1 - cQueen, 0 - cQueen] + [o[1] - cQueen for o in obstables if o[0] == rQueen]
	total += min([o for o in obEW if o > 0]) - 1
	total += -max([o for o in obEW if o < 0]) - 1
	obD1 = [min(n + 1 - rQueen, n + 1 - cQueen), max(0 - rQueen, 0 - cQueen)] + [o[1] - cQueen for o in obstables if o[0] - rQueen == o[1] - cQueen]
	total += min([o for o in obD1 if o > 0]) - 1
	total += -max([o for o in obD1 if o < 0]) - 1
	obD2 = [min(rQueen - 0, n + 1 - cQueen), max(rQueen - n - 1, 0 - cQueen)] + [o[1] - cQueen for o in obstables if o[0] - cQueen == rQueen - o[1]]
	total += min([o for o in obD2 if o > 0]) - 1
	total += -max([o for o in obD2 if o < 0]) - 1
	return total
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
obstables = []
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	obstables.append([int(rObstacle), int(cObstacle)])
print(alg(n, k, rQueen, cQueen, obstables))


(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(qr, qc) = input().strip().split(' ')
(qr, qc) = [int(qr) - 1, int(qc) - 1]

class Obs:

	def __init__(self, r, c):
		self.r = r
		self.c = c

	def max_row(self, other):
		return self if self.r > other.r else other

	def min_row(self, other):
		return other if self.r > other.r else self

	def max_column(self, other):
		return self if self.c > other.c else other

	def min_column(self, other):
		return other if self.c > other.c else self

	def __str__(self):
		return '({}, {})'.format(self.r, self.c)
obstacle_matrix = [[Obs(-1, -1), Obs(-1, qc), Obs(-1, n)], [Obs(qr, -1), Obs(qr, qc), Obs(qr, n)], [Obs(n, -1), Obs(n, qc), Obs(n, n)]]
for i in range(k):
	(ir, ic) = input().strip().split(' ')
	(ir, ic) = [int(ir) - 1, int(ic) - 1]
	o = Obs(ir, ic)
	if ir == qr:
		if ic < qc:
			obstacle_matrix[1][0] = obstacle_matrix[1][0].max_column(o)
		else:
			obstacle_matrix[1][2] = obstacle_matrix[1][2].min_column(o)
	elif ic == qc:
		if ir < qr:
			obstacle_matrix[0][1] = obstacle_matrix[0][1].max_row(o)
		else:
			obstacle_matrix[2][1] = obstacle_matrix[2][1].min_row(o)
	elif abs(ic - qc) == abs(ir - qr):
		if ic < qc:
			if ir < qr:
				obstacle_matrix[0][0] = obstacle_matrix[0][0].max_row(o)
			else:
				obstacle_matrix[2][0] = obstacle_matrix[2][0].min_row(o)
		elif ir < qr:
			obstacle_matrix[0][2] = obstacle_matrix[0][2].max_row(o)
		else:
			obstacle_matrix[2][2] = obstacle_matrix[2][2].min_row(o)
attacking = 0
attacking += abs(obstacle_matrix[1][0].c - qc)
attacking += abs(obstacle_matrix[1][2].c - qc)
attacking += abs(obstacle_matrix[0][1].r - qr)
attacking += abs(obstacle_matrix[2][1].r - qr)
attacking += min(abs(obstacle_matrix[2][0].r - qr), abs(obstacle_matrix[2][0].c - qc))
attacking += min(abs(obstacle_matrix[2][2].r - qr), abs(obstacle_matrix[2][2].c - qc))
attacking += min(abs(obstacle_matrix[0][0].r - qr), abs(obstacle_matrix[0][0].c - qc))
attacking += min(abs(obstacle_matrix[0][2].r - qr), abs(obstacle_matrix[0][2].c - qc))
attacking -= 8
print(attacking)


def get_dir_dist(q, t):
	(x_d, y_d) = (t[0] - q[0], t[1] - q[1])
	dist = max(abs(x_d), abs(y_d))
	if x_d == y_d:
		return ('ur', dist) if x_d > 0 else ('ll', dist)
	elif x_d == -y_d:
		return ('lr', dist) if x_d > 0 else ('ul', dist)
	elif x_d == 0:
		return ('up', dist) if y_d > 0 else ('lo', dist)
	elif y_d == 0:
		return ('ri', dist) if x_d > 0 else ('le', dist)
	return None

def init_min_dist_dict(n, q):
	(q_x, q_y) = q
	(upper, lower) = ((q_x, n), (q_x, 1))
	(left, right) = ((1, q_y), (n, q_y))
	left_margin = q_x - 1
	lower_margin = q_y - 1
	right_margin = n - q_x
	upper_margin = n - q_y
	(ul_m, ur_m, lr_m, ll_m) = (min(left_margin, upper_margin), min(upper_margin, right_margin), min(right_margin, lower_margin), min(lower_margin, left_margin))
	upper_left = (q_x - ul_m, q_y + ul_m)
	upper_right = (q_x + ur_m, q_y + ur_m)
	lower_right = (q_x + lr_m, q_y - lr_m)
	lower_left = (q_x - ll_m, q_y - ll_m)
	dd = {}
	(dd['le'], dd['ri']) = (get_dir_dist(q, left)[1], get_dir_dist(q, right)[1])
	(dd['up'], dd['lo']) = (get_dir_dist(q, upper)[1], get_dir_dist(q, lower)[1])
	(dd['ul'], dd['ur']) = (get_dir_dist(q, upper_left)[1], get_dir_dist(q, upper_right)[1])
	(dd['ll'], dd['lr']) = (get_dir_dist(q, lower_left)[1], get_dir_dist(q, lower_right)[1])
	return dd
(n, k) = [int(num) for num in input().strip().split(' ')]
q = tuple((int(num) for num in input().strip().split(' ')))
dd = init_min_dist_dict(n, q)
for a0 in range(k):
	t = tuple((int(n) for n in input().strip().split(' ')))
	temp = get_dir_dist(q, t)
	if temp:
		(direction, dist) = temp
		dd[direction] = min(dd[direction], dist - 1)
print(sum((dd[k] for k in dd)))


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
total = 0
obstacles = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obstacles.add((rObstacle, cObstacle))
for i in range(cQueen - 1, 0, -1):
	if (rQueen, i) in obstacles:
		break
	total += 1
for i in range(cQueen + 1, n + 1):
	if (rQueen, i) in obstacles:
		break
	total += 1
for i in range(rQueen - 1, 0, -1):
	if (i, cQueen) in obstacles:
		break
	total += 1
for i in range(rQueen + 1, n + 1):
	if (i, cQueen) in obstacles:
		break
	total += 1
temp = min(rQueen, cQueen)
for i in range(1, temp):
	if (rQueen - i, cQueen - i) in obstacles:
		break
	total += 1
temp = max(rQueen, cQueen)
for i in range(1, n - temp + 1):
	if (rQueen + i, cQueen + i) in obstacles:
		break
	total += 1
temp = min(n - rQueen, cQueen - 1)
for i in range(1, temp + 1):
	if (rQueen + i, cQueen - i) in obstacles:
		break
	total += 1
temp = min(rQueen - 1, n - cQueen)
for i in range(1, temp + 1):
	if (rQueen - i, cQueen + i) in obstacles:
		break
	total += 1
print(total)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQ, cQ) = map(int, input().split())
moves = 0
down = rQ - 1
up = n - rQ
left = cQ - 1
right = n - cQ
diag1 = min(left, up)
diag2 = min(left, down)
diag3 = min(right, down)
diag4 = min(right, up)
d = {'Q1': diag1, 'Q2': diag2, 'Q3': diag3, 'Q4': diag4, 'up': up, 'down': down, 'left': left, 'right': right}
D = {'Q1': 0, 'Q2': 0, 'Q3': 0, 'Q4': 0, 'up': 0, 'down': 0, 'left': 0, 'right': 0}
for a0 in range(k):
	(rOb, cOb) = map(int, input().split())
	r = rOb - rQ
	c = cOb - cQ
	if abs(r) == abs(c):
		if r < 0 and c < 0:
			if D['Q2'] == 0:
				D['Q2'] = abs(r)
			elif abs(r) < D['Q2']:
				D['Q2'] = abs(r)
		elif r < 0 and c > 0:
			if D['Q3'] == 0:
				D['Q3'] = c
			elif c < D['Q3']:
				D['Q3'] = c
		elif r > 0 and c > 0:
			if D['Q4'] == 0:
				D['Q4'] = r
			elif r < D['Q4']:
				D['Q4'] = r
		elif r > 0 and c < 0:
			if D['Q1'] == 0:
				D['Q1'] = r
			elif r < D['Q1']:
				D['Q1'] = r
	elif 0 in {r, c}:
		if r == 0 and c < 0:
			if D['left'] == 0:
				D['left'] = abs(c)
			elif abs(c) < D['left']:
				D['left'] = abs(c)
		if r == 0 and c > 0:
			if D['right'] == 0:
				D['right'] = c
			elif c < D['right']:
				D['right'] = c
		if r < 0 and c == 0:
			if D['down'] == 0:
				D['down'] = abs(r)
			elif abs(r) < D['down']:
				D['down'] = abs(r)
		if r > 0 and c == 0:
			if D['up'] == 0:
				D['up'] = r
			elif r < D['up']:
				D['up'] = r
for i in D.keys():
	if D[i] == 0:
		moves += d[i]
	else:
		moves += D[i] - 1
print(moves)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, 1), (-1, 1), (1, -1)]

def in_range(row, col):
	return 1 <= row <= n and 1 <= col <= n
obstacles = set()
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	obstacles.add((rObstacle, cObstacle))
result = 0
for direction in DIRS:
	(cur_row, cur_col) = (rQueen, cQueen)
	while True:
		cur_row += direction[0]
		cur_col += direction[1]
		if in_range(cur_row, cur_col) and (cur_row, cur_col) not in obstacles:
			result += 1
		else:
			break
print(result)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(qy, qx) = [int(rQueen) - 1, int(cQueen) - 1]
dis = [qy + 1, qx + 1, n - qy, n - qx]
for i in range(4):
	dis.append(min(dis[i], dis[(i + 1) % 4]))
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(y, x) = [int(rObstacle) - 1, int(cObstacle) - 1]
	(dy, dx) = (y - qy, x - qx)
	assert dx != 0 or dy != 0
	if dy != 0 and dx != 0 and (abs(dx) != abs(dy)):
		continue
	d = max(abs(dy), abs(dx))
	i = -1
	if dx == 0 and dy < 0:
		i = 0
	if dy == 0 and dx < 0:
		i = 1
	if dx == 0 and dy > 0:
		i = 2
	if dy == 0 and dx > 0:
		i = 3
	if dy < 0 and dx < 0:
		i = 4
	if dy > 0 and dx < 0:
		i = 5
	if dy > 0 and dx > 0:
		i = 6
	if dy < 0 and dx > 0:
		i = 7
	assert 0 <= i and i < 8
	dis[i] = min(dis[i], d)
t = sum([d - 1 for d in dis])
print(t)


read_numbers = lambda : tuple((int(x) for x in input().strip().split(' ')))
moves = ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1))
(n, k) = read_numbers()
q = read_numbers()
obstacles = {read_numbers() for o in range(k)}

def check_for_border_single(counter, move, idx):
	find_next_field = lambda : q[idx] + counter * move[idx]
	v = find_next_field()
	if v > 0 and v <= n:
		return v
	return None

def check_for_border(counter, move):
	next_field = tuple((check_for_border_single(counter, move, x) for x in range(2)))
	if all(next_field):
		return next_field
	return None
possible_move_counter = 0
for m in moves:
	counter = 1
	while True:
		next_field = check_for_border(counter, m)
		if next_field and next_field not in obstacles:
			possible_move_counter += 1
			counter += 1
		else:
			break
print(possible_move_counter)


import sys
from math import sqrt
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(yQ, xQ) = input().strip().split(' ')
(yQ, xQ) = [int(yQ), int(xQ)]
yMax = n
yMin = 1
xMax = n
xMin = 1
d1_c = yQ - xQ
d1_xMax = min(n - d1_c, n)
d1_yMax = min(n + d1_c, n)
d1_xMin = max(1 - d1_c, 1)
d1_yMin = max(1 + d1_c, 1)
d2_c = yQ + xQ
d2_xMax = max(d2_c - n, 1)
d2_yMax = min(d2_c - 1, n)
d2_xMin = min(d2_c - 1, n)
d2_yMin = max(d2_c - n, 1)
for a0 in range(k):
	(yO, xO) = input().strip().split(' ')
	(yO, xO) = [int(yO), int(xO)]
	if yO == yQ:
		if xO > xQ:
			xMax = min(xMax, xO - 1)
		else:
			xMin = max(xMin, xO + 1)
	elif xO == xQ:
		if yO > yQ:
			yMax = min(yMax, yO - 1)
		else:
			yMin = max(yMin, yO + 1)
	elif yO == xO + d1_c:
		if yO > yQ:
			d1_xMax = min(d1_xMax, xO - 1)
			d1_yMax = min(d1_yMax, yO - 1)
		else:
			d1_xMin = max(d1_xMin, xO + 1)
			d1_yMin = max(d1_yMin, yO + 1)
	elif yO == -1.0 * xO + d2_c:
		if xO < xQ:
			d2_xMax = max(d2_xMax, xO + 1)
			d2_yMax = min(d2_yMax, yO - 1)
		else:
			d2_xMin = min(d2_xMin, xO - 1)
			d2_yMin = max(d2_yMin, yO + 1)
total_moves = 0
total_moves += yMax - yQ
total_moves += yQ - yMin
total_moves += xMax - xQ
total_moves += xQ - xMin
total_moves += sqrt((d1_yMax - yQ) ** 2 + (d1_xMax - xQ) ** 2) / sqrt(2.0)
total_moves += sqrt((d1_yMin - yQ) ** 2 + (d1_xMin - xQ) ** 2) / sqrt(2.0)
total_moves += sqrt((d2_yMax - yQ) ** 2 + (d2_xMax - xQ) ** 2) / sqrt(2.0)
total_moves += sqrt((d2_yMin - yQ) ** 2 + (d2_xMin - xQ) ** 2) / sqrt(2.0)
print(int(total_moves))


(N, K) = map(int, input().split())
(rQueen, cQueen) = map(int, input().split())
(sQrc, dQrc) = (rQueen + cQueen, rQueen - cQueen)
list_rcO = [(0, cQueen), (N + 1, cQueen), (rQueen, 0), (rQueen, N + 1)]
list_rcO += [(0, sQrc), (N + 1, sQrc - N - 1), (sQrc, 0), (sQrc - N - 1, N + 1)]
list_rcO += [(0, -dQrc), (N + 1, N + 1 - dQrc), (dQrc, 0), (dQrc + N + 1, N + 1)]
list_rcO += (tuple(map(int, input().split())) for _ in range(K))
T = R = B = L = D1 = D2 = D3 = D4 = N
for (rObstacle, cObstacle) in list_rcO:
	(sOrc, dOrc) = (rObstacle + cObstacle, rObstacle - cObstacle)
	if cObstacle == cQueen:
		if rObstacle > rQueen:
			T = min(T, rObstacle - rQueen)
		else:
			B = min(B, rQueen - rObstacle)
	if rObstacle == rQueen:
		if cObstacle > cQueen:
			R = min(R, cObstacle - cQueen)
		else:
			L = min(L, cQueen - cObstacle)
	if sOrc == sQrc:
		if dOrc > dQrc:
			D1 = min(D1, (dOrc - dQrc) // 2)
		else:
			D2 = min(D2, (dQrc - dOrc) // 2)
	if dOrc == dQrc:
		if sOrc > sQrc:
			D3 = min(D3, (sOrc - sQrc) // 2)
		else:
			D4 = min(D4, (sQrc - sOrc) // 2)
print(T + B + R + L + D1 + D2 + D3 + D4 - 8)


(n, k) = map(int, input().split())
(posx, posy) = map(int, input().split())
barrier = {}
for _ in range(k):
	(varx, vary) = map(int, input().split())
	barrier[varx, vary] = True
result = 0
for i in range(posx + 1, n + 1):
	if barrier.get((i, posy)):
		break
	else:
		result += 1
for i in range(posx - 1, 0, -1):
	if barrier.get((i, posy)):
		break
	else:
		result += 1
for i in range(posy - 1, 0, -1):
	if barrier.get((posx, i)):
		break
	else:
		result += 1
for i in range(posy + 1, n + 1):
	if barrier.get((posx, i)):
		break
	else:
		result += 1
p = posx + 1
q = posy - 1
while p <= n and q > 0:
	if barrier.get((p, q), 0):
		break
	else:
		result += 1
	p += 1
	q -= 1
p = posx + 1
q = posy + 1
while p <= n and q <= n:
	if barrier.get((p, q), 0):
		break
	else:
		result += 1
	p += 1
	q += 1
p = posx - 1
q = posy - 1
while p > 0 and q > 0:
	if barrier.get((p, q), 0):
		break
	else:
		result += 1
	p -= 1
	q -= 1
p = posx - 1
q = posy + 1
while p > 0 and q <= n:
	if barrier.get((p, q), 0):
		break
	else:
		result += 1
	p -= 1
	q += 1
print(result)


import sys
(num, k) = list(map(int, input().strip().split(' ')))
(qr, qc) = list(map(int, input().strip().split(' ')))
obstacles = set()
for a0 in range(k):
	(r, c) = list(map(int, input().strip().split(' ')))
	obstacles.add((r, c))
n = (num + 1, qc)
s = (0, qc)
e = (qr, num + 1)
w = (qr, 0)
d = min(num + 1 - qr, num + 1 - qc)
ne = (qr + d, qc + d)
d = min(qr, num + 1 - qc)
se = (qr - d, qc + d)
d = min(qr, qc)
sw = (qr - d, qc - d)
d = min(num + 1 - qr, qc)
nw = (qr + d, qc - d)
for (r, c) in obstacles:
	if c == qc:
		if r > qr and r < n[0]:
			n = (r, c)
			continue
		if r < qr and r > s[0]:
			s = (r, c)
			continue
	if r == qr:
		if c > qc and c < e[1]:
			e = (r, c)
			continue
		if c < qc and c > w[1]:
			w = (r, c)
			continue
	rdiff = r - qr
	cdiff = c - qc
	if abs(rdiff) == abs(cdiff):
		if rdiff > 0 and cdiff > 0:
			if r < ne[0]:
				ne = (r, c)
				continue
		if rdiff < 0 and cdiff > 0:
			if r > se[0]:
				se = (r, c)
				continue
		if rdiff < 0 and cdiff < 0:
			if r > sw[0]:
				sw = (r, c)
				continue
		if rdiff > 0 and cdiff < 0:
			if r < nw[0]:
				nw = (r, c)
				continue
can_attack = 0
can_attack += n[0] - s[0] - 2
can_attack += e[1] - w[1] - 2
can_attack += ne[0] - sw[0] - 2
can_attack += nw[0] - se[0] - 2
print(can_attack)


import sys

def my_directions(rQueen, cQueen, n):
	north = (n + 1, cQueen)
	east = (rQueen, n + 1)
	south = (0, cQueen)
	west = (rQueen, 0)
	if rQueen > cQueen:
		diff = n + 1 - rQueen
		north_east = (n + 1, cQueen + diff)
		south_west = (rQueen - cQueen, 0)
	else:
		diff = n + 1 - cQueen
		north_east = (rQueen + diff, n + 1)
		south_west = (0, cQueen - rQueen)
	if rQueen + cQueen > n:
		north_west = (n + 1, rQueen + cQueen - (n + 1))
		south_east = (rQueen + cQueen - (n + 1), n + 1)
	else:
		north_west = (rQueen + cQueen, 0)
		south_east = (0, rQueen + cQueen)
	return [north, east, south, west, north_east, north_west, south_west, south_east]
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
(rQueen, cQueen) = input().strip().split(' ')
(rQueen, cQueen) = [int(rQueen), int(cQueen)]
(north, east, south, west, north_east, north_west, south_west, south_east) = my_directions(rQueen, cQueen, n)
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	if rObstacle == rQueen:
		if cObstacle > cQueen:
			if east > (rObstacle, cObstacle):
				east = (rObstacle, cObstacle)
		elif west < (rObstacle, cObstacle):
			west = (rObstacle, cObstacle)
	elif cObstacle == cQueen:
		if rObstacle > rQueen:
			if north > (rObstacle, cObstacle):
				north = (rObstacle, cObstacle)
		elif south < (rObstacle, cObstacle):
			south = (rObstacle, cObstacle)
	elif cObstacle < cQueen and rObstacle < rQueen or (cObstacle > cQueen and rObstacle > rQueen):
		if abs(rQueen - rObstacle) == abs(cQueen - cObstacle):
			if cObstacle < cQueen:
				if south_west < (rObstacle, cObstacle):
					south_west = (rObstacle, cObstacle)
			elif north_east > (rObstacle, cObstacle):
				north_east = (rObstacle, cObstacle)
	elif cObstacle > cQueen and rObstacle < rQueen or (cObstacle < cQueen and rObstacle > rQueen):
		if rQueen + cQueen == rObstacle + cObstacle:
			if cObstacle < cQueen:
				if north_west > (rObstacle, cObstacle):
					north_west = (rObstacle, cObstacle)
			elif south_east < (rObstacle, cObstacle):
				south_east = (rObstacle, cObstacle)
res = east[1] - cQueen + (cQueen - west[1]) + (north[0] - rQueen) + (rQueen - south[0]) + (2 * cQueen - north_west[1] - south_west[1]) + (south_east[1] + north_east[1] - 2 * cQueen) - 8
print(res)


import sys
(n, k) = input().strip().split(' ')
(n, k) = [int(n), int(k)]
z = []
(rQ, cQ) = input().strip().split(' ')
(rQ, cQ) = [int(rQ), int(cQ)]
for a0 in range(k):
	(rObstacle, cObstacle) = input().strip().split(' ')
	(rObstacle, cObstacle) = [int(rObstacle), int(cObstacle)]
	z.append((rObstacle, cObstacle))
maw = 0
miw = 100000000
ww1 = cQ - 1
ww2 = n - cQ
for i in z:
	if i[0] == rQ:
		if i[1] < cQ:
			if i[1] > maw:
				maw = i[1]
			ww1 = cQ - maw - 1
		else:
			if i[1] < miw:
				miw = i[1]
			ww2 = miw - cQ - 1
ww = ww1 + ww2
mak = 0
mik = 100000000
wk1 = rQ - 1
wk2 = n - rQ
for i in z:
	if i[1] == cQ:
		if i[0] < rQ:
			if i[0] > mak:
				mak = i[0]
			wk1 = rQ - mak - 1
		else:
			if i[0] < mik:
				mik = i[0]
			wk2 = mik - rQ - 1
kk = wk1 + wk2
map1 = 0
mip1 = 100000000
wp1 = min(rQ, cQ) - 1
wp2 = n - max(rQ, cQ)
for i in z:
	if i[0] - rQ == i[1] - cQ:
		if i[0] < rQ:
			if i[0] > map1:
				map1 = i[0]
			wp1 = rQ - map1 - 1
		else:
			if i[0] < mip1:
				mip1 = i[0]
			wp2 = mip1 - rQ - 1
wp = wp1 + wp2
map1 = 0
mip1 = 100000000
wpp1 = min(rQ - 1, n - cQ)
wpp2 = min(n - rQ, cQ - 1)
for i in z:
	if i[0] - rQ == cQ - i[1]:
		if i[0] < rQ:
			if i[0] > map1:
				map1 = i[0]
			wpp1 = rQ - map1 - 1
		else:
			if i[0] < mip1:
				mip1 = i[0]
			wpp2 = mip1 - rQ - 1
wpp = wpp1 + wpp2
print(ww + kk + wp + wpp)