#include <bits/stdc++.h>
using namespace std;
long long dx[4] = {1, 0, -1, 0};
long long dy[4] = {0, -1, 0, 1};
template <class T>
void inputVector(vector<T>& v, long long n) {
  v.resize(n);
  for (long long i = 0; i < v.size(); i++) cin >> v[i];
}
signed main() {
  long long n, q;
  cin >> n >> q;
  for (long long _ = 0; _ < (q); _++) {
    long long x, y;
    scanf("%lld %lld", &y, &x);
    x--;
    y--;
    long long ret = 0;
    if (n % 2) {
      long long type = (x + y) % 2;
      if (type == 0) {
        ret += (y / 2) * n;
        if (y % 2) ret += n / 2 + 1;
        ret += x / 2;
        ret++;
      } else {
        ret += (y / 2) * n + (n * n) / 2 + 1;
        if (y % 2) ret += n / 2;
        ret += x / 2;
        ret++;
      }
    } else {
      long long type = (x + y) % 2;
      if (type == 0) {
        ret += n / 2 * y;
        ret += x / 2;
        ret++;
      } else {
        ret += n / 2 * y + n * n / 2;
        ret += x / 2;
        ret++;
      }
    }
    printf("%lld\n", ret);
  }
  return 0;
}
