#include <bits/stdc++.h>
using namespace std;
const long long MaxN = 301002;
long long n, q;
long long up(long long a, long long b) {
  if (a % b != 0) return (a / b) + 1;
  return (a / b);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  while (q--) {
    long long x, y;
    cin >> x >> y;
    long long resp = 0;
    if ((x + y) % 2 == 0) {
      if (x & 1) {
        resp += (x / 2LL) * up(n, 2LL);
        resp += (x / 2LL) * (n / 2LL);
        resp += up(y, 2LL);
      } else {
        resp += (x / 2LL) * up(n, 2LL);
        resp += ((x / 2LL) - 1) * (n / 2LL);
        resp += y / 2LL;
      }
    } else {
      resp = up(n * n, 2LL);
      if (x & 1) {
        resp += (x / 2LL) * (n / 2LL);
        resp += (x / 2LL) * up(n, 2LL);
        resp += y / 2LL;
      } else {
        resp += (x / 2LL) * (n / 2LL);
        resp += ((x / 2LL) - 1) * up(n, 2LL);
        resp += up(y, 2LL);
      }
    }
    cout << resp << "\n";
  }
}
