#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i,n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pip pair<int, pii>
#define ppi pair<pii, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
const ll inf = 1ll<<60;
const int iinf=2147483647;
const ll mod = 1e9+7;
const ll maxn=5005;
const ll maxm=5e4+5;
const double PI=acos(-1);
ll pw(ll x, ll p, ll m=mod){
if (p < 0) return 0;
ll ret=1;
while (p>0){
if (p&1){
ret*=x;
ret%=m;
}
x*=x;
x%=m;
p>>=1;
}
return ret;
}
ll inv(ll a, ll m=mod){
return pw(a,m-2,m);
}
int n, q;
int pfp(int c3, int c2, int c1, int c0, int b){ // 1 to b
if (b == 0) return 0;
int ret = b*c0%mod;
ret += b*(b+1)%mod*inv(2)%mod*c1%mod;
ret %= mod;
ret += b*(b+1)%mod*(2*b+1)%mod*inv(6)%mod*c2%mod;
ret %= mod;
ret += SQ(b*(b+1)%mod*inv(2)%mod)%mod*c3%mod;
ret = (ret%mod+mod)%mod;
return ret;
}
int Q1(int x, int y){
if (x <= 0 || y <= 0) return 0;
int m = max(x, y);
// 1
int ret = x*(y*(y+1)%mod*inv(2)%mod)%mod - y*(x*(x+1)%mod*inv(2)%mod)%mod;
ret = (ret%mod+mod)%mod;
// 2
int b = min(x, y);
if (b < m){
ret += b*(pfp(0, 4, -2, 1, m)-pfp(0, 4, -2, 1, b))%mod;
ret %= mod;
}
ret = (ret%mod+mod)%mod;
// 3
ret += pfp(8, -8, 4, -1, b);
ret = (ret%mod+mod)%mod;
return ret;
}
int Q2(int x, int y){
if (x <= 0 || y <= 0) return 0;
int m = max(x, y);
// 1
int ret = y*(x*(x+1)%mod*inv(2)%mod)%mod - x*(y*(y+1)%mod*inv(2)%mod)%mod;
ret = (ret%mod+mod)%mod;
// 2
int b = min(x, y);
if (b < m){
ret += b*(pfp(0, 4, 0, 1, m)-pfp(0, 4, 0, 1, b))%mod;
ret %= mod;
}
ret = (ret%mod+mod)%mod;
// 3
ret += pfp(8, -4, 2, -1, b);
ret = (ret%mod+mod)%mod;
return ret;
}
int Q3(int x, int y){
if (x <= 0 || y <= 0) return 0;
int m = max(x, y);
// 1
int ret = x*(y*(y+1)%mod*inv(2)%mod)%mod - y*(x*(x+1)%mod*inv(2)%mod)%mod;
ret = (ret%mod+mod)%mod;
// 2
int b = min(x, y);
if (b < m){
ret += b*(pfp(0, 4, 2, 1, m)-pfp(0, 4, 2, 1, b))%mod;
ret %= mod;
}
ret = (ret%mod+mod)%mod;
// 3
ret += pfp(8, 0, 0, -1, b);
ret = (ret%mod+mod)%mod;
return ret;
}
int Q4(int x, int y){
if (x <= 0 || y <= 0) return 0;
int m = max(x-1, y);
int ret = y*(x*(x+1)%mod*inv(2)%mod)%mod - x*(y*(y+1)%mod*inv(2)%mod)%mod;
ret = (ret%mod + mod)%mod;
int b = min(x-1, y);
if (x-1 < y){
ret += x*(pfp(0, 4, 4, 1, m)-pfp(0, 4, 4, 1, x-1))%mod;
ret %= mod;
}
if (x-1 > y){
ret += y*(pfp(0, 4, 4, 1, m)-pfp(0, 4, 4, 1, y))%mod;
ret %= mod;
}
ret = (ret%mod+mod)%mod;
ret += pfp(8, 8, 2, 0, b);
ret = (ret%mod+mod)%mod;
return ret;
}
int L1(int x){
if (x <= 0) return 0;
return pfp(0, 4, -3, 1, x);
}
int L2(int x){
if (x <= 0) return 0;
return pfp(0, 4, -1, 1, x);
}
int L3(int x){
if (x <= 0) return 0;
return pfp(0, 4, 1, 1, x);
}
int L4(int x){
if (x <= 0) return 0;
return pfp(0, 4, 3, 1, x);
}
signed main(){
// IOS();
cin>>n>>q;
while(q--){
int xl, yl, xr, yr; cin>>xl>>yl>>xr>>yr;
int sm = 0;
if (xr >= 1 && yr >= 1){
sm += Q1(xr, yr)-Q1(max(0ll, xl-1), yr)-Q1(xr, max(0ll, yl-1))+Q1(max(0ll, xl-1), max(0ll, yl-1));
sm %= mod;
}
if (xl <= -1 && yr >= 1){
sm += Q2(-xl, yr)-Q2(max(0ll, -xr-1), yr)-Q2(-xl, max(0ll, yl-1))+Q2(max(0ll, -xr-1), max(0ll, yl-1));
sm %= mod;
}
if (xl <= -1 && yl <= -1){
sm += Q3(-xl, -yl)-Q3(max(0ll, -xr-1), -yl)-Q3(-xl, max(0ll, -yr-1))+Q3(max(0ll, -xr-1), max(0ll, -yr-1));
sm %= mod;
}
if (xr >= 1 && yl <= -1){
sm += Q4(xr, -yl)-Q4(max(0ll, xl-1), -yl)-Q4(xr, max(0ll, -yr-1))+Q4(max(0ll, xl-1), max(0ll, -yr-1));
sm %= mod;
}
sm = (sm%mod + mod)%mod;
if (yl <= 0 && yr >= 0){
sm += L1(max(xr, 0ll))-L1(max(xl-1, 0ll));
sm += L3(max(-xl, 0ll))-L3(max(-xr-1, 0ll));
}
if (xl <= 0 && xr >= 0){
sm += L2(max(yr, 0ll))-L2(max(yl-1, 0ll));
sm += L4(max(-yl, 0ll))-L4(max(-yr-1, 0ll));
}
if (xl <= 0 && xr >= 0 && yl <= 0 && yr >= 0){
sm++;
}
sm = (sm%mod + mod)%mod;
cout<<sm<<endl;
}
}
/*
69 10
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 1
1 1 2 2
1 1 2 3
1 1 3 1
1 1 3 2
1 1 3 3
1 1 4 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
588 KB |
Output is correct |
