#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[]) {
  long long n, q;
  cin >> n >> q;
  while (q--) {
    long long x, y, ans;
    cin >> x >> y;
    if (n % 2) {
      long long frst, idx;
      ans = 0;
      idx = (n * n) / 2 + (n * n) % 2;
      if ((x + y) % 2) ans = idx;
      if (x % 2) {
        frst = (y / 2) + (y % 2);
      } else {
        frst = (y / 2) + (n / 2) + (n % 2);
      }
      ans += frst + (n * ((x - 1) / 2));
      cout << ans << endl;
    } else {
      ans = y / 2 + y % 2;
      ans += (x - 1) * (n / 2);
      if ((x + y) % 2) ans += (n * n) / 2;
      cout << ans << endl;
    }
  }
  return 0;
}
