+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **به محدودیت عدد $n$ در این سوال دقت کنید.** جدولی $ (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 ```

حل سؤال در بانک سؤالات