// Muallif: Mansuraliyev Husanboy Murotali o'g'li >> NamPS
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const double PI=3.1415926535897932384626433832795;
// 0-9 >> 48-57; A-Z>>65-90 and a-z>>97-122 respectively;
int main(){
ios;
ll n,q; cin>>n>>q;
vector<ll> a;
a.push_back(1ll);
ll b=sqrt(n);
for(ll i=2;i<sqrt(n);i++){
if(n%i==0){
a.push_back(i); a.push_back(n/i);
}
}
if(b*b==n){
a.push_back(b);
}
vector<ll> ans,ans2;
ll sz=a.size();
for(auto u:a){
ll x=n/u;
if(x%2ll==0){
ans.push_back((n*n)/2ll);
ans2.push_back((n*n)/2ll);
}else{
ll k=(n*n-u*u)/2ll+u*u;
ans.push_back(k);
ans2.push_back(n*n-k);
}
}
while(q--){
ll x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
for(int i=0;i<sz;i++){
ll u=a[i];
/*ll x=n/u;
ll black=0ll,white=0ll;
ll tx2=x2-x2%u,tx1=x1-(x1%u==0ll||x1%u==1ll?u:x1%u)+u+(x1%u==1ll||u==1ll?0ll:1ll),ty1=y1-(y1%u==0ll||y1%u==1ll?u:y1%u)+u+(y1%u==1||u==1ll?0ll:1ll),ty2=y2-y2%u;
//cout<<u<<": "<<tx1<<' '<<ty1<<' '<<tx2<<' '<<ty2<<endl;
if(tx1<=tx2&&ty1<=ty2){
}else{
}*/
ll x=(x1+u-1ll)/u,y=(y1+u-1ll)/u;
//cout<<u<<": "<<x<<' '<<y<<">> ";
if((x+y)%2==0){
ans[i]--; ans2[i]++;//cout<<ans[i]<<endl;
}else{
ans[i]++; ans2[i]--;//cout<<ans[i]<<endl;
}
}
}
ll mn=1e18;
for(int i=0;i<sz;i++){
//cout<<ans[i]<<' '<<ans2[i]<<endl;
mn=min(mn,min(ans[i],ans2[i]));
}
cout<<mn;
}
