#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n, q;
  scanf("%lld%lld", &n, &q);
  if (n % 2) {
    long long m = n * n;
    long long z = (m / 2) + 2;
    while (q--) {
      long long x, y;
      scanf("%lld%lld", &x, &y);
      long long odd = x / 2;
      long long ev = max((long long)0, x - odd - 1);
      if ((x + y) % 2) {
        x--;
        y--;
        long long st = z + odd * (n / 2) + ev * ((n / 2) + 1);
        printf("%lld\n", st + (y / 2));
      } else {
        x--;
        y--;
        long long k = n / 2;
        long long st = 1 + odd * ((n / 2) + 1) + ev * (n / 2);
        printf("%lld\n", st + (y / 2));
      }
    }
  } else {
    long long m = n * n;
    long long z = (m / 2) + 1;
    long long h = n / 2;
    while (q--) {
      long long x, y;
      scanf("%lld%lld", &x, &y);
      if ((x + y) % 2) {
        x--;
        y--;
        long long st = z + (x * h);
        printf("%lld\n", st + (y / 2));
      } else {
        x--;
        y--;
        long long st = 1 + (x * h);
        printf("%lld\n", st + (y / 2));
      }
    }
  }
  return 0;
}
