vector<int> one_dimension_prefix(vector<int> nums) {
    int n = nums.size();
	vector<int> prefix(n + 1);
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + nums[i - 1];
    }
    return prefix;
}

vector<vector<int>> two_dimension_prefix(vector<vector<int>> nums) {
    int m = nums.size();
    int n = nums[0].size();
    vector<vector<int>> prefix(m + 1, vector(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            prefix[i][j] = nums[i][j] + prefix[i - 1][j]
                + prefix[i][j - 1] - prefix[i - 1][j - 1];
        }
    }
    return prefix;
}