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