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.

Difficulty: interview

Starter code:

Solutions:
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)

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)

from math import ceil
n,m=list(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=list(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)      


def solve_query(n, i, j):
    i, j = i - 1, j - 1  # from zero
    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]


def __starting_point():
    #n = 4
    #for i in range(1, n + 1):
    #    print([solve_query(n, i, j) for j in range(1, n + 1)])
    n, q = list(map(int, input().split()))
    queries = [list(map(int, input().split())) for _ in range(q)]
    for answer in solve(n, queries):
        print(answer)

__starting_point()

import sys

n,q = list(map(int, sys.stdin.readline().split()))
h=-(-n*n//2)
for i in range(q):
    x,y = list(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)








n,q=list(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

        else:
            if 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)




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')


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))

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))

#
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))

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)
		else:
			if((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
	else:
		if (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)
		else:
			if((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])
				


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 sys

def __starting_point():
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    size = data[0]
    n = data[1]
    #size, n = map(int, input().split())
    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)
__starting_point()

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 = list(map(int, sys.stdin.readline().split()))
for line in sys.stdin:
    print(query(n, *list(map(int, line.split()))))


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)


















n,q=map(int, input().strip().split(" "))
# print(n,q)
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:
        #     print(1)
        #     continue
        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+.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-.5) 
            m=int(y/2 + 0.5)
            print(k+l+m+p)

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))

n,q=list(map(int,input().split()))
nn=(n**2+1) //2
#for y in range(1,n+1):
#    for x in range(1,n+1):
#        if (x+y)%2==0:
#            print( ((y-1)*n+x+1)//2)
#        else:
#            print( nn+((y-1)*n+x+1)//2 )

#n=10**9
#q=10**5
#y,x=10**9,10**9
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))


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())))

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
    else:
        if 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)



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)
    else:
        if (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().strip().split())
nc=n
# print(n,q)
    
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())
        # print(n,q,x,y)
        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
    
        else:
            if(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
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
		#print(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)