#include <bits/stdc++.h>
using namespace std;
double PI = 3.14159265358979323846;
const int MAX = 1e9;
const int rx[8] = {1, 1, 1, -1, -1, -1, 0, 0};
const int ry[8] = {0, -1, 1, 0, -1, 1, 1, -1};
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
long long n, q, x, y, ev, od, ans, h;
int main() {
  cin >> n >> q;
  ev = (n * n) / 2 + ((n * n) % 2);
  od = ev + 1;
  map<pair<long long, long long>, long long> ma;
  ma[{1, 1}] = 1;
  ma[{1, 2}] = 6;
  ma[{1, 3}] = 2;
  ma[{2, 1}] = 7;
  ma[{2, 2}] = 3;
  ma[{2, 3}] = 8;
  ma[{3, 1}] = 4;
  ma[{3, 2}] = 9;
  ma[{3, 3}] = 5;
  while (q--) {
    cin >> x >> y;
    if (n == 3) {
      cout << ma[{x, y}] << endl;
      continue;
    }
    if ((x + y) % 2 == 0) {
      if (n % 2 == 0) {
        ans = (x - 1) * (n / 2);
        if (x % 2 == 0) {
          ans += (y / 2);
        } else {
          ans += (y + 1) / 2;
        }
      } else {
        if (x % 2 == 1) {
          ans = (x - 1) / 2 * (n - n / 2) + (x - 1) / 2 * (n / 2);
        } else {
          ans = (x - 2) / 2 * (n - n / 2) + (x - 2) / 2 * (n / 2) + (n - n / 2);
        }
        if (x % 2 == 0) {
          ans += (y / 2);
        } else {
          ans += (y + 1) / 2;
        }
      }
      cout << ans << endl;
    } else {
      if (n % 2 == 0) {
        ans = (x - 1) * (n / 2);
        if (x % 2 == 0) {
          ans += ((y + 1) / 2);
        } else {
          ans += (y / 2);
        }
      } else {
        if (x % 2 == 1) {
          ans = (x - 1) / 2 * (n / 2) + (x - 1) / 2 * (n - n / 2);
        } else {
          ans = (x - 2) / 2 * (n / 2) + (x - 2) / 2 * (n - n / 2) + (n / 2);
        }
        if (x % 2 == 0) {
          ans += ((y + 1) / 2);
        } else {
          ans += (y / 2);
        }
      }
      cout << ans + ev << endl;
    }
  }
  return 0;
}
