#include <bits/stdc++.h>
using namespace std;
long long n, q;
long long solve(long long x, long long y) {
  long long ans = 0;
  if (n % 2 == 0) {
    if ((x + y) & 1) {
      ans = (x - 1) * n / 2 + n * n / 2 + (y + 1) / 2;
    } else {
      ans = (x - 1) * n / 2 + (y + 1) / 2;
    }
  } else {
    if ((x & 1) && (y & 1)) {
      ans = x / 2 * n + (y + 1) / 2;
    } else if (!(x & 1) && !(y & 1)) {
      ans = x / 2 * n - n + (n + 1) / 2 + y / 2;
    } else if ((x & 1) && !(y & 1)) {
      ans = (n * n + 1) / 2 + (x / 2) * n + y / 2;
    } else {
      ans = (n * n + 1) / 2 + (x / 2) * n - n + n / 2 + (y + 1) / 2;
    }
  }
  return ans;
}
int main() {
  cin >> n >> q;
  long long x, y;
  long long res;
  for (int i = 0; i < q; i++) {
    scanf("%I64d%I64d", &x, &y);
    res = solve(x, y);
    printf("%I64d\n", res);
  }
  return 0;
}
