[백준] 11660번 구간 합 구하기 5

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner kb = new Scanner(System.in);
    	StringBuilder sb = new StringBuilder();
    	
    	int n = kb.nextInt();
    	int m = kb.nextInt();
    	int[][] arr = new int[n+1][n+1];
    	int[][] pre = new int[n+1][n+1];
    	for(int i=1; i<=n; i++) {
    		for(int j=1; j<=n; j++) {
    			arr[i][j] = kb.nextInt();
    		}
    	}
    	
    	for(int i=1; i<=n; i++) {
    		for(int j=1; j<=n; j++) {
    			pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + arr[i][j];
    		}
    	}
    	
    	for(int i=0; i<m; i++) {
    		int x1 = kb.nextInt();
    		int y1 = kb.nextInt();
    		int x2 = kb.nextInt();
    		int y2 = kb.nextInt();
    		
    		int answer = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];
    		sb.append(answer).append('\n');
    		
    	}
    	
    	System.out.print(sb.toString());
    }
}