====== سوال ۱۹ ======

در هر خانه‌ی یک جدول $n\times n$، یک عدد صحیح با قدر مطلق کم‌تر از ۱۰۰۰ نوشته شده است. در هر $Query$، یک مستطیل داده می‌شود و برنامه‌ی شما باید عدد مربوط به آن را حساب کند. مستطیل با خانه‌ی بالا و سمت چپش و خانه‌ی پایین و سمت راستش مشخص می‌شود. به عبارت دیگر، اگر $a_{ij}$ خانه‌ی ردیف $i$ ام و ستون $j$ ام جدول باشد (که $a_{11}$ خانه‌ی بالا و سمت چپ جدول است)، مستطیل با $i_1$، $j_1$، $i_2$ و $j_2$ مشخص می‌شود و شامل تمام $a_{ij}$ هایی است که $i_1\leq i \leq i_2$ و $j_1 \leq j \leq j_2$. تعداد ستون‌های مستطیل $(j_2-j_1+1)$ عددی زوج می‌باشد. عدد مستطیل عبارت است از جمع عددهای ستون‌های $j_1$، $j_1+2$، $j_1+4$، ...، $j_2-1$ منهای جمع عددهای ستون‌های $j_1+1$، $j_1+3$، $j_1+5$،...، $j_2$ در مستطیل.

===== ورودی =====

در سطر اول فایل ورودی دو عدد $n$ و $k$ آمده‌اند، که $k$ تعداد $Query$ ها می‌باشد. سپس جدول نوشته شده است. ($n$ و $k$ به ترتیب از ۱۰۰۰ و $10^6$ بیش‌تر نیستند.)

سپس در $k$ خط، در هر خط اعداد $i_1$، $j_1$، $i_2$ و $j_2$ به ترتیب نوشته شده‌اند.

===== خروجی =====

در خروجی $k$ خط بنویسید، به طوری که در خط $i$ ام عدد مستطیل $i$ ام ورودی باشد.

===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|4 2 \\ 12 -7 3 5 \\ 1 2 0 -2 \\ 0 30 17 10 \\ 7 3 9 4 \\ 1 1 4 4 \\ 2 2 3 3|4 \\ 15|

</WRAP>
  * [[سوال ۲۰|سوال بعد]]
  * [[سوال ۱۸|سوال قبل]]