- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
جدولی \( (2 \times n+1) \times (2 \times n+1)\) به این صورت ساخته شدهاست که ابتدا عدد ۱ را در مرکز جدول مینویسیم، سپس عدد ۲ را در خانهی سمت راست عدد ۱ مینویسیم و باقی اعداد را با شروع از عدد ۳ در جهت عکس عقربههای ساعت و به صورت مارپیج و کنار هم در جدول مینویسیم.
شما باید به ازای هر یک از \(q\) تا درخواستی که یک زیر مستطیل از این جدول را نمایش میدهند، باقیماندهی مجموع اعداد داخل این زیر مستطیل را بر \(10 ^ 9 + 7\) در خروجی چاپ کنید.
به عنوان مثال در جدول زیر عدد \(n\) برابر ۲ و مجموع اعداد داخل زیرمستطیل طوسی رنگ برابر ۷۴ است.
ورودی
در خط اول ورودی ۲ عدد \(n\) و \(q\) آمده است که به ترتیب اندازهی جدول و تعداد درخواستها را مشخص میکنند.
در \(q\) خط بعدی در هر خط به ترتیب ۴ عدد \(x_1\) و \(y_1\) و \(x_2\) و \(y_2\) آمده است که مختصات ۲ خانه از جدول را نشان میدهند و این ۲ خانهي مشخص شده، ۲ خانه از ۲ گوشهی روبهروی هم زیر مستطیلی است که شما باید مجموع اعداد داخل آن را حساب کنید.
\[1 \le q \le 100\] \[1 \le n \le 100\ 000\] \[-n \le x_1 \le x_2 \le n\] \[-n \le y_1 \le y_2 \le n\]
خروجی
در خط \(i\)ام خروجی باقیماندهی مجموع اعداد داخل زیرمستطیل مشخص شده در درخواست \(i\)ام را بر \(10 ^ 9 +7\) چاپ کنید.
مثال
ورودی نمونه ۱
2 3
0 -2 1 1
-1 0 1 0
1 2 1 2
خروجی نمونه ۱
74
9
14