#include "bits/stdc++.h" #include #include #include #define rep(i,n) for(int i = 0; i < n; i++) typedef long long ll; typedef unsigned long long ull; using namespace std; #define vll vector> #define vl vector #define vi vector #define vii vector> #define pb push_back #define pf push_front #define ld long double #define Sort(a) sort(a.begin(),a.end()) #define cSort(a,cmp) sort(a.begin(),a.end(),cmp) #define reSort(a) sort(a.rbegin(), a.rend()) static const ll llMAX = numeric_limits::max(); static const int intMAX = numeric_limits::max(); static const ll llMIN = numeric_limits::min(); static const int intMIN = numeric_limits::min(); static const ll d_5 = 100000; static const ll d9_7 = 1000000007; static const ll d_9 = 1000000000; static const double PI=3.14159265358979323846; template void Printvector(std::vector a){ int size = a.size(); rep(i,size){ cout< void Printvector(std::vector> a){ int size = a.size(); rep(i,size){ int size2=a[i].size(); rep(j,size2){ cout< vector getaccum(vector a){ int size=a.size(); vector ans(size); ans[0]=a[0]; for(int i=0;i vector> getaccum2D(vector> a){ int sizey=a.size(); int sizex=a[0].size(); vector> ans(sizey,vector(sizex,0)); //ans=a; ans[0][0]=a[0][0]; for(int i=1;i accum,int l,int r){//閉区間[l,r]の総和 if(l==0){ return accum[r]; }else{ return accum[r]-accum[l-1]; } } template T getaccumnum2D(vector> accum,int x1,int y1,int x2,int y2){//2の方が右下、閉区間 T ans=accum[y2][x2]; if(x1==0 && y1==0){ ; }else if(x1>0 && y1==0){ ans-=accum[y2][x1-1]; }else if(x1==0 && y1>0){ ans-=accum[y1-1][x2]; }else{ ans-=accum[y1-1][x2]; ans-=accum[y2][x1-1]; ans+=accum[y1-1][x1-1]; } return ans; } int main(void){ ll n,M; cin>>n>>M; vll m(M,vl(M)); rep(i,M){ rep(j,M){ cin>>m[i][j]; } } vi x(n),y(n); rep(i,n){ cin>>y[i]>>x[i]; x[i]--; y[i]--; } vll accum = getaccum2D(m); int ans=0; rep(i,n){ ans=0; for(int x1=0;x1<=x[i];x1++){ for(int x2=x[i];x2