#include <bits/stdc++.h>
#define d1(x) cout << #x << " : " << x << endl << flush
#define d2(x, y) cout << #x << " : " << x << " " << #y << " : " << y << endl << flush
#define d3(x, y, z) cout << #x << " : " << x << " " << #y << " : " << y << " " << #z << " : " << z << endl << flush
#define d4(x, y, z, a) cout << #x << " : " << x << " " << #y << " : " << y << " " << #z << " : " << z << " "<< #a << " : " << a << endl << flush
#define arr(x) array <ll, x>
#define ld long double
#define ll long long
#define int long long
#define pb push_back
#define endl '\n'
#define lc v << 1
#define rc v << 1 | 1
using namespace std;
const int INF = 1e9 + 24 + (34 / 10); // 34 ---> 35
const int MAXN = 2e5 + 24 + (34 / 10); // 34 ---> 35
const int MOD = 1e9 + 7;
int pw(int a, int b){
if(b == 0)
return 1;
int res = pw(a, b / 2);
res = (res * res) % MOD;
if(b & 1)
res = (res * a) % MOD;
return res;
}
int T1(int x, int y){
int res = y * (y + 1) / 2 % MOD;
res %= MOD;
if(x != 1)
res -= T1(1, x - 1);
res %= MOD;
res += MOD;
res %= MOD;
return res;
}
int T2(int x, int y){
int res = y * (y + 1) % MOD;
res *= (2 * y + 1) % MOD * pw(6, MOD - 2) % MOD;
if(x != 1)
res -= T2(1, x - 1);
res %= MOD;
res += MOD;
res %= MOD;
return res;
}
int T3(int x, int y){
int res = y * (y + 1) / 2 % MOD;
res %= MOD;
res *= res;
res %= MOD;
if(x != 1)
res -= T3(1, x - 1);
res %= MOD;
res += MOD;
res %= MOD;
return res;
}
int Hal1(int x1, int y1, int x2, int y2){
if(x1 > 1 || y1 > 1){
int ans = Hal1(1, 1, x2, y2);
if(x1 > 1)
ans -= Hal1(1, 1, x1 - 1, y2), ans %= MOD;
if(y1 > 1)
ans -= Hal1(1, 1, x2, y1 - 1), ans %= MOD;
if(x1 > 1 && y1 > 1)
ans += Hal1(1, 1, x1 - 1, y1 - 1), ans %= MOD;
return ans % MOD;
}
int X = min(x2, y2);
int res = 0;
// satrrr
if(y2 > x2){
int x = x2 + 1, y = y2;
int n = x2, m = y - x + 1;
// d4(x, y, n, m);
res -= n * (n - 1) / 2 % MOD * m % MOD;
res %= MOD;
res += n * 4 * T2(x, y) % MOD;
res %= MOD;
res -= n * T1(x, y);
res %= MOD;
}
// sotoooon
else if(y2 < x2){
int x = y2 + 1, y = x2;
int n = y2, m = y - x + 1;
res += n * (n - 1) / 2 % MOD * m % MOD;
res %= MOD;
res += 4 * n * T2(x, y) % MOD;
res %= MOD;
res -= 3 * n * T1(x, y) % MOD;
res %= MOD;
res += 2 * n * m % MOD;
res %= MOD;
}
res -= X % MOD;
res %= MOD;
res += 8 * T3(1, X) % MOD;
res %= MOD;
res -= 8 * T2(1, X) % MOD;
res %= MOD;
res += 4 * T1(1, X) % MOD;
res %= MOD;
res += MOD;
res %= MOD;
// d2(1, res);
return res;
}
int Hal2(int x1, int y1, int x2, int y2){
if(x1 < 0 || y1 > 1){
int ans = Hal2(0, 1, x2, y2);
if(x1 < 0)
ans -= Hal2(0, 1, -x1 - 1, y2), ans %= MOD;;
if(y1 > 1)
ans -= Hal2(0, 1, x2, y1 - 1), ans %= MOD;;
if(x1 < 0 && y1 > 1)
ans += Hal2(0, 1, -x1 - 1, y1 - 1), ans %= MOD;;
return ans % MOD;
}
int X = min(x2, y2);
int res = 0;
// satrrrrr
if(x2 < y2){
int x = x2 + 1, y = y2;
int n = x2 + 1, m = y - x + 1;
res += n * (n - 1) / 2 % MOD * m % MOD;
res %= MOD;
res += m * n % MOD;
res %= MOD;
res += 4 * n * T2(x, y) % MOD;
res %= MOD;
res -= n * T1(x, y);
res %= MOD;
}
else if(x2 > y2){
int x = y2 + 1, y = x2;
int n = y2, m = y - x + 1;
res += 4 * n * T2(x, y) % MOD;
res %= MOD;
res += n * T1(x, y) % MOD;
res %= MOD;
res -= n * (n - 1) / 2 % MOD * m % MOD;
res %= MOD;
}
res += 8 * T3(1, X) % MOD;
res %= MOD;
res += T1(1, X);
res %= MOD;
res += MOD;
res %= MOD;
// d2(2, res);
return res;
}
int Hal3(int x1, int y1, int x2, int y2){
// d4(x1, y1, x2, y2);
if(x1 < 0 || y1 < 0){
int ans = Hal3(0, 0, x2, y2);
if(x1 < 0){
// d1(1111111);
ans -= Hal3(0, 0, -x1 - 1, y2);
ans %= MOD;
}
if(y1 < 0){
// d1(2);
ans -= Hal3(0, 0, x2, -y1 - 1);
ans %= MOD;
}
if(x1 < 0 && y1 < 0){
// d1(3);
ans += Hal3(0, 0, -x1 - 1, -y1 - 1);
ans %= MOD;
}
return ans % MOD;
}
int X = min(x2, y2);
int res = 1;
if(x2 < y2){
int x = x2 + 1, y = y2;
int n = x2 + 1, m = y - x + 1;
res += 4 * n * T2(x, y) % MOD;
res %= MOD;
res += 3 * n * T1(x, y) % MOD;
res %= MOD;
res += n * m % MOD;
res %= MOD;
res -= n * (n - 1) / 2 % MOD * m % MOD;
res %= MOD;
}
else if(x2 > y2){
int x = y2 + 1, y = x2;
int n = y2 + 1, m = y - x + 1;
res += 4 * n * T2(x, y) % MOD;
res %= MOD;
res += n * T1(x, y) % MOD;
res %= MOD;
res += n * m % MOD;
res %= MOD;
res += n * (n - 1) / 2 % MOD * m % MOD;
res %= MOD;
}
res += X;
res %= MOD;
res += 8 * T3(1, X) % MOD;
res %= MOD;
res += 8 * T2(1, X) % MOD;
res %= MOD;
res += 4 * T1(1, X) % MOD;
res %= MOD;
res += MOD;
res %= MOD;
// d2(3, res);
return res;
}
int Hal4(int x1, int y1, int x2, int y2){
// d4(x1, y1, x2, y2);
if(x1 > 1 || y1 < 0){
int ans = Hal4(0, 1, x2, y2);
if(x1 > 1)
ans -= Hal4(0, 1, x1 - 1, y2), ans %= MOD;
if(y1 < 0)
ans -= Hal4(0, 1, x2, -y1 - 1), ans %= MOD;
if(x1 > 1 && y1 < 0)
ans += Hal4(0, 1, x1 - 1, -y1 - 1), ans %= MOD;
return ans % MOD;
}
int X = min(x2 - 1, y2);
int res = 2;
// satrrrr
if(x2 < y2 + 1){
int x = x2, y = y2;
int n = x2, m = y - x + 1;
// d4(x, y, n, m);
res += 4 * n * T2(x, y) % MOD;
res %= MOD;
res += 3 * n * T1(x, y) % MOD;
res %= MOD;
res += 2 * n * m % MOD;
res %= MOD;
res += n * (n - 1) / 2 % MOD * m % MOD;
res %= MOD;
// d1(res);
}
else if(x2 > y2 + 1){
int x = y2 + 2, y = x2;
int n = y2 + 1, m = y - x + 1;
res += 4 * n * T2(x, y) % MOD;
res %= MOD;
res -= 3 * n * T1(x, y) % MOD;
res %= MOD;
res += n * m % MOD;
res %= MOD;
res -= n * (n - 1) / 2 % MOD * m % MOD;
res %= MOD;
}
if(X > 0){
res += X * 2;
res %= MOD;
res += 8 * T3(1, X) % MOD;
res %= MOD;
res += 12 * T2(1, X) % MOD;
res %= MOD;
res += 8 * T1(1, X) % MOD;
res %= MOD;
}
res %= MOD;
res += MOD;
res %= MOD;
// d4(x1, y1, x2, y2);
// d2(4, res);
return res;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
while(q--){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int ans = 0;
int X1 = abs(x1);
int Y1 = abs(y1);
int X2 = abs(x2);
int Y2 = abs(y2);
// 1111
if(x2 > 0 && y2 > 0){
ans += Hal1(x1, y1, X2, Y2);
// d2(1, ans);
}
// 2222
if(x1 <= 0 && y2 > 0){
ans += Hal2(x2, y1, X1, Y2);
// d2(2, ans);
}
// 33333
if(x1 <= 0 && y1 <= 0){
ans += Hal3(x2, y2, X1, Y1);
// d2(3, ans);
}
// 4444
if(x2 > 0 && y1 <= 0){
ans += Hal4(x1, y2, X2, Y1);
// d2(4, ans);
}
ans %= MOD;
ans += MOD;
ans %= MOD;
cout << ans << endl;
}
}
// Ey To Bahane! :_)))
// -------------<3------------- //
/*
Magasan dor shirini:
1. MAXN
2. Input style
3. index or value? Masale In Ast!
4. MOD
*/
/*
1000000000 1
-1 0 -1 1
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |