#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n, q, i, j;
  cin >> n >> q;
  long long ns = 1LL * n * n;
  long long sh = (ns + 1LL) / 2;
  long long ans;
  while (q--) {
    cin >> i >> j;
    if (i % 2) {
      if (j % 2) {
        ans = 1LL + n * (i / 2) + (j / 2);
        cout << ans;
      } else {
        ans = 1LL + n * (i / 2) + sh + ((j / 2) - 1LL);
        cout << ans;
      }
    } else {
      if (j % 2) {
        ans = 1LL + n * ((i - 1) / 2) + sh + (n / 2) + (j / 2);
        cout << ans;
      } else {
        ans = 1LL + ((i - 1) / 2) * n + ((n + 1) / 2) + ((j / 2) - 1LL);
        cout << ans;
      }
    }
    cout << "\n";
  }
}
