#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  long long int n, q;
  cin >> n >> q;
  while (q--) {
    long long int x, y, t;
    cin >> x >> y;
    t = (x - 1) / 2 * n;
    if (x % 2 == 0) {
      t += n / 2 + (n % 2 * (y % 2 == 0));
    }
    t += (y + 1) / 2;
    if ((x + y) % 2) {
      t += (n * n + 1) / 2;
    }
    cout << t << '\n';
  }
}
