public static int[][] preprocess(int[][] matrix) {
        int[][] processed = new int[matrix.length][matrix[0].length];
        processed[0][0] = matrix[0][0];
        for (int i = 1; i < matrix.length; ++i) {
            processed[i][0] = processed[i - 1][0] + matrix[i][0];
        }
        for (int j = 1; j < matrix[0].length; ++j) {
            processed[0][j] = processed[0][j - 1] + matrix[0][j];
        }
        for (int i = 1; i < matrix.length; ++i) {
            for (int j = 1; j < matrix[0].length; ++j) {
                processed[i][j] = processed[i - 1][j] +
                                  processed[i][j - 1] -
                                  processed[i - 1][j - 1] +
                                  matrix[i][j];
            }
        }
        return processed;
    }