#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
int n, q;
ll quickPow(ll x, ll y)
{
ll ans = 1;
while(y) {
if(y & 1) {
ans *= x;
ans %= MOD;
}
y >>= 1;
x *= x;
x %= MOD;
}
return ans;
}
ll add(ll x, ll y)
{
return (((x+y)%MOD)+MOD)%MOD;
}
ll sub(ll x, ll y)
{
return add(x, -y);
}
ll mul(ll x, ll y)
{
return x*y%MOD;
}
ll dvd(ll x, ll y)
{
return x*quickPow(y,MOD-2)%MOD;
}
ll get1(ll x1, ll y1, ll x2, ll y2, ll base, bool swapNM)
{
if(x2 < x1 || y2 < y1) return 0LL;
ll n = y2-y1+1;
ll m = x2-x1+1;
ll ans = 0;
if(swapNM) swap(n, m);
// BASE*n*m
ans = add(ans, mul(mul(n, m), base));
// squares
ll nn = min(n, m);
// n*(2*n-1)*(2*n+1) / 3
ans = add(ans, dvd(mul(nn, mul(sub(mul(2, nn), 1), add(mul(2, nn), 1))), 3));
// 8 * ( n^2*(n-1)*(n+1) / 4 )
ans = add(ans, mul(8, dvd(mul(mul(nn, nn), mul(sub(nn, 1), add(nn, 1))), 4)));
// rectangles
if(n > m) {
// m * ( n*(3*n-1) / 2 - m*(3*m-1) / 2) - (n-m)*m*(m-1)/2
ans = add(ans,
mul(m,
sub(dvd(mul(n, sub(mul(3, n), 1)), 2),
dvd(mul(m, sub(mul(3, m), 1)), 2))
));
ans = sub(ans, dvd(mul(sub(n, m), mul(m, sub(m, 1))), 2));
// 8 * m * ( n*(n-1)*(n+1) / 6 - m*(m-1)*(m+1) / 6 )
ans = add(ans,
mul(mul(8, m),
sub(dvd(mul(n, mul(sub(n, 1), add(n, 1))), 6),
dvd(mul(m, mul(sub(m, 1), add(m, 1))), 6))));
}
else if(m > n) {
// n * ( m*(m+1) / 2 - n*(n+1) / 2) + (m-n)*n*(n-1)/2
ans = add(ans,
mul(n,
sub(dvd(mul(m, add(m, 1)), 2),
dvd(mul(n, add(n, 1)), 2))
));
ans = add(ans, dvd(mul(sub(m, n), mul(n, sub(n, 1))), 2));
// 8 * n * ( m*(m-1)*(m+1) / 6 - n*(n-1)*(n+1) / 6 )
ans = add(ans,
mul(mul(8, n),
sub(dvd(mul(m, mul(sub(m, 1), add(m, 1))), 6),
dvd(mul(n, mul(sub(n, 1), add(n, 1))), 6))));
}
return ans;
}
ll get2(ll x1, ll y1, ll x2, ll y2, ll base)
{
if(x2 < x1 || y2 < y1) return 0LL;
ll n = y2-y1+1;
ll m = x2-x1+1;
ll ans = 0;
if(n < m) swap(n, m);
// square
// (m*(m-1)*(4*m+1)) / 6
ans = add(ans, dvd(mul(m, mul(sub(m, 1), add(mul(4, m), 1))), 6LL));
// rectangle
if(n != m) {
// m * ( n*(n-1)/2 - m*(m-1)/2 )
ans = add(ans, mul(m,
sub(dvd(mul(n, sub(n, 1)), 2),
dvd(mul(m, sub(m, 1)), 2))));
}
// ans *= base;
ans = mul(ans, base);
return ans;
}
ll get3(ll m, ll base, ll init)
{
if(m <= 0) return 0LL;
ll ans = 0;
// init * m
ans = add(ans, mul(init, m));
// base * ( m*(m-1) / 2 )
ans = add(ans, mul(base, dvd(mul(m, sub(m, 1)), 2)));
// 8 * ( m*(m-1)*(m-2) / 6 )
ans = add(ans, mul(8, dvd(mul(m, mul(sub(m, 2), sub(m, 1))), 6)));
return ans;
}
int main()
{
cin >> n >> q;
for(int k = 0; k < q; k++) {
ll x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
ll ans = 0;
// corner 3
if(x2 >= 1 && y2 >= 1) {
if(x1 <= 1 && y1 <= 1) {
//cerr << get1(max(x1, 1LL), max(y1, 1LL), x2, y2, 2, false) << "\n";
ans = add(ans, get1(1, 1, x2, y2, 2, false));
}
else if(x1 > 1 && y1 <= 1) {
ans = add(ans, get1(1, 1, x2, y2, 2, false));
ans = sub(ans, get1(1, 1, x1-1, y2, 2, false));
}
else if(x1 <= 1 && y1 > 1) {
ans = add(ans, get1(1, 1, x2, y2, 2, false));
ans = sub(ans, get1(1, 1, x2, y1-1, 2, false));
}
else {
ans = add(ans, get1(1, 1, x2, y2, 2, false));
ans = add(ans, get1(1, 1, x1-1, y1-1, 2, false));
ans = sub(ans, get1(1, 1, x1-1, y2, 2, false));
ans = sub(ans, get1(1, 1, x2, y1-1, 2, false));
}
}
// corner 5
if(x1 <= -1 && y2 >= 1) {
if(x2 >= -1 && y1 <= 1) {
//cerr << get1(x1, max(y1, 1LL), min(x2, -1LL), y2, 4, true) << "\n";
ans = add(ans, get1(x1, 1, -1, y2, 4, true));
//cerr << get2(x1, max(y1, 1LL), min(x2, -1LL), y2, 2) << "\n";
ans = add(ans, get2(x1, 1, -1, y2, 2));
}
else if(x2 < -1 && y1 <= 1) {
ans = add(ans, get1(x1, 1, -1, y2, 4, true));
ans = sub(ans, get1(x2+1, 1, -1, y2, 4, true));
ans = add(ans, get2(x1, 1, -1, y2, 2));
ans = sub(ans, get2(x2+1, 1, -1, y2, 2));
}
else if(x2 >= -1 && y1 > 1) {
ans = add(ans, get1(x1, 1, -1, y2, 4, true));
ans = sub(ans, get1(x1, 1, -1, y1-1, 4, true));
ans = add(ans, get2(x1, 1, -1, y2, 2));
ans = sub(ans, get2(x1, 1, -1, y1-1, 2));
}
else {
ans = add(ans, get1(x1, 1, -1, y2, 4, true));
ans = add(ans, get1(x2+1, 1, -1, y1-1, 4, true));
ans = sub(ans, get1(x2+1, 1, -1, y2, 4, true));
ans = sub(ans, get1(x1, 1, -1, y1-1, 4, true));
ans = add(ans, get2(x1, 1, -1, y2, 2));
ans = add(ans, get2(x2+1, 1, -1, y1-1, 2));
ans = sub(ans, get2(x2+1, 1, -1, y2, 2));
ans = sub(ans, get2(x1, 1, -1, y1-1, 2));
}
}
// corner 7
if(x1 <= -1 && y1 <= -1) {
if(x2 >= -1 && y2 >= -1) {
//cerr << get1(x1, y1, min(x2, -1LL), min(y2, -1LL), 6, false) << "\n";
ans = add(ans, get1(x1, y1, -1, -1, 6, false));
//cerr << get2(x1, y1, min(x2, -1LL), min(y2, -1LL), 4) << "\n";
ans = add(ans, get2(x1, y1, -1, -1, 4));
}
else if(x2 < -1 && y2 >= -1) {
ans = add(ans, get1(x1, y1, -1, -1, 6, false));
ans = sub(ans, get1(x2+1, y1, -1, -1, 6, false));
ans = add(ans, get2(x1, y1, -1, -1, 4));
ans = sub(ans, get2(x2+1, y1, -1, -1, 4));
}
else if(x2 >= -1 && y2 < -1) {
ans = add(ans, get1(x1, y1, -1, -1, 6, false));
ans = sub(ans, get1(x1, y2+1, -1, -1, 6, false));
ans = add(ans, get2(x1, y1, -1, -1, 4));
ans = sub(ans, get2(x1, y2+1, -1, -1, 4));
}
else {
ans = add(ans, get1(x1, y1, -1, -1, 6, false));
ans = add(ans, get1(x2+1, y2+1, -1, -1, 6, false));
ans = sub(ans, get1(x2+1, y1, -1, -1, 6, false));
ans = sub(ans, get1(x1, y2+1, -1, -1, 6, false));
ans = add(ans, get2(x1, y1, -1, -1, 4));
ans = add(ans, get2(x2+1, y2+1, -1, -1, 4));
ans = sub(ans, get2(x2+1, y1, -1, -1, 4));
ans = sub(ans, get2(x1, y2+1, -1, -1, 4));
}
}
// corner 10
if(x2 >= 2 && y1 <= -1) {
if(x1 <= 2 && y2 >= -1) {
//cerr << get1(max(x1, 2LL), y1, x2, min(y2, -1LL), 9, true) << "\n";
ans = add(ans, get1(2, y1, x2, -1, 9, true));
//cerr << get2(max(x1, 2LL), y1, x2, min(y2, -1LL), 6) << "\n";
ans = add(ans, get2(2, y1, x2, -1, 6));
}
else if(x1 > 2 && y2 >= -1) {
ans = add(ans, get1(2, y1, x2, -1, 9, true));
ans = sub(ans, get1(2, y1, x1-1, -1, 9, true));
ans = add(ans, get2(2, y1, x2, -1, 6));
ans = sub(ans, get2(2, y1, x1-1, -1, 6));
}
else if(x1 <= 2 && y2 < -1) {
ans = add(ans, get1(2, y1, x2, -1, 9, true));
ans = sub(ans, get1(2, y2+1, x2, -1, 9, true));
ans = add(ans, get2(2, y1, x2, -1, 6));
ans = sub(ans, get2(2, y2+1, x2, -1, 6));
}
else {
ans = add(ans, get1(2, y1, x2, -1, 9, true));
ans = add(ans, get1(2, y2+1, x1-1, -1, 9, true));
ans = sub(ans, get1(2, y1, x1-1, -1, 9, true));
ans = sub(ans, get1(2, y2+1, x2, -1, 9, true));
ans = add(ans, get2(2, y1, x2, -1, 6));
ans = add(ans, get2(2, y2+1, x1-1, -1, 6));
ans = sub(ans, get2(2, y1, x1-1, -1, 6));
ans = sub(ans, get2(2, y2+1, x2, -1, 6));
}
}
// 4 and up
if(x1 <= 0 && 0 <= x2) {
//cerr << sub(get3(y2, 11, 4), get3(y1-1, 11, 4)) << "\n";
ans = add(ans, sub(get3(y2, 11, 4), get3(y1-1, 11, 4)));
}
// 6 and left
if(y1 <= 0 && 0 <= y2) {
//cerr << sub(get3(-x1, 13, 6), get3((-x2)-1, 13, 6)) << "\n";
ans = add(ans, sub(get3(-x1, 13, 6), get3((-x2)-1, 13, 6)));
}
// 8 and down
if(x1 <= 0 && 0 <= x2) {
//cerr << sub(get3(-y1, 15, 8), get3((-y2)-1, 15, 8)) << "\n";
ans = add(ans, sub(get3(-y1, 15, 8), get3((-y2)-1, 15, 8)));
}
// 9 and down
if(x1 <= 1 && 1 <= x2) {
//cerr << sub(get3(-y1, 15, 9), get3((-y2)-1, 15, 9)) << "\n";
ans = add(ans, sub(get3(-y1, 15, 9), get3((-y2)-1, 15, 9)));
}
// 2 and right
if(y1 <= 0 && 0 <= y2) {
//cerr << sub(get3(x2, 9, 2), get3(x1-1, 9, 2)) << "\n";
ans = add(ans, sub(get3(x2, 9, 2), get3(x1-1, 9, 2)));
}
// 1
if(x1 <= 0 && 0 <= x2 && y1 <= 0 && 0 <= y2) {
//cerr << "1\n";
ans = add(ans, 1);
}
cout << ans << "\n";
cerr << "-----------\n";
}
return 0;
}
/*
10000 5
-69 69 420 420
-69 420 69 420
69 0 420 69
-69 0 420 69
-420 0 420 69
out: 498496110, 98020159, 892399318, 984401158, 897862664 ok
10000 1
-5 -2 -3 3
out: 1281 ok
10000 3
2 2 3 3
2 1 3 3
1 2 3 3
out: 106, 147, 153 ok
10000 3
-3 2 -2 3
-3 1 -2 3
-3 2 -1 3
out: 128, 185, 179 ok
10000 3
-3 -3 -2 -2
-3 -3 -2 -1
-3 -3 -1 -2
out: 150, 211, 217 ok
10000 3
3 -3 4 -2
3 -3 4 -1
2 -3 4 -2
out: 176, 255, 249 ok
10000 5
-3 -3 -1 -1
-3 -1 -1 -1
-1 -3 -1 -1
-3 -5 -1 -1
-5 -3 -1 -1
out: 285, 68, 74, 852, 822 ok
10000 5
-3 -3 -1 0
-3 -1 -1 0
-1 -3 -1 0
-3 -5 -1 0
-5 -3 -1 0
out: 350, 133, 80, 917, 1062 ok
10000 2
-5 0 -3 0
-3 0 -1 0
out: 215, 65 ok
10000 1
-2 -2 2 2
out: 325 ok
10000 1
-10 -10 10 10
out: 97461 ok
10000 2
1 1 3 1
1 1 4 1
out: 44, 98 ok
10000 2
1 1 1 3
1 1 1 4
out: 50, 110 ok
10000 2
1 1 3 3
1 1 4 4
out: 197, 596 ok
10000 2
1 1 2 6
1 1 6 2
out: 690, 642 ok
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
2 ms |
292 KB |
Output is correct |
