You are given a chessboard of size $n \times n$. It is filled with numbers from $1$ to $n^2$ in the following way: the first $\lceil \frac{n^2}{2} \rceil$ numbers from $1$ to $\lceil \frac{n^2}{2} \rceil$ are written in the cells with even sum of coordinates from left to right from top to bottom. The rest $n^2 - \lceil \frac{n^2}{2} \rceil$ numbers from $\lceil \frac{n^2}{2} \rceil + 1$ to $n^2$ are written in the cells with odd sum of coordinates from left to right from top to bottom. The operation $\lceil\frac{x}{y}\rceil$ means division $x$ by $y$ rounded up.

For example, the left board on the following picture is the chessboard which is given for $n=4$ and the right board is the chessboard which is given for $n=5$. [Image] 

You are given $q$ queries. The $i$-th query is described as a pair $x_i, y_i$. The answer to the $i$-th query is the number written in the cell $x_i, y_i$ ($x_i$ is the row, $y_i$ is the column). Rows and columns are numbered from $1$ to $n$.


-----Input-----

The first line contains two integers $n$ and $q$ ($1 \le n \le 10^9$, $1 \le q \le 10^5$) — the size of the board and the number of queries.

The next $q$ lines contain two integers each. The $i$-th line contains two integers $x_i, y_i$ ($1 \le x_i, y_i \le n$) — description of the $i$-th query.


-----Output-----

For each query from $1$ to $q$ print the answer to this query. The answer to the $i$-th query is the number written in the cell $x_i, y_i$ ($x_i$ is the row, $y_i$ is the column). Rows and columns are numbered from $1$ to $n$. Queries are numbered from $1$ to $q$ in order of the input.


-----Examples-----
Input
4 5
1 1
4 4
4 3
3 2
2 4

Output
1
8
16
13
4

Input
5 4
2 1
4 2
3 3
3 4

Output
16
9
7
20



-----Note-----

Answers to the queries from examples are on the board in the picture from the problem statement.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Implementation


Solutions:
import math
import sys
(n, k) = map(int, input().split())
for p in range(k):
	(i, j) = map(int, sys.stdin.readline().split())
	i -= 1
	j -= 1
	if n % 2 == 1:
		if (i + j) % 2 == 0:
			ans = n // 2 * i + (i + 1) // 2 + int(j / 2) + 1
		else:
			ans = n * n // 2 + 1 + n // 2 * i + i // 2 + j // 2 + 1
		print(ans)
	else:
		if (i + j) % 2 == 0:
			ans = n // 2 * i + j // 2 + 1
		else:
			ans = n ** 2 // 2 + int(i * (n / 2)) + int(j / 2) + 1
		print(ans)


(n, q) = map(int, input().split())
a = []
val = (n * n + 1) // 2
for i in range(q):
	(x, y) = map(int, input().split())
	if (x + y) % 2 == 0:
		if x % 2 == 1:
			a.append(str((x - 1) // 2 * n + (y + 1) // 2))
		else:
			a.append(str((x - 2) // 2 * n + (n + 1) // 2 + y // 2))
	else:
		k = 0
		if x % 2 == 1:
			a.append(str((x - 1) // 2 * n + y // 2 + val))
		else:
			a.append(str((x - 2) // 2 * n + n // 2 + (y + 1) // 2 + val))
print('\n'.join(a))


def R():
	return map(int, input().split())
ans = []
(n, q) = R()
d = (n * n + 1) // 2
for _ in range(q):
	(x, y) = R()
	i = ((x - 1) * n + y - 1) // 2 + 1
	if x % 2 != y % 2:
		i += d
	ans.append(str(i))
print('\n'.join(ans))


(n, q) = map(int, input().split())
l = (n ** 2 + 1) // 2
A = []
a = []
for _ in range(q):
	(x, y) = map(int, input().split())
	A.append(x)
	a.append(y)
for i in range(q):
	posValue = (n * (A[i] - 1) + a[i] + 1) // 2
	if (A[i] + a[i]) % 2 == 1:
		posValue += l
	print(posValue)


from math import ceil
(n, m) = map(int, input().split())
if n % 2 == 0:
	a = n // 2
	b = a
else:
	b = n // 2
	a = b + 1
l = 0
l = n ** 2
if l % 2 == 0:
	l = l // 2
	l += 0
else:
	l = l // 2
	l += 1
ans = ''
for i in range(m):
	(q1, q2) = map(int, input().split())
	if (q1 + q2) % 2 == 0:
		x = (q1 - 1) // 2
		y = ceil((q1 - 1) / 2)
		na = y * a + x * b
		if q1 % 2 != 0:
			w = ceil(q2 / 2)
		else:
			w = q2 // 2
		ans += str(na + w) + chr(10)
	else:
		x = (q1 - 1) // 2
		y = ceil((q1 - 1) / 2)
		na = y * b + x * a
		if q1 % 2 == 0:
			w = ceil(q2 / 2)
		else:
			w = q2 // 2
		ans += str(na + w + l) + chr(10)
print(ans)


import sys
(n, q) = map(int, input().split())
for i in range(q):
	(x, y) = map(int, sys.stdin.readline().split())
	print((x + y) % 2 * ((n ** 2 + 1) // 2) + (y + (x - 1) * n + 1) // 2)


from math import ceil, floor
(n, q) = map(int, input().split())
from sys import stdin, stdout
f = floor(n / 2)
ce = ceil(n / 2)
if n % 2 == 0:
	k = n // 2 * n
else:
	k = (n - 1) // 2 * n + ce
for i in range(q):
	(r, c) = (int(o) for o in stdin.readline().split())
	if r % 2 == 1:
		m = (r - 1) // 2 * n
		if c % 2 == 1:
			print(m + ceil(c / 2))
		else:
			print(k + m + floor(c / 2))
	else:
		m = (r - 2) // 2 * n
		if c % 2 == 0:
			print(m + ce + floor(c / 2))
		else:
			print(k + m + f + ceil(c / 2))


(n, q) = [int(i) for i in input().split()]
z = []
while q > 0:
	(x, y) = [int(i) for i in input().split()]
	if n % 2 == 0:
		if (x + y) % 2 == 0:
			valor = (n * (x - 1) + (y + 1)) // 2
		else:
			valor = (n * (x - 1) + (y + 1) + n * n) // 2
	else:
		valor = n * ((x - 1) // 2)
		if (x + y) % 2 == 0:
			valor += (y + 1) // 2 if x % 2 == 1 else (y + 1) // 2 + (n + 1) // 2
		else:
			valor += (y + 1) // 2 if x % 2 == 1 else (y + 1) // 2 + n // 2
			valor += n * n // 2 + 1
	z.append(str(valor))
	q -= 1
print('\n'.join(z))


(n, q) = map(int, input().split())
ans = []
while q:
	(a, b) = map(int, input().split())
	x = (a - 1) * n + b + 1
	if (a + b) % 2 != 0:
		x = x + n * n
	ans.append(str(x // 2))
	q = q - 1
print('\n'.join(ans))


def numb(x, y):
	ret = (n ** 2 + 1) // 2 * ((x + y) % 2)
	if n % 2:
		ret += (x - 1) // 2 * n + ((n + 1) // 2 - (x + y) % 2) * (1 - x % 2) + (y + 1) // 2
	else:
		ret += (x - 1) * (n // 2) + (y + 1) // 2
	return ret
from sys import stdin
all_in = [tuple(map(int, el.split())) for el in stdin.readlines()]
(n, q, *co) = (*all_in[0], *all_in[1:])
ans = [numb(*el) for el in co]
print('\n'.join(map(str, ans)))


def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP2():
	return map(float, input().split())

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

def STRING():
	return input()
import string
import sys
from heapq import heappop, heappush
from bisect import *
from collections import deque, Counter, defaultdict
from math import *
from itertools import permutations, accumulate
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
(n, q) = MAP()
ans = []
for i in range(q):
	(x, y) = MAP()
	k = ((x - 1) * n + y + 1) // 2
	z = (n * n + 1) // 2
	if (x + y) % 2 != 0:
		k += z
	ans.append(k)
for i in ans:
	print(i)


from math import *
import sys
f = sys.stdin
(n, q) = map(int, f.readline().rstrip('\r\n').split())
k = n * n // 2
if n % 2 != 0:
	k += 1
for _ in range(q):
	(x, y) = map(int, f.readline().rstrip('\r\n').split())
	if n % 2 == 0:
		if (x + y) % 2 == 0:
			ans = (x - 1) * (n // 2)
			if x % 2 == 0:
				ans += y // 2
			else:
				ans += (y + 1) // 2
			print(ans)
		else:
			ans = k
			ans += (x - 1) * (n // 2)
			if x % 2 != 0:
				ans += y // 2
			else:
				ans += (y + 1) // 2
			print(ans)
	elif (x + y) % 2 == 0:
		ans = x // 2 * ((n + 1) // 2)
		ans += (x - 1) // 2 * ((n - 1) // 2)
		if x % 2 != 0:
			ans += (y + 1) // 2
		else:
			ans += y // 2
		print(ans)
	else:
		ans = k
		ans += x // 2 * ((n - 1) // 2)
		ans += (x - 1) // 2 * ((n + 1) // 2)
		if x % 2 == 0:
			ans += (y + 1) // 2
		else:
			ans += y // 2
		print(ans)


(n, q) = map(int, input().split())
results = []
for _ in range(q):
	(x, y) = map(int, input().split())
	if (y - x % 2) % 2:
		res = x // 2 * (n // 2) + (x - 1) // 2 * ((n + 1) // 2) + (y + (x + 1) % 2) // 2 + (n * n + 1) // 2
	else:
		res = x // 2 * ((n + 1) // 2) + (x - 1) // 2 * (n // 2) + (y + x % 2) // 2
	results.append(str(res))
print('\n'.join(results))


(n, q) = map(int, input().split())
ans = []
for i in range(0, q):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	ans.append(str((x * n + y) // 2 + 1 if (x + y) % 2 == 0 else n * n // 2 + n % 2 + (x * n + y) // 2 + 1))
print('\n'.join(ans))


import math
import sys
input = sys.stdin.readline

def solve(n, x, y):
	r = (n * (x - 1) + (y - 1)) // 2 + 1 + int((x + y) % 2 == 1) * (n ** 2 // 2 + int(n % 2 == 1))
	return r
(n, q) = [int(s) for s in input().split(' ')]
for query in range(q):
	(x, y) = [int(s) for s in input().split(' ')]
	print(solve(n, x, y))


(n, q) = map(int, input().split())
n2 = (n ** 2 + 1) // 2
s = ''
for i in range(q):
	(x, y) = map(int, input().split())
	if (x + y) % 2 == 0:
		s += str((n * (x - 1) + y + 1) // 2) + '\n'
	else:
		s += str(n2 + (n * (x - 1) + y + 1) // 2) + '\n'
print(s)


import sys
input = sys.stdin.read()
data = list(map(int, input.split()))
size = data[0]
n = data[1]
plus = (size * size + size % 2) // 2
for i in range(n):
	(x, y) = (data[i * 2 + 2], data[i * 2 + 3])
	print(((x - 1) * size + y + 1) // 2 + (x + y) % 2 * plus)


import math
(n, q) = map(int, input().split())
a = [0] * q
for i in range(q):
	(x, y) = map(int, input().split())
	if n % 2 == 0:
		num = n // 2 * (x - 1) + math.ceil(y / 2)
		if (x + y) % 2 == 1:
			num += n ** 2 // 2
	elif x % 2 == 1:
		num = n * (x // 2) + math.ceil(y / 2)
		if y % 2 == 0:
			num += n ** 2 // 2 + 1
	else:
		num = n * x // 2 - n // 2 + y // 2
		if y % 2 == 1:
			num += n ** 2 // 2 + 1
	a[i] = num
for item in a:
	print(item)


import sys
(n, q) = map(int, sys.stdin.readline().strip().split())
nc = n
if n % 2 == 0:
	n2 = int(n * n / 2)
else:
	n2 = int(n * n / 2) + 1
n1 = int(n / 2)
if 1 == 1:
	for i in range(q):
		(x, y) = map(int, sys.stdin.readline().strip().split())
		x1 = int(x / 2)
		y1 = int(y / 2)
		op = 0
		if x % 2 != 0:
			if y % 2 != 0:
				if x > 1:
					op = n * x1
				op = op + 1 + y1
			else:
				op = n2 + n * x1 + y1
		elif y % 2 == 0:
			if n % 2 == 0:
				op = n1
			else:
				op = n1 + 1
			op = op + n * (x1 - 1)
			op = op + y1
		else:
			op = n2 + n1 + n * (x1 - 1) + y1 + 1
		print(op)


import sys
(N, q) = map(int, sys.stdin.readline().split())
u = (N * N + 1) // 2
for i in range(q):
	(x, y) = map(int, sys.stdin.readline().split())
	p = N * (x - 1) + y + 1
	print(p // 2 + (x + y) % 2 * u)


import math

def formula(n, a, b):
	if (a + b) % 2 == 0:
		return ((a - 1) * n + b + 1) // 2
	else:
		return ((a - 1) * n + b + 1 + n * n) // 2
(n, q) = map(int, input().split())
ans = []
for i in range(q):
	(x, y) = map(int, input().split())
	ans.append(formula(n, x, y))
print(*ans)


(n, q) = list(map(int, input().split()))
nn = (n ** 2 + 1) // 2
a = []
kv_n = n * n
pol_n = n // 2
for i in range(q):
	(y, x) = list(map(int, input().split()))
	if y > pol_n:
		spes = kv_n - (n - y + 1) * n
	else:
		spes = (y - 1) * n
	if (x + y) % 2 == 0:
		a.append(str((spes + x + 1) // 2))
	else:
		a.append(str(nn + (spes + x + 1) // 2))
print('\n'.join(a))


(n, q) = map(int, input().split())
Q = [None] * q
for i in range(q):
	Q[i] = list(map(int, input().split()))
for i in range(q):
	x = Q[i][0]
	y = Q[i][1]
	if n % 2 == 0:
		if (x + y) % 2 == 0:
			ANS = (x - 1) * (n // 2) + (y + 1) // 2
		else:
			ANS = n ** 2 // 2 + (x - 1) * (n // 2) + (y + 1) // 2
	elif n % 2 == 1:
		if (x + y) % 2 == 0:
			if x % 2 == 1:
				ANS = (x - 1) // 2 * n + (y + 1) // 2
			else:
				ANS = (x - 1) // 2 * n + (n // 2 + 1) + (y + 1) // 2
		elif x % 2 == 1:
			ANS = n ** 2 // 2 + 1 + (x - 1) // 2 * n + (y + 1) // 2
		else:
			ANS = n ** 2 // 2 + 1 + (x - 1) // 2 * n + n // 2 + (y + 1) // 2
	print(ANS)


import bisect
import os
import gc
import sys
from io import BytesIO, IOBase
from collections import Counter
from collections import deque
import heapq
import math
import statistics

def sin():
	return input()

def ain():
	return list(map(int, sin().split()))

def sain():
	return input().split()

def iin():
	return int(sin())
MAX = float('inf')
MIN = float('-inf')
MOD = 1000000007

def readTree(n, m):
	adj = [deque([]) for _ in range(n + 1)]
	for _ in range(m):
		(u, v) = ain()
		adj[u].append(v)
		adj[v].append(u)
	return adj

def main():
	(n, q) = ain()
	for __ in range(q):
		(x, y) = ain()
		if x + y & 1 == 0:
			c = 0
			if n & 1 == 0:
				p = x - 1
				c += p * (n // 2)
				c += math.ceil(y / 2)
				print(c)
			else:
				p = x - 1
				j = math.ceil(p / 2)
				k = p - j
				c += j * math.ceil(n / 2) + k * int(n / 2)
				c += math.ceil(y / 2)
				print(c)
		else:
			c = (n * n + 1) // 2
			if n & 1 == 0:
				p = x - 1
				c += p * (n // 2)
				c += math.ceil(y / 2)
				print(c)
			else:
				p = x - 1
				j = math.ceil(p / 2)
				k = p - j
				c += j * int(n / 2) + k * math.ceil(n / 2)
				c += math.ceil(y / 2)
				print(c)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
l = sys.stdin.readlines()
(n, q) = map(int, l[0].split())
k = (n * n + 1) // 2
for i in range(q):
	(x, y) = map(int, l[i + 1].split())
	if n % 2 == 0:
		if (x + y) % 2 == 0:
			ans = (x - 1) * (n // 2) + (y - 1) // 2 + 1
		else:
			ans = (x - 1) * (n // 2) + (y - 1) // 2 + 1 + k
	elif (x + y) % 2 == 0:
		ans = ((x - 1 - 1) // 2 + 1) * ((n - 1) // 2 + 1) + (x - 1) // 2 * (n // 2) + (y - 1) // 2 + 1
	elif x % 2 == 0:
		ans = ((x - 1 - 1) // 2 + 1) * ((n - 1) // 2 + 1) + (x - 1) // 2 * (n // 2) + (y - 1) // 2 + k
	else:
		ans = ((x - 1 - 1) // 2 + 1) * ((n - 1) // 2 + 1) + (x - 1) // 2 * (n // 2) + (y - 1) // 2 + k + 1
	sys.stdout.write(str(ans) + '\n')


(n, q) = map(int, input().split())
r = []
for i in range(q):
	(x, y) = map(int, input().split())
	t = (x - 1) * n + y + 1
	if (x + y) % 2 != 0:
		t = t + n * n
	r.append(t // 2)
print(*r)


import sys
input = sys.stdin.readline

def invr():
	return map(int, input().split())
(n, q) = invr()
for i in range(q):
	(x, y) = invr()
	long_value = (x - 1) * n + y
	value = long_value // 2
	if long_value % 2 != 0:
		value = value + 1
	base = n * n // 2
	if n % 2 != 0:
		base = base + 1
	if x % 2 == y % 2:
		print(value)
	else:
		print(value + base)


import sys
(n, q) = map(int, sys.stdin.readline().split())
h = -(-n * n // 2)
for i in range(q):
	(x, y) = map(int, sys.stdin.readline().split())
	ans = (x - 1) // 2 * n
	if (x + y) % 2 == 0:
		if x % 2 == 0:
			ans += -(-n // 2)
			ans += y // 2
		else:
			ans += (y + 1) // 2
	else:
		ans += h
		if x % 2 == 0:
			ans += n // 2
			ans += (y + 1) // 2
		else:
			ans += y // 2
	print(ans)


import sys
(n, k) = list(map(int, sys.stdin.readline().split()))
half = n // 2
add = 0
res = 0
y = 0
x = 0
for i in range(k):
	(y, x) = list(map(int, sys.stdin.readline().split()))
	if n % 2 == 0:
		add = 0
		if (y + x) % 2 != 0:
			add = n * n // 2
		res = add + half * (y - 1) + (x + 1) // 2
	elif y % 2 == x % 2:
		res = (n * (y - 1) + 1) // 2 + (x + 1) // 2
	else:
		res = (n * n + 1) // 2 + (n * (y - 1) + 1) // 2 + (x + 1) // 2
		if y % 2 == 0:
			res -= 1
	print(res)


def cin(obj=list, type=int, sep=' '):
	return obj(map(type, input().split(sep)))
(n, q) = cin()
ans = [0] * q
from sys import stdin
i = 0
for s in stdin:
	(x, y) = list(map(int, s.split()))
	ans[i] = (x + y) % 2 * ((n ** 2 + 1) // 2) + (x - 1) // 2 * (n // 2 * 2 + n % 2) + (x - 1) % 2 * (n // 2 + n % 2 * ((x + y) % 2 == 0)) + (y + 1) // 2
	i += 1
print(*ans, sep='\n')


import sys
from array import array

def readline():
	return sys.stdin.buffer.readline().decode('utf-8')
(n, q) = map(int, readline().split())
ans = [0] * q
for i in range(q):
	(y, x) = map(int, readline().split())
	z = (y - 1 >> 1) * n + (x + 1 >> 1)
	if x + y & 1:
		z += n ** 2 + 1 >> 1
		if y & 1 == 0:
			z += n >> 1
	elif y & 1 == 0:
		z += n + 1 >> 1
	ans[i] = z
sys.stdout.buffer.write('\n'.join(map(str, ans)).encode('utf-8'))


from sys import stdin, stdout
(n, q) = map(int, stdin.readline().split())
ans = []
for line in stdin:
	(x, y) = map(int, line.split())
	if x % 2 == y % 2:
		ans.append(str(((x - 1) * n + (y - 1)) // 2 + 1))
	else:
		ans.append(str(((x - 1) * n + (y - 1)) // 2 + 1 + (n * n + 1) // 2))
stdout.write('\n'.join(ans) + '\n')


(n, q) = map(int, input().split())
k = 0
z = []
for i in range(q):
	(x, y) = map(int, input().split())
	if n % 2:
		if (x + y) % 2:
			k = (n ** 2 + 1) // 2
			k += (x - 1) * n // 2
			k += (y + 1) // 2
			z.append(k)
		else:
			k = n // 2 * (x - 1)
			k += x // 2
			k += (y + 1) // 2
			z.append(k)
	elif (x + y) % 2:
		k = n ** 2 // 2
		k += (x - 1) * n // 2
		k += (y + 1) // 2
		z.append(k)
	else:
		k = n // 2 * (x - 1)
		k += (y + 1) // 2
		z.append(k)
for i in z:
	print(i)


from sys import stdin
from math import *
line = stdin.readline().rstrip().split()
n = int(line[0])
q = int(line[1])
ceiling = int(n * n)
if ceiling % 2 == 0:
	ceiling //= 2
else:
	ceiling = (ceiling + 1) // 2
for i in range(q):
	numbers = list(map(int, stdin.readline().rstrip().split()))
	x = numbers[0] - 1
	y = numbers[1] - 1
	result = 0
	if (x + y) % 2 == 1:
		result += ceiling
	if n % 2 == 0:
		result += x * (n // 2)
		result += y // 2
	else:
		aux = x * n + y
		result += aux // 2
	print(result + 1)


import math
from sys import stdin
string = stdin.readline().strip().split()
n = int(string[0])
q = int(string[1])
if n % 2 == 0:
	oA = math.floor(n / 2)
	eA = math.floor(n / 2)
	oB = oA
	eB = eA
	half = math.floor(n * n / 2)
else:
	oA = math.floor(n / 2) + 1
	eA = n - oA
	oB = eA
	eB = oA
	half = math.floor((n * n + 1) // 2)
for _ in range(q):
	string1 = stdin.readline().strip().split()
	x = int(string1[0])
	y = int(string1[1])
	number = None
	if (x + y) % 2 == 0:
		if x % 2 == 1:
			number = (oA + eA) * math.floor(x / 2) + math.floor((y + 1) / 2)
		else:
			number = oA * math.floor(x / 2) + eA * (math.floor(x / 2) - 1) + math.floor(y / 2)
	else:
		if x % 2 == 1:
			number = (oB + eB) * math.floor(x / 2) + math.floor(y / 2)
		else:
			number = oB * math.floor(x / 2) + eB * (math.floor(x / 2) - 1) + math.floor((y + 1) / 2)
		number += half
	print(number)


import sys
(n, q) = map(int, sys.stdin.readline().split())
for line in sys.stdin:
	(x, y) = map(int, line.split())
	ans = 1 + ((x - 1) * n + y - 1) // 2
	if (x + y) % 2:
		ans += n * n // 2 + n % 2
	print(int(ans))


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
evenOneLine = (n + 1) // 2
evenTwoLine = n // 2
oddOneLine = evenTwoLine
oddTwoLine = evenOneLine
for i in range(q):
	num = 0
	(x, y) = map(int, input().split())
	if (x + y) % 2 == 0:
		if x % 2 == 1:
			num += x // 2 * (evenOneLine + evenTwoLine)
			num += y // 2 + 1
			print(num)
		else:
			num += (x - 1) // 2 * (evenOneLine + evenTwoLine) + evenOneLine
			num += (y - 1) // 2 + 1
			print(num)
	else:
		num = n ** 2 // 2
		if n % 2 == 1:
			num += 1
		if x % 2 == 1:
			num += x // 2 * (oddOneLine + oddTwoLine)
			num += (y - 1) // 2 + 1
			print(num)
		else:
			num += (x - 1) // 2 * (oddOneLine + oddTwoLine) + oddOneLine
			num += y // 2 + 1
			print(num)


import sys
res = sys.stdin.readline().split()
(n, query) = (int(res[0]), int(res[1]))
for i in range(0, query):
	result = sys.stdin.readline().split()
	(rows, columns) = (int(result[0]), int(result[1]))
	posicion = (rows - 1) * n + columns
	ans = (posicion + 1) // 2
	if (rows + columns) % 2 == 1:
		ans += (n * n + 1) // 2
	sys.stdout.write(str(ans) + '\n')


(n, q) = map(int, input().split())
a = []
for i in range(q):
	(x, y) = map(int, input().split())
	t = (x - 1) * n + y
	ans = (t + 1) // 2
	if (x + y) % 2 == 1:
		ans = ans + (n * n + 1) // 2
	a.append(ans)
for i in range(q):
	print(a[i])


from sys import stdin, stdout
(a, b) = map(int, stdin.readline().split())
f = (a * a + 1) // 2
for i in stdin:
	(x, y) = map(int, i.split())
	z = ((x - 1) * a + y + 1) // 2
	stdout.write(str(z + (x + y) % 2 * f) + '\n')


import sys
(n, *a) = sys.stdin.readlines()
n = int(n.split()[0])
for l in a:
	(x, y) = map(int, l.split())
	print((x + y) % 2 * (n * n + 1) // 2 + (y + x * n - n + 1) // 2)


import sys
lst = sys.stdin.readlines()
(n, q) = map(int, lst[0].split())
for i in range(q):
	(x, y) = map(int, lst[i + 1].split())
	cnt = (x - 1) * n + y
	ans = (cnt + 1) // 2
	if (x + y) % 2 == 1:
		ans += (n * n + 1) // 2
	sys.stdout.write(str(ans) + '\n')


(n, q) = map(int, input().split())
if n & 1:
	val = n ** 2 // 2 + 1
else:
	val = n ** 2 // 2
for i in range(q):
	(x, y) = map(int, input().split())
	a = ((x - 1) * n + y + 1) // 2
	print(a + val) if x + y & 1 else print(a)


import sys

def query(n, x, y):
	num = (x - 1) * n // 2 + (y + 1) // 2
	factor = (x + 1) % 2 if n % 2 == 1 else 0
	return num + factor if (x + y) % 2 == 0 else (n * n + 1) // 2 + num
(n, q) = map(int, sys.stdin.readline().split())
for line in sys.stdin:
	print(query(n, *map(int, line.split())))


from math import ceil
(n, q) = map(int, input().split())
a = []

def getNumber(x, y):
	nonlocal n
	if n % 2 == 0:
		if (x + y) % 2 == 0:
			start = 0
		else:
			start = n ** 2 // 2
		pos = (x - 1) * n // 2 + (y + 1) // 2
	else:
		t = (x - 1) * n + y + 1
		if t % 2 == 0:
			start = 0
		else:
			start = (n ** 2 + 1) // 2
		pos = t // 2
	return start + pos
for i in range(q):
	(xi, yi) = map(int, input().split())
	a.append(str(getNumber(xi, yi)))
print('\n'.join(a))


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def ceil(n):
	if n % 2 == 0:
		return int(n // 2)
	else:
		return int(n // 2) + 1
(n, q) = [int(i) for i in input().split()]
for i in range(q):
	(xi, yi) = [int(i) for i in input().split()]
	if xi % 2 == 1:
		over = (xi - 1) // 2 * ceil(n) + (xi - 1) // 2 * (n // 2)
		if yi % 2 == 1:
			print(over + ceil(yi))
		else:
			print(ceil(n ** 2) + over + ceil(yi))
	else:
		over = ((xi - 1) // 2 + 1) * ceil(n) + (xi - 1) // 2 * (n // 2)
		if yi % 2:
			temp = 0
			if n % 2 == 0:
				temp = 1
			print(ceil(n ** 2) + over + ceil(yi) - 1 + temp)
		else:
			print(over + ceil(yi))


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
ee = (n + 1) // 2
eo = n // 2
oe = n // 2
oo = (n + 1) // 2
for i in range(q):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	if (x + y) % 2 == 0:
		if x % 2 == 0:
			t = x // 2 * (ee + eo)
			t += y // 2 + 1
		else:
			t = (x + 1) // 2 * ee + x // 2 * eo
			t += (y + 1) // 2
	elif x % 2 == 0:
		t = (n ** 2 + 1) // 2
		t += x // 2 * (oe + oo)
		t += (y + 1) // 2
	else:
		t = (n ** 2 + 1) // 2
		t += x // 2 * oo + (x + 1) // 2 * oe
		t += y // 2 + 1
	print(t)


from sys import stdin, stdout
(n, queries) = map(int, stdin.readline().split())
max_in_first_row = n // 2 + 1 if n % 2 else n // 2
max_in_second_row = n // 2
start = n ** 2 // 2 + 1 if n % 2 == 0 else n ** 2 // 2 + 2
for _ in range(queries):
	(i, j) = map(int, stdin.readline().split())
	if (i + j) % 2 == 0:
		if i % 2 == 0:
			result = i // 2 * (max_in_first_row + max_in_second_row) - max_in_second_row
			result += j // 2
		else:
			i -= 1
			if i < 1:
				result = j // 2 + 1
			else:
				result = i // 2 * (max_in_first_row + max_in_second_row)
				result += j // 2 + 1
	elif i % 2 == 0:
		result = i // 2 * (max_in_second_row + max_in_first_row) + start - max_in_first_row
		result += j // 2
	else:
		i -= 1
		if i < 1:
			result = j // 2 + start - 1
		else:
			result = i // 2 * (max_in_second_row + max_in_first_row) + start
			result += j // 2 - 1
	print(result)


import sys
import math
for _ in range(1):
	(n, k) = map(int, sys.stdin.readline().split())
	for k in range(k):
		(x, y) = map(int, sys.stdin.readline().split())
		if (x + y) % 2 == 0:
			print(((x - 1) * n + y + 1) // 2)
		else:
			print((n ** 2 + 1) // 2 + ((x - 1) * n + y + 1) // 2)


import math
import sys
(n, q) = map(int, sys.stdin.readline().split())
while q:
	s = 0
	(x, y) = map(int, sys.stdin.readline().split())
	if n % 2:
		if x % 2 and y % 2 or (not x % 2 and (not y % 2)):
			if x % 2:
				s = 1 + (x - 1) * (n // 2) + y // 2 + x // 2
			else:
				s = 1 + (x - 1) * (n // 2) + (y - 1) // 2 + x // 2
		elif x % 2:
			s = (n * n + 1) // 2 + (x - 1) * (n // 2) + (y - 1) // 2 + 1 + (x - 1) // 2
		else:
			s = (n * n + 1) // 2 + (x - 1) * (n // 2) + y // 2 + 1 + (x - 1) // 2
	elif x % 2 and y % 2 or (not x % 2 and (not y % 2)):
		if x % 2:
			s = 1 + (x - 1) * (n // 2) + y // 2
		else:
			s = 1 + (x - 1) * (n // 2) + (y - 1) // 2
	elif x % 2:
		s = (n * n + 1) // 2 + 1 + (x - 1) * (n // 2) + (y - 1) // 2
	else:
		s = (n * n + 1) // 2 + 1 + (x - 1) * (n // 2) + y // 2
	print(s)
	q -= 1


def solve_query(n, i, j):
	(i, j) = (i - 1, j - 1)
	half = n ** 2 // 2 + (n & 1)
	prev_total_nums = n * i + j
	if n % 2 == 0:
		prev_small_nums = n // 2 * i + (j // 2 if i % 2 else (j + 1) // 2)
	else:
		prev_small_nums = (n // 2 + 1) * ((i + 1) // 2) + n // 2 * (i // 2) + (j // 2 if i % 2 else (j + 1) // 2)
	if (i + j) % 2 == 0:
		return prev_small_nums + 1
	prev_big_nums = prev_total_nums - prev_small_nums
	return half + prev_big_nums + 1

def solve(n, queries):
	return [solve_query(n, x, y) for (x, y) in queries]
(n, q) = map(int, input().split())
queries = [list(map(int, input().split())) for _ in range(q)]
for answer in solve(n, queries):
	print(answer)


import sys
f = sys.stdin

def answer1(x, y):
	a = 1
	val = round(n ** 2 / 2)
	if x + y & 1 == 1:
		a += val
	x1 = a + (x - 1) * (n // 2)
	y1 = x1 + ((y + 1) // 2 - 1)
	sys.stdout.write(str(y1) + '\n')

def answer2(x, y):
	a = 1
	val = n ** 2 // 2
	if n & 1 == 1:
		val += 1
	if x + y & 1 == 1:
		a += val
	x1 = a + ((x + 1) // 2 - 1) * n
	if x & 1 == 0:
		y += n
	y1 = x1 + ((y + 1) // 2 - 1)
	sys.stdout.write(str(y1) + '\n')

def find(x, y):
	if n & 1 == 0:
		answer1(x, y)
	else:
		answer2(x, y)
(n, q) = map(int, f.readline().rstrip('\r\n').split())
for _ in range(q):
	(x, y) = map(int, f.readline().rstrip('\r\n').split())
	find(x, y)


from sys import *
input = stdin.readline
(n, q) = map(int, input().split())
nn = n * n
if nn % 2 == 1:
	for i in range(q):
		(x, y) = map(int, input().split())
		s = x + y
		if s % 2 == 0:
			p = (x - 1) * n + y
			print(p // 2 + 1)
		else:
			p = (x - 1) * n + y
			print(nn // 2 + p // 2 + 1)
else:
	for i in range(q):
		(x, y) = map(int, input().split())
		s = x + y
		if s % 2 == 0:
			p = (x - 1) * n + y
			print((p + 1) // 2)
		else:
			p = (x - 1) * n + y
			print(nn // 2 + (p + 1) // 2)


from sys import stdin
(n, q) = map(int, input().split())
n2 = (n ** 2 + 1) // 2
l = stdin.read().splitlines()
for (i, s) in enumerate(l):
	(x, y) = map(int, s.split())
	if (x ^ y) & 1:
		l[i] = n2 + (n * (x - 1) + y + 1) // 2
	else:
		l[i] = (n * (x - 1) + y + 1) // 2
print('\n'.join(map(str, l)))


def editor():
	import sys
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, q) = map(int, input().split())
	till = (n ** 2 + 1) // 2
	if n % 2 == 0:
		half = n // 2
		for _ in range(q):
			(x, y) = map(int, input().split())
			if (x + y) % 2 == 0:
				print((x - 1) * half + (y + 1) // 2)
			else:
				print(till + (x - 1) * half + (y + 1) // 2)
	else:
		oh = n // 2
		eh = (n + 1) // 2
		for _ in range(q):
			(x, y) = map(int, input().split())
			if (x + y) % 2 == 0:
				if x % 2 == 1:
					print(x // 2 * n + (y + 1) // 2)
				else:
					print(x // 2 * n - (n - y) // 2)
			elif x % 2 == 1:
				print(till + x // 2 * n + (y + 1) // 2)
			else:
				print(till + x // 2 * n - (n - y) // 2)
tc = 1
for t in range(tc):
	solve()


import math
l = input().split()
n = int(l[0])
q = int(l[1])

def get(x, y):
	r = math.floor(get2RowStart(x))
	if y % 2 == 0:
		r += math.floor(n * n / 2) * (1 if x % 2 == 1 else -1) - 1
		if n % 2 == 1 & x % 2 == 1:
			r += 1
	return int(r + math.floor(y / 2))

def get2RowStart(x):
	return 1 + math.floor((x - 1) / 2) * n + (math.floor(n * (n + 1) / 2) if x % 2 == 0 else 0)
result = ''
for i in range(q):
	query = input().split()
	result += str(get(int(query[0]), int(query[1]))) + '\n'
print(result)


import sys
(n, q) = map(int, sys.stdin.readline().strip().split())
pp = n * n
fh = (pp + 1) // 2
fr1 = 1
sr1 = fh + n // 2 + 1
for _ in range(q):
	ans = 0
	(x, y) = map(int, sys.stdin.readline().strip().split())
	ab = (x - 1) // 2 * n
	bc = y // 2
	if x % 2:
		ans += ab + fr1
		if y % 2:
			ans += bc
		else:
			ans += fh + bc - 1
	else:
		ans += ab + sr1
		if y % 2:
			ans += bc
		else:
			ans -= pp - fh
			ans += bc - 1
	print(ans)


I = lambda : map(int, input().split())
(n, q) = I()
A = []
for _ in range(q):
	(x, y) = I()
	A.append((n * (x - 1) + y + 1 + (n * n if (x + y) % 2 else 0)) // 2)
print(*A, sep='\n')


from sys import stdin

def main():
	(n, m) = map(int, input().split())
	(n2, m) = (n * n // 2, n - 1 - n % 2)
	l = stdin.read().splitlines()
	for (i, s) in enumerate(l):
		(x, y) = map(int, s.split())
		t = (x * n + y - m) // 2
		l[i] = str(t + n2 if (x ^ y) & 1 else t)
	print('\n'.join(l))
main()


import math
import sys
inputlist = sys.stdin.readlines()
(n, q) = list(map(int, inputlist[0].split(' ')))
for i in range(q):
	(x, y) = list(map(int, inputlist[i + 1].split(' ')))
	if (x + y) % 2 == 0:
		print(((x - 1) * n + y + 1) // 2)
	else:
		initial_sum = (n * n + 1) // 2
		print(initial_sum + ((x - 1) * n + y + 1) // 2)


(n, q) = map(int, input().strip().split())
res = []
for i in range(q):
	(x, y) = map(int, input().strip().split())
	a = (x - 1) * n + y + 1
	if (x + y) % 2 != 0:
		a = a + n * n
	res.append(a // 2)
print(*res)


from math import ceil
(n, q) = map(int, input().split())
l = []
for i in range(q):
	(x, y) = map(int, input().split())
	c = (x - 1) * n + y
	if (x + y) % 2 == 0:
		l.append((c + 1) // 2)
	else:
		l.append((c + 1) // 2 + (n ** 2 + 1) // 2)
print(*l)


from functools import cmp_to_key
from math import *
import sys

def main():
	(n, q) = [int(i) for i in sys.stdin.readline().split(' ')]
	for i in range(q):
		(x, y) = [int(i) for i in sys.stdin.readline().split(' ')]
		tot = n * (x - 1) + y
		tot = (tot + 1) // 2
		if (x + y) % 2 == 1:
			tot += (n * n + 1) // 2
		print(tot)
main()


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def msi():
	return map(str, input().strip().split(' '))

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(100000000)
	threading.stack_size(40960000)
	thread = threading.Thread(target=main)
	thread.start()
from math import ceil, floor, log, sqrt, factorial
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[1]

def sort2(l):
	return sorted(l, key=getKey, reverse=True)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r))

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def main():
	if True:
		(n, q) = mi()
		p = ceil(n / 2) + floor(n / 2)
		for i in range(q):
			(x, y) = mi()
			if (x + y) % 2 == 0:
				d = (x - 1) // 2
				r = (x - 1) % 2
				num = d * p
				if n % 2 == 0:
					if r == 1:
						num += ceil(n / 2)
					num += ceil(y / 2)
				else:
					if r == 1:
						num += ceil(n / 2)
					num += ceil(y / 2)
				print(num)
			else:
				x1 = n
				y1 = n
				d = (x1 - 1) // 2
				r = (x1 - 1) % 2
				num = d * p
				if r == 1:
					num += ceil(n / 2)
				num += ceil(y1 / 2)
				d = (x - 1) // 2
				r = (x - 1) % 2
				num += d * p
				if n % 2 == 0:
					if r == 1:
						num += floor(n / 2)
					num += ceil(y / 2)
				else:
					if r == 1:
						num += floor(n / 2)
					num += ceil(y / 2)
				print(num)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from math import ceil, floor
(n, q) = map(int, input().split())
ans = []
for _ in range(int(q)):
	(a, b) = map(int, input().split())
	ans.append(((a - 1) * n + b + 1) // 2)
	if a + b & 1:
		ans[-1] += (n ** 2 + 1) // 2
print('\n'.join(map(str, ans)))


import sys
readline = sys.stdin.readline
(N, Q) = map(int, readline().split())
Ans = [None] * Q
for i in range(Q):
	(a, b) = map(int, readline().split())
	Ans[i] = (a - 1) // 2 * N + (-(-N // 2) if (a + b) % 2 == 0 else N // 2) * ((a + 1) % 2) + -(-b // 2) + -(-N ** 2 // 2) * ((a + b) % 2)
print('\n'.join(map(str, Ans)))


import sys
l = sys.stdin.readlines()
(n, q) = map(int, l[0].split())
k = (n * n + 1) // 2
for i in range(q):
	(x, y) = map(int, l[i + 1].split())
	ans = (x - 1) * n + y
	ans = (ans + 1) // 2
	if (x + y) % 2 == 1:
		ans += k
	print(ans)


import sys
(n, q) = map(int, sys.stdin.readline().split())
n1 = n % 2
n2 = n // 2
n3 = (n * n + 1) // 2
for i in range(q):
	(x, y) = map(int, sys.stdin.readline().split())
	if n1 == 0:
		if (x + y) % 2 == 0:
			print((x - 1) * n2 + (y - 1) // 2 + 1)
		else:
			print(n3 + (x - 1) * n2 + (y - 1) // 2 + 1)
	elif (x + y) % 2 == 0:
		print(((x - 1) * n + 1) // 2 + (y - 1) // 2 + 1)
	else:
		print(n3 + (x - 1) * n // 2 + (y - 1) // 2 + 1)


import sys
(n, q) = map(int, sys.stdin.readline().rstrip().split())
for _ in range(q):
	(x, y) = map(int, sys.stdin.readline().rstrip().split())
	(x, y) = (x - 1, y - 1)
	if (x + y) % 2 == 0:
		res = 1
		res += x // 2 * n
		res += x % 2 * ((n + 1) // 2)
		res += y // 2
		print(res)
	else:
		res = (n * n + 1) // 2 + 1
		res += x // 2 * n
		res += x % 2 * (n // 2)
		res += y // 2
		print(res)


from sys import stdin
from math import ceil
inp = stdin.readline
(n, t) = [int(x) for x in inp().strip().split()]
for _ in range(t):
	(x, y) = [int(x) for x in inp().strip().split()]
	s = (x - 1) * n + y
	if (x + y) % 2:
		print((s + 1) // 2 + (n ** 2 + 1) // 2)
	else:
		print((s + 1) // 2)


import sys

def write(x):
	sys.stdout.write(str(x) + '\n')
[n, q] = [int(x) for x in sys.stdin.readline().strip().split()]
for i in range(q):
	(x, y) = [int(x) for x in sys.stdin.readline().strip().split()]
	if (x + y) % 2 == 0:
		write(((x - 1) * n + y + 1) // 2)
	else:
		write((n * n + 1) // 2 + ((x - 1) * n + y + 1) // 2)


fl = list(map(int, input().split(' ')))
n = fl[0]
result = []
for i in range(fl[1]):
	l = list(map(int, input().split(' ')))
	r = l[0]
	c = l[1]
	if n % 2 == 0:
		odd_offset = 0
		if (r + c) % 2 == 1:
			odd_offset = n ** 2 // 2
			if r % 2 == 1:
				c -= 1
		row_offset = (r - 1) * n // 2
		if r % 2 == 0:
			c -= 1
		col_offset = c // 2 + 1
		result.append(odd_offset + row_offset + col_offset)
	else:
		row_offset = (r - 1) // 2 * n
		if (r + c) % 2 == 0:
			odd_offset = 0
			if c % 2 == 1:
				col_offset = c // 2 + 1
			else:
				small_o = n // 2 + 1
				col_offset = c // 2 + small_o
		else:
			odd_offset = n ** 2 // 2 + 1
			if c % 2 == 0:
				col_offset = c // 2
			else:
				small_o = n // 2
				col_offset = c // 2 + 1 + small_o
		result.append(odd_offset + row_offset + col_offset)
for r in result:
	print(r)


import sys
from math import ceil

def func(n):
	return int(n * n / 2) + n % 2

def print_cell_num(n, x, y):
	if x % 2 == 0 and y % 2 == 0 or (x % 2 == 1 and y % 2 == 1):
		num_so_far = n * ((x - 1) // 2)
		if x % 2 == 0:
			num_so_far += n % 2 + n // 2
		num_so_far += y // 2 + y % 2
		sys.stdout.write(str(num_so_far) + '\n')
		return
	if x % 2 == 0 and y % 2 == 1 or (x % 2 == 1 and y % 2 == 0):
		num_so_far = func(n)
		num_so_far += n * ((x - 1) // 2)
		if x % 2 == 0:
			num_so_far += n // 2
		num_so_far += y // 2 + y % 2
		sys.stdout.write(str(num_so_far) + '\n')
		return
lst = sys.stdin.readlines()
(n, q) = map(int, lst[0].split())
for i in range(q):
	(x, y) = map(int, lst[i + 1].split())
	print_cell_num(n, x, y)


import math

def query(n, a, b):
	if (a + b) % 2 == 0:
		temp = ((a - 1) * n + b + 1) // 2
	else:
		temp = (n ** 2 + n * (a - 1) + b + 1) // 2
	return temp
(n, q) = map(int, input().split())
ans = []
for i in range(q):
	(a, b) = map(int, input().split())
	ans.append(query(n, a, b))
for a in ans:
	print(a)


import math
import sys
while True:
	try:

		def solution(n, q):
			t = []
			for i in range(q):
				(a, b) = map(int, input().split())
				cunt = ((a - 1) * n + b + 1) // 2
				if a + b & 1:
					t.append(cunt + (n ** 2 + 1) // 2)
				else:
					t.append(cunt)
			print(*t)

		def read():
			(n, q) = map(int, input().split())
			solution(n, q)
		if __name__ == '__main__':
			read()
	except EOFError:
		break


import sys
inp = sys.stdin.readlines()
ii = 0
(n, q) = map(int, inp[ii].split())
ii += 1
for qu in range(q):
	(x, y) = map(int, inp[ii].split())
	ii += 1
	c = (x - 1) * n + y
	a = (c + 1) // 2
	if (x + y) % 2 == 1:
		a += (n ** 2 + 1) // 2
	print(a)


(n, numQueries) = map(int, input().split())
answers = []
for i in range(numQueries):
	(x, y) = map(int, input().split())
	mid = (n * n + 1) // 2
	pos = (x - 1) * n + y
	ans = (pos + 1) // 2
	if (x + y) % 2 == 1:
		ans += mid
	answers.append(ans)
for ans in answers:
	print(ans)


(N, Q) = map(int, input().split())
qs = [tuple(map(lambda x: int(x) - 1, input().split())) for i in range(Q)]
M = (N * N + 1) // 2
ans = []
if N % 2:
	for (y, x) in qs:
		a = 1
		if (x + y) % 2:
			a += M
		a += x // 2
		a += N * (y // 2)
		if y % 2:
			if (x + y) % 2:
				a += N // 2
			else:
				a += N // 2 + 1
		ans.append(a)
else:
	for (y, x) in qs:
		a = 1
		if (x + y) % 2:
			a += M
		a += x // 2
		a += N // 2 * y
		ans.append(a)
print(*ans, sep='\n')


f = [int(x) for x in input().split(' ')]
n = f[0]
q = f[1]
a = [0] * q
b = [0] * q
for i in range(q):
	(a[i], b[i]) = [int(x) for x in input().split(' ')]
for i in range(q):
	c = (a[i] - 1) * n + b[i]
	x = (c + 1) // 2
	if (a[i] + b[i]) % 2 == 1:
		x += (n * n + 1) // 2
	print(x)


import math
import sys

def solution(n, q):
	t = []
	for i in range(q):
		(a, b) = map(int, input().split())
		cunt = ((a - 1) * n + b + 1) // 2
		if a + b & 1:
			t.append(cunt + (n ** 2 + 1) // 2)
		else:
			t.append(cunt)
	print(*t)

def read():
	(n, q) = map(int, input().split())
	solution(n, q)
read()


from sys import stdin, stdout
from collections import deque

def ev_even(s, c):
	cnt = (n + 1) // 2 * (s - 1) + (c - 1) // 2
	return cnt + 1

def ev_odd(s, c):
	cnt = n // 2 * (s - 1) + (c - 1) // 2
	return cnt + 1 + (n * n + 1) // 2

def od_even(s, c):
	cnt = (n + 1) // 2 * ((s - 1 + 1) // 2) + n // 2 * ((s - 1) // 2) + (c - 1) // 2
	return cnt + 1

def od_odd(s, c):
	cnt = (n + 1) // 2 * ((s - 1) // 2) + n // 2 * ((s - 1 + 1) // 2) + (c - 1) // 2
	return cnt + 1 + (n * n + 1) // 2
(n, q) = map(int, stdin.readline().split())
for i in range(q):
	(s, c) = map(int, stdin.readline().split())
	if s + c & 1:
		if not n & 1:
			stdout.write(str(ev_odd(s, c)) + '\n')
		else:
			stdout.write(str(od_odd(s, c)) + '\n')
	elif not n & 1:
		stdout.write(str(ev_even(s, c)) + '\n')
	else:
		stdout.write(str(od_even(s, c)) + '\n')


import sys, string
(n, q) = map(int, sys.stdin.readline().split())
for _ in range(q):
	(a, b) = map(int, sys.stdin.readline().split())
	if a % 2 == 0:
		rn = (a - 1) // 2
		ans = 1 + rn * n + n * (n + 1) // 2
		if b % 2 == 0:
			cn = (b - 1) // 2
			ans += cn - n ** 2 // 2
		else:
			cn = b // 2
			ans += cn
	else:
		rn = a // 2
		ans = 1 + rn * n
		if b % 2 == 0:
			cn = (b - 1) // 2
			if n % 2 == 0:
				ans += cn + n ** 2 // 2
			else:
				ans += cn + n ** 2 // 2 + 1
		else:
			cn = b // 2
			ans += cn
	print(ans)


def cin(obj=list, type=int, sep=' '):
	return obj(map(type, input().split(sep)))
(n, q) = cin()
ans = [0] * q
for i in range(q):
	(x, y) = list(map(int, input().split()))
	ans[i] = (x + y) % 2 * ((n ** 2 + 1) // 2) + (x - 1) // 2 * (n // 2 * 2 + n % 2) + (x - 1) % 2 * (n // 2 + n % 2 * ((x + y) % 2 == 0)) + (y + 1) // 2
print(*ans, sep='\n')


from sys import stdin, stdout
(a, b) = map(int, stdin.readline().split())
f = (a * a + 1) // 2
for i in stdin:
	(x, y) = map(int, i.split())
	z = ((x - 1) * a + y + 1) // 2
	if x % 2 == y % 2:
		print(z)
	else:
		print(z + f)


(f, c, i) = (lambda x: x // 2, lambda x: x - f(x), lambda : map(int, input().split()))
(n, q) = i()
res = ''
for _ in range(q):
	(x, y) = i()
	if (x + y) % 2 == 0:
		res += str(f(x) * n - f(n) * (x % 2 ^ 1) + c(y)) + '\n'
	else:
		res += str(c(n ** 2) + (f(x) * n - c(n) * (x % 2 ^ 1)) + c(y)) + '\n'
print(res, end='')


import math

def main():
	ans_list = []
	(n, q) = map(int, input().split())
	for i in range(q):
		(x, y) = map(int, input().split())
		count1 = (x - 1) // 2
		count2 = n // 2
		if (x + y) % 2 == 0:
			if (x - 1) % 2 != 0:
				if n % 2 != 0:
					p = (count1 + 1) * (count2 + 1)
				else:
					p = (count1 + 1) * count2
			elif n % 2 != 0:
				p = count1 * (count2 + 1)
			else:
				p = count1 * count2
			p += math.floor((x - 1) / 2) * math.floor(n / 2)
		else:
			if (x - 1) % 2 != 0:
				p = (count1 + 1) * math.floor(n / 2)
			else:
				p = count1 * math.floor(n / 2)
			if n % 2 != 0:
				p += count1 * (count2 + 1)
			else:
				p += count1 * count2
		if (x + y) % 2 == 0:
			if x % 2 == 0:
				start = 2
			else:
				start = 1
		elif x % 2 == 0:
			start = 1
		else:
			start = 2
		k = (y - start) // 2
		k += 1
		ans = p + k
		if (x + y) % 2 != 0:
			count = n ** 2 // 2
			if n ** 2 % 2 != 0:
				count += 1
			ans += count
		ans_list.append(ans)
	for i in ans_list:
		print(i)
main()


def prog():
	from sys import stdin
	(n, q) = map(int, stdin.readline().split())
	a = n // 2
	if n % 2 == 0:
		b = a
		c = n * n // 2
	else:
		b = a + 1
		c = n * n // 2 + 1
	for i in range(q):
		(x, y) = map(int, stdin.readline().split())
		(e, r, t, u) = (x % 2, y % 2, x // 2, y // 2)
		if (x + y) % 2 == 0:
			if e == 1:
				print((a + b) * t + u + 1)
			else:
				print(b * t + a * (t - 1) + u)
		elif e == 1:
			print(c + (a + b) * t + u)
		else:
			print(c + a * t + b * (t - 1) + u + 1)
prog()


a = list(map(int, input().split()))
n = a[0]
q = a[1]
ans = []
starte = 0
if n % 2 == 1:
	starto = n ** 2 // 2 + 1
else:
	starto = n ** 2 // 2
for i in range(q):
	a = list(map(int, input().split()))
	x = a[0]
	y = a[1]
	line = x
	cell = y
	if n % 2 == 1:
		if line % 2 == 0:
			if (x + y) % 2 == 1:
				t = line // 2 * (n // 2) + (line // 2 - 1) * (n // 2 + 1) + starto + cell // 2 + 1
			else:
				t = (line // 2 - 1) * (n // 2) + line // 2 * (n // 2 + 1) + starte + cell // 2
		elif (x + y) % 2 == 1:
			t = line // 2 * (n // 2 + 1) + line // 2 * (n // 2) + starto + cell // 2
		else:
			t = line // 2 * (n // 2 + 1) + line // 2 * (n // 2) + starte + cell // 2 + 1
	elif line % 2 == 0:
		if (x + y) % 2 == 0:
			t = (line - 1) * (n // 2) + starte + cell // 2
		else:
			t = (line - 1) * (n // 2) + starto + (cell // 2 + 1)
	elif (x + y) % 2 == 1:
		t = (line - 1) * (n // 2) + starto + cell // 2
	else:
		t = (line - 1) * (n // 2) + starte + cell // 2 + 1
	ans.append(t)
for i in range(q):
	print(ans[i])


(n, q) = map(int, input().split())
list = []
for _ in range(q):
	(x, y) = map(int, input().split())
	count = (x - 1) * n + y
	if (x + y) % 2 == 0:
		a = (count + 1) // 2
		list.append(a)
	else:
		a = (count + 1) // 2
		b = (n ** 2 + 1) // 2
		list.append(a + b)
for i in range(len(list)):
	print(list[i], end=' ')


(n, q) = map(int, input().strip().split(' '))
a = []
for i in range(q):
	(x, y) = map(int, input().strip().split(' '))
	a.append([x, y])
if n % 2 == 0:
	for (x, y) in a:
		if (x + y) % 2 == 0:
			k = 0
		else:
			k = n * n // 2
		k = k
		l = (x - 1) * n // 2
		m = int(y / 2 + 0.5)
		print(k + l + m)
else:
	for (x, y) in a:
		if (x + y) % 2 == 0:
			k = 0
			l = (x - 1) // 2 * n
			p = (x - 1) % 2 * int(n / 2 + 0.5)
			m = int(y / 2 + 0.5)
			print(k + l + m + p)
			continue
		else:
			k = n * n // 2 + 1
			l = (x - 1) // 2 * n
			p = (x - 1) % 2 * int(n / 2 - 0.5)
			m = int(y / 2 + 0.5)
			print(k + l + m + p)