#include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N   410000

 #define MOD 1000000007

 #define eps 1e-8

 #define pi acos(-1)

 #define oo 110000000000000

 char c[N][],a[N];

 int b[N];

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 void swap(int &x,int &y)

 {

     int t=x;x=y;y=t;

 }

 int main()

 {

     //freopen("1.in","r",stdin);

 //    freopen("1.out","w",stdout);

     ll n;

     int q;

     scanf("%lld%d",&n,&q);

     while(q--)

     {

         ll x,y;

         scanf("%lld%lld",&x,&y);

         ll s1=n%;

         ll s2=x%;

         ll s3=y%;

         ll ans;

         if(s1&&s2&&s3) ans=(x-)/*n+(y+)/;

         if(s1&&s2&&s3==) ans=(n*n+)/+x/*n+y/;

         if(s1&&s2==&&s3) ans=(n*n+)/+x/*n+y/-n/;

         if(s1&&s2==&&s3==) ans=x/*n+y/-n/;

         if(s1==&&s2&&s3) ans=(x-)/*n+(y+)/;

         if(s1==&&s2&&s3==) ans=(n*n+)/+x/*n+y/;

         if(s1==&&s2==&&s3) ans=(n*n+)/+x/*n+y/-n/+;

         if(s1+s2+s3==) ans=x/*n+y/-n/;

         printf("%lld\n",ans);

     }

     return ;

 }