در هر خانهی یک جدول n×n، یک عدد صحیح با قدر مطلق کمتر از ۱۰۰۰ نوشته شده است. در هر Query، یک مستطیل داده میشود و برنامهی شما باید عدد مربوط به آن را حساب کند. مستطیل با خانهی بالا و سمت چپش و خانهی پایین و سمت راستش مشخص میشود. به عبارت دیگر، اگر aij خانهی ردیف i ام و ستون j ام جدول باشد (که a11 خانهی بالا و سمت چپ جدول است)، مستطیل با i1، j1، i2 و j2 مشخص میشود و شامل تمام aij هایی است که i1≤i≤i2 و j1≤j≤j2. تعداد ستونهای مستطیل (j2−j1+1) عددی زوج میباشد. عدد مستطیل عبارت است از جمع عددهای ستونهای j1، j1+2، j1+4، …، j2−1 منهای جمع عددهای ستونهای j1+1، j1+3، j1+5،…، j2 در مستطیل.
در سطر اول فایل ورودی دو عدد n و k آمدهاند، که k تعداد Query ها میباشد. سپس جدول نوشته شده است. (n و k به ترتیب از ۱۰۰۰ و 106 بیشتر نیستند.)
سپس در k خط، در هر خط اعداد i1، j1، i2 و j2 به ترتیب نوشته شدهاند.
در خروجی k خط بنویسید، به طوری که در خط i ام عدد مستطیل i ام ورودی باشد.