You are given a chessboard of size n × n. It is filled with numbers from 1 to n^2 in the following way: the first ⌈ (n^2)/(2) ⌉ numbers from 1 to ⌈ (n^2)/(2) ⌉ are written in the cells with even sum of coordinates from left to right from top to bottom. The rest n^2 - ⌈ (n^2)/(2) ⌉ numbers from ⌈ (n^2)/(2) ⌉ + 1 to n^2 are written in the cells with odd sum of coordinates from left to right from top to bottom. The operation ⌈x/y⌉ 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 ≤ n ≤ 10^9, 1 ≤ q ≤ 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 ≤ x_i, y_i ≤ 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.
import java.io.*;
import java.math.*;
import java.util.*;
import static java.lang.Math.*;

public class SuperClassss{
    static class Run{
        static void main(){
            int n = nextInt(), q = nextInt(); //n*n - самое большое - (n-1;n)
            long k1 = (n+1)/2, k2 = n - k1;
            //в сторках y%2==1 по k1 первых чисел
            //в остальных по k2 первых чисел
            long str, count, max;
            int x, y;
            x = n; y = n;
            str = (y+1)/2;
            max = k1*str+k2*(y-str);
            max-=(n-x)/2;
            for(int i = 0; i<q; i++){
                y = nextInt();
                x = nextInt();
                if ((x+y)%2==0){
                    str = (y+1)/2;
                    count = k1*str+k2*(y-str); //последнее число в данной строке
                    count-=(n-x)/2; //(n-x+1)/2
                }
                else{
                    str = (y+1)/2;
                    count = k2*str+k1*(y-str)+max; //последнее число в данной строке
                    count-=(n-x)/2; //(n-x+1)/2
                }
                println(count);
            }
        }
    }

    public static void main(String[] args) {
        Run.main();
        out.flush();
    }

    static final String alph = "abcdefghijklmnopqrstuvwxyz";
    static final int INF = Integer.MAX_VALUE;
    static Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(System.out);
    static StreamTokenizer in1 = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedReader in2 = new BufferedReader(new InputStreamReader(System.in));

    public static<T extends Number> long[] getPrefixSumArray(T[] array){
        long res[] = new long[size(array)];
        res[0] = array[0].longValue();
        for(int i = 1; i<size(array); i++) res[i] = res[i-1]+array[i].longValue();
        return res;
    }

    public static char[] strToArray(String s){
        return s.toCharArray();
    }

    public static char[] strToArray(StringBuilder s){
        return new String(s).toCharArray();
    }

    public static char chAt(String s, int pos){
        return s.charAt(pos);
    }

    public static char chAt(StringBuilder s, int pos){
        return s.charAt(pos);
    }

    public static int[] prefix_function(String s, String t){
        String edit = s+"#"+t;
        return prefix_function(edit);
    }

    public static int[] prefix_function(String edit){
        int len = edit.length(), pi[] = new int[len];
        for(int i = 1; i<len; i++){
            int j = pi[i-1];
            while(j>0 && edit.charAt(i)!=edit.charAt(j)) j = pi[j-1];
            if(edit.charAt(i)==edit.charAt(j)) j++;
            pi[i] = j;
        }
        return pi;
    }

    public static int size(String obj){
        return obj.length();
    }

    public static int size(StringBuilder obj){
        return obj.length();
    }

    public static int size(Collection<?> obj){
        return obj.size();
    }

    public static int size(AbstractMap<?, ?> obj){
        return obj.size();
    }

    public static int size(AbstractCollection<?> obj){
        return obj.size();
    }

    public static<T> int size(T[] obj){
        return obj.length;
    }

    public static <T> void print(T... args) {
        for (T x : args) {
            out.print(x.toString());
        }
    }

    public static <T> void println(T... args) {
        print(args);
        out.println();
    }

    public static long nextLong() {
        try {
            in1.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (long) in1.nval;
    }

    public static int nextInt() {
        try {
            in1.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in1.nval;
    }

    public static String nextLine(){
        return in.nextLine();
    }

    public static String nextString() {
        try {
            return in2.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }

    public static String next(){
        return in.next();
    }

    public static char nextChar() {
        try {
            return (char) in2.read();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return '!';
    }

    public static void readArray(int[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = nextInt();
    }

    public static void readArray(long[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = nextInt();
    }

    public static void readArray(char[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = nextChar();
    }

    public static void readArray(String[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = nextString();
    }

    public static void readArray(StringBuilder[] array) {
        for (int i = 0; i < array.length; i++)
            array[i] = new StringBuilder(nextString());
    }

    public static int gcd(int a, int b) {
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }

    public static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    public static int min(int...args){
        Arrays.sort(args);
        return (args[0]);
    }

    public static int max(int...args){
        Arrays.sort(args);
        return(args[args.length-1]);
    }

    public static double s(int x1, int y1, int x2, int y2, int x3, int y3) {
        return Math.abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)) / 2.0;
    }

    public static LinkedList<Integer> isPrimeList(int n) {
        LinkedList<Integer> res = new LinkedList<>();
        boolean prime[] = new boolean[n];
        Arrays.fill(prime, true);
        prime[1] = false;
        for (int i = 2; i * i < n; i++) {
            if (prime[i])
                for (int j = i * i; j < n; j += i)
                    prime[j] = false;
        }
        for (int i = 2; i < n; i++)
            if (prime[i]) res.add(i);
        return res;
    }

    public static BigInteger bigSqrt(BigInteger n) {
        BigInteger a = BigInteger.ONE.shiftLeft((n.bitLength() + 1) / 2), next = a.subtract(BigInteger.ONE);
        while (next.compareTo(a) < 0) {
            a = next;
            next = a.add(n.divide(a)).divide(BigInteger.valueOf(2));
        }
        return a;
    }

    public static<T> ArrayList<T> assign(int size, T obj){
        ArrayList res = new ArrayList(size);
        for(int i = 0; i<size; i++) res.add(obj);
        return res;
    }

    //добавить запрос минимума
    static class FenwickTree{
        ArrayList<Integer> tree;
        int n;
        FenwickTree(ArrayList<Integer> a){
            n = size(a);
            tree = new ArrayList(n);
            tree = assign(n, 0);
            for(int i = 0; i<n; i++){
                inc(i, a.get(i));
            }
        }

        void inc(int i, int d){
            for(; i<n; i=(i|(i+1)))
                tree.set(i, tree.get(i)+d);
        }

        void add(int k, int x){
            while(k<n){
                int adds = tree.get(k)+x;
                tree.set(k, adds);
                k += k&-k;
            }
        }

        int getMin(int r){
            int result = INF;
            for(; r>=0; r = (r & (r+1)) - 1){
                result = min(result, tree.get(r));
            }
            return result;
        }

        int sum(int r){
            int res = 0;
            for(;r>=0;r = (r&(r+1))-1)
                res+= tree.get(r);
            return res;
        }

        int sum(int l, int r){
            return sum(r)-sum(l-1);
        }

        void out(){
            for(int i = 0; i<n; i++)
                print(tree.get(i)+" ");
        }
    }
}