#include <bits/stdc++.h>
using namespace std;
int main() {
  long long int n, q, x, y, p, q1, r;
  cin >> n >> q1;
  if (n % 2 == 0) {
    while (q1--) {
      cin >> x >> y;
      p = (x - 1) * (n / 2) + (y + 1) / 2;
      ((x + y) % 2 == 0) ? cout << p : cout << n * n / 2 + p;
      cout << "\n";
    }
  } else {
    while (q1--) {
      cin >> x >> y;
      if ((x + y) % 2 == 0) {
        p = (x / 2) * ((n + 1) / 2);
        q = ((x - 1) / 2) * (n / 2);
        if (x % 2 == 0) {
          r = y / 2;
        } else {
          r = (y + 1) / 2;
        }
        cout << p + q + r;
      } else {
        p = (x / 2) * (n / 2);
        q = ((x - 1) / 2) * ((n + 1) / 2);
        if (x % 2 == 1) {
          r = y / 2;
        } else {
          r = (y + 1) / 2;
        }
        cout << (n * n + 1) / 2 + p + q + r;
      }
      cout << "\n";
    }
  }
}
