#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=998244353;
const int N=1200103;
ll f[N],a[N],pw[N];
ll p,q;
ll iv(ll x){return x==1?1:(p-p/x)*iv(p%x)%p;}
void solve(){
    cin>>p>>q;
    for(int i=pw[0]=1;i<=32;i++)pw[i]=pw[i-1]*2;
    while(q--) {
        ll a,b,c,d;
        cin>>a>>b>>c>>d;
        if((a+b)%p!=(c+d)%p){
            cout<<-1<<'\n';
        }else {
            //a t-a
            ll t=(a+b)%p;
            int ans=-1;
            for(int i=0;i<=32;i++) {
                //a=1 t=3 d=4
                //2*(1+4)
                if(iv(t)*(pw[i]*a%p+d)%p<=pw[i]&&iv(t)*(pw[i]*a%p+d)%p>=1) {
                    ans=i;
                    break;
                }
            }
            cout<<ans<<'\n';
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)solve();

}