#include <bits/stdc++.h>
#define pb push_back
using namespace std;
using ll = long long;
using PII = pair <int, int>;
const ll INF = 1e18;
const int N = 1e5 + 5;
ll n, m, ans = INF;
vector <int> divs;
ll dp[N];
void add(int num) {
if (num == n) return;
divs.pb(num);
ll len = n / num;
dp[num] = (len * len + 1) / 2 * num * num;
}
int getCnt(int pos, int len) {
int full = pos - (pos % len);
int ret = (full / len + 1) / 2 * len;
if ((full / len) % 2 == 0) ret += pos - full;
return ret;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cin >> n >> m;
for (int i = 1; i * i <= n; i++) {
if (n % i != 0) continue;
add(i);
if (i * i != n) add(n / i);
}
for (int i = 0; i < m; i++) {
int a1, b1, a2, b2; cin >> a1 >> b1 >> a2 >> b2;
for (auto& num : divs) {
int black, white, Black, White;
black = getCnt(a2, num) - getCnt(a1-1, num);
white = a2 - a1 + 1 - black;
Black = getCnt(b2, num) - getCnt(b1-1, num);
White = b2 - b1 + 1 - Black;
ll cur = black - white, cur1 = -cur;
dp[num] -= cur * Black + cur1 * White;
// cout << a1 << ' ' << b1 << ' ' << num << " : " << cur * Black + cur1 * White << '\n';
}
}
for (auto& num : divs) {
// cout << num << ": " << dp[num] << '\n';
ans = min(ans, min(dp[num], n * n - dp[num]));
}
cout << ans << '\n';
}
