// ~ Be Name Khoda ~ //
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
ll tagh2, tagh6;
inline ll max(ll a, int b){
return max(a, ll(b));
}
inline ll min(ll a, int b){
return min(a, ll(b));
}
inline ll pw(ll a, ll b){
ll ret = 1; a %= mod;
for(; b; b >>= 1, a = a * a % mod)
if(b&1) ret = ret * a % mod;
return ret;
}
// ----------------------SGIMA----------------------
inline ll sigmai(ll n){
n %= mod;
return (n * (n + 1) % mod) * tagh2 % mod;
}
inline ll sigmai2(ll n){
n %= mod;
return ((n * (n + 1) % mod) * ((2 * n + 1) % mod) % mod) * tagh6 % mod;
}
inline ll sigmai3(ll n){
n %= mod;
ll ans = (n * (n + 1) % mod) * tagh2 % mod;
return ans * ans % mod;
}
// ----------------------MORABA----------------------
inline ll moraba1(ll n){
return (2 * mod + (8 * sigmai3(n) % mod) - (8 * sigmai2(n) % mod) + (4 * sigmai(n) % mod) - (n % mod)) % mod;
}
inline ll moraba2(ll n){
return (2 * mod + (8 * sigmai3(n) % mod) - (12 * sigmai2(n) % mod) + (8 * sigmai(n) % mod) - (2 * n % mod)) % mod;
}
inline ll moraba3(ll n){
return (2 * mod + (8 * sigmai3(n) % mod) - (16 * sigmai2(n) % mod) + (12 * sigmai(n) % mod) - (3 * n % mod)) % mod;
}
inline ll moraba4(ll n){
return (2 * mod + (8 * sigmai3(n) % mod) - (4 * sigmai2(n) % mod) + (2 * sigmai(n) % mod) - (n % mod)) % mod;
}
// ----------------------SUM KHAT----------------------
inline ll sumio11(ll n){
return (mod + (4 * sigmai2(n) % mod) - (3 * sigmai(n) % mod) + (2 * n % mod)) % mod;
}
inline ll sum1oi1(ll n){
return (mod + (4 * sigmai2(n) % mod) - sigmai(n)) % mod;
}
inline ll sumio02(ll n){
return (mod + (4 * sigmai2(n) % mod) - (3 * sigmai(n) % mod) + (n % mod)) % mod;
}
inline ll sum1oi2(ll n){
return (mod + (4 * sigmai2(n) % mod) - (5 * sigmai(n) % mod) + (3 * n % mod)) % mod;
}
inline ll sumio03(ll n){
return (mod + (4 * sigmai2(n) % mod) - (7 * sigmai(n) % mod) + (4 * n % mod)) % mod;
}
inline ll sum0oi3(ll n){
return (mod + (4 * sigmai2(n) % mod) - (5 * sigmai(n) % mod) + (2 * n % mod)) % mod;
}
inline ll sumio14(ll n){
return (mod + (4 * sigmai2(n) % mod) + (sigmai(n) % mod)) % mod;
}
inline ll sum1oi4(ll n){
return (mod + (4 * sigmai2(n) % mod) - (sigmai(n) % mod) + (2 * n % mod)) % mod;
}
inline ll sum0oi5(ll n){
return (mod + (4 * sigmai2(n) % mod) - (sigmai(n) % mod) + (n % mod)) % mod;
}
// ----------------------GET----------------------
inline ll get1(ll x2, ll y2){
ll ans = moraba1(min(x2, y2));
if(y2 < x2){
ll A = (sumio11(x2) - sumio11(y2) + mod) % mod;
ll d = x2 - y2; d %= mod;
ans += (y2 * ((2 * A + ((y2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod;
ans %= mod;
}
if(y2 > x2){
ll A = (sum1oi1(y2) - sum1oi1(x2) + mod) % mod;
ll d = (x2 % mod) - (y2 % mod) + mod; d %= mod;
ans += (x2 * ((2 * A + ((x2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod;
ans %= mod;
}
return ans;
}
inline ll get2(ll x2, ll y2){
y2 *= -1; y2++;
ll ans = moraba2(min(x2, y2));
if(y2 < x2){
ll A = (sumio02(x2) - sumio02(y2) + mod) % mod;
ll d = mod + (y2 % mod) - (x2 % mod); d %= mod;
ans += (y2 * ((2 * A + ((y2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod;
ans %= mod;
}
if(y2 > x2){
ll A = (sum1oi2(y2) - sum1oi2(x2) + mod) % mod;
ll d = (y2 % mod) - (x2 % mod) + mod; d %= mod;
ans += (x2 * ((2 * A + ((x2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod;
ans %= mod;
}
return ans;
}
inline ll get3(ll x2, ll y2){
y2 *= -1; y2++; x2 *= -1; x2++;
ll ans = moraba3(min(x2, y2));
if(y2 < x2){
ll A = (sumio03(x2) - sumio03(y2) + mod) % mod;
ll d = mod + (x2 % mod) - (y2 % mod); d %= mod;
ans += (y2 * ((2 * A + ((y2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod;
ans %= mod;
}
if(y2 > x2){
ll A = (sum0oi3(y2) - sum0oi3(x2) + mod) % mod;
ll d = (x2 % mod) - (y2 % mod) + mod; d %= mod;
ans += (x2 * ((2 * A + ((x2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod;
ans %= mod;
}
return ans;
}
inline ll get4(ll x2, ll y2){
x2 *= -1;
ll ans = moraba4(min(x2, y2));
if(y2 < x2){
ll A = (sumio14(x2) - sumio14(y2) + mod) % mod;
ll d = mod + (y2 % mod) - (x2 % mod); d %= mod;
ans += (y2 * ((2 * A + ((y2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod;
ans %= mod;
}
if(y2 > x2){
ll A = (sum1oi4(y2) - sum1oi4(x2) + mod) % mod;
ll d = (y2 % mod) - (x2 % mod) + mod; d %= mod;
ans += (x2 * ((2 * A + ((x2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod;
ans %= mod;
}
return ans;
}
// ----------------------MANTAGHE----------------------
inline ll mantaghe1(ll x1, ll y1, ll x2, ll y2){
if(x2 < 1)
return 0;
if(y2 < 1)
return 0;
x1 = max(x1, 1); y1 = max(y1, 1);
ll ans = get1(x2, y2);
if(x1 > 1)
ans = (ans + mod - get1(x1 - 1, y2)) % mod;
if(y1 > 1)
ans = (ans + mod - get1(x2, y1 - 1)) % mod;
if(x1 > 1 && y1 > 1)
ans = (ans + get1(x1 - 1, y1 - 1)) % mod;
return ans;
}
inline ll mantaghe2(ll x1, ll y1, ll x2, ll y2){
if(x2 < 1)
return 0;
if(y1 > 0)
return 0;
x1 = max(x1, 1); y2 = min(y2, 0);
swap(y1, y2);
ll ans = get2(x2, y2);
if(x1 > 1)
ans = (ans + mod - get2(x1 - 1, y2)) % mod;
if(y1 < 0)
ans = (ans + mod - get2(x2, y1 + 1)) % mod;
if(x1 > 1 && y1 < 0)
ans = (ans + get2(x1 - 1, y1 + 1)) % mod;
return ans;
}
inline ll mantaghe3(ll x1, ll y1, ll x2, ll y2){
if(x1 > 0)
return 0;
if(y1 > 0)
return 0;
x2 = min(x2, 0); y2 = min(y2, 0);
swap(y1, y2); swap(x1, x2);
ll ans = get3(x2, y2);
if(x1 < 0)
ans = (ans + mod - get3(x1 + 1, y2)) % mod;
if(y1 < 0)
ans = (ans + mod - get3(x2, y1 + 1)) % mod;
if(x1 < 0 && y1 < 0)
ans = (ans + get3(x1 + 1, y1 + 1)) % mod;
return ans;
}
inline ll mantaghe4(ll x1, ll y1, ll x2, ll y2){
if(x1 > -1)
return 0;
if(y2 < 1)
return 0;
x2 = min(x2, -1); y1 = max(y1, 1);
swap(x1, x2);
ll ans = get4(x2, y2);
if(x1 < -1)
ans = (ans + mod - get4(x1 + 1, y2)) % mod;
if(y1 > 1)
ans = (ans + mod - get4(x2, y1 - 1)) % mod;
if(x1 < -1 && y1 > 1)
ans = (ans + get4(x1 + 1, y1 - 1)) % mod;
return ans;
}
inline ll mantaghe5(ll x1, ll y1, ll x2, ll y2){
if(x1 > 0 || x2 < 0)
return 0;
if(y2 < 1)
return 0;
x1 = x2 = 0; y1 = max(y1, 1);
return (sum0oi5(y2) - (y1 == 1 ? 0 : sum0oi5(y1 - 1)) + mod) % mod;
}
// ----------------------MAIN----------------------
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
tagh2 = pw(2, mod - 2);
tagh6 = pw(6, mod - 2);
ll n; int tt; cin >> n >> tt;
while(tt--){
ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
ll ans = mantaghe1(x1, y1, x2, y2);
ans = (ans + mantaghe2(x1, y1, x2, y2)) % mod;
ans = (ans + mantaghe3(x1, y1, x2, y2)) % mod;
ans = (ans + mantaghe4(x1, y1, x2, y2)) % mod;
ans = (ans + mantaghe5(x1, y1, x2, y2)) % mod;
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
