//AcWing 798. 差分矩阵

#include<iostream>
using namespace std;

const int N = 1010;
int n,m,q;
int a[N][N],b[N][N];

void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1] += c;
    b[x2+1][y1] -= c;
    b[x1][y2+1] -= c;
    b[x2+1][y2+1] += c;
}
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            insert(i,j,i,j,a[i][j]);//初始a视为全0矩阵；插入原始数据
        }
    }
    while(q--){//执行q次操作
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);
    }

    for(int i=1;i<=n;i++){//计算前缀和
        for(int j=1;j<=m;j++){
            b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1];
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%d ", b[i][j]);
        }
        cout<<'\n';
    }
    return 0;
}

//AcWing 797. 差分

#include<iostream>
using namespace  std;

const int N = 1e5+10;
int a[N],b[N];
void insert(int l,int r,int c){
    b[l] += c;
    b[r+1] -= c;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]); //前缀和数组b为全0;初始数据视为插入
        insert(i,i,a[i]);
    }  
    while(m--){
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        insert(l,r,c);
    }

    for(int i=1; i<=n; i++)  b[i] += b[i-1];//操作完之后求前缀和
    for(int i=1; i<=n; i++)  printf("%d ", b[i]);
    return 0;
}

//AcWing 796. 子矩阵的和

#include<iostream>
using namespace std;

const int N = 1010;
int a[N][N],s[N][N];

int main(){
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d", &a[i][j]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j];//求前缀和

    while(q--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n", s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);//求子矩阵的和
    }

    return 0;
}

//AcWing 795. 前缀和

#include<iostream>
using namespace std;

const int N = 1e5+10;
int a[N],s[N];//全局变量，默认初始全为0
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)   scanf("%d", &a[i]);
    for(int i=1;i<=n;i++)   s[i] = s[i-1]+a[i];//s[0] = 0;
    while(m--){
        int l,r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l-1]);//统一写法，少特判
    }
    return 0;
}

//AcWing 794. 高精度除法

//高精度 / 低精度
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int> &A, int a, int &r){
    vector<int>C;
    for(int i=A.size()-1; i>=0; i--){//从高位开始除起
        r = r*10 + A[i];
        C.push_back(r / a);
        r %= a;
    }
    reverse(C.begin(),C.end());
    //去前导0（*0）
    while(C.size()>1 && C.back() == 0)  C.pop_back();
    return C;
}
int main(){
    string s;
    int a;
    cin>>s>>a;
    vector<int>A;
    int r = 0;
    for(int i = s.size()-1; i>=0; i--)  A.push_back(s[i] - '0');
    auto C = div(A,a,r);
    for(int i = C.size()-1; i>=0; i--)  printf("%d", C[i]);
    cout<<endl<<r;
    return 0;
}

//AcWing 793. 高精度乘法

//高精度 * 低精度
#include<iostream>
#include<vector>

using namespace std;
vector<int> mul(vector<int> &A, int a){
    vector<int>C;
    int t = 0;
    for(int i=0; i<A.size()||t; i++){//高精度各位还未遍历完或进位没有处理完
        if(i<A.size())  t+=A[i]*a;
        C.push_back(t%10);
        t /= 10;
    }
    //去前导0（*0）
    while(C.size()>1 && C.back() == 0)  C.pop_back();
    return C;
}
int main(){
    string s;
    int a;
    cin>>s>>a;
    vector<int>A;
    for(int i = s.size()-1; i>=0; i--)  A.push_back(s[i] - '0');
    auto C = mul(A,a);
    for(int i = C.size()-1; i>=0; i--)  printf("%d", C[i]);
    return 0;
}

//AcWing 792. 高精度减法

#include<iostream>
#include<vector>

using namespace std;
bool cmp(string a, string b){//a>=b
    if(a.size() != b.size())    return a.size() > b.size();
    else  return a.compare(b)>=0 ? 1 : 0;
}
vector<int> sub (vector<int> &A, vector<int> &B){
    vector<int> C;
    int t = 0;//记录借位
    for(int i = 0;i<A.size();i++){
        t = A[i] - t;
        if(i<B.size())
            t -= B[i];
        C.push_back((t+10)%10);
        if(t<0) t = 1;
        else t=0;
    }
    //删前导0
    while(C.size()>1 && C.back() == 0)  C.pop_back();

    return C;

}
int main(){
    string a,b;
    vector<int>A,B;
    cin>>a>>b;
    for(int i=a.size()-1; i>=0; i--)    A.push_back(a[i] - '0');
    for(int i=b.size()-1; i>=0; i--)    B.push_back(b[i] - '0');

    if(cmp(a,b)){//A>B
        auto C = sub(A,B);
        for(int i=C.size()-1; i>=0 ; i-- )    printf("%d", C[i]);
    }
    else{//A<B
        auto C = sub(B,A);
        cout<<"-";
        for(int i=C.size()-1; i>=0 ; i-- )    printf("%d", C[i]);//A>B
    }
    return 0;
}

//AcWing 791. 高精度加法

#include<iostream>
#include<vector>

using namespace std;
vector<int> add (vector<int> &A, vector<int> &B){
    if(A.size() < B.size()) return add(B,A);
    int t = 0;//记录进位
    vector<int> C;
    for(int i = 0;i<A.size();i++){
        t+=A[i];
        if(i<B.size())
            t+=B[i];
        C.push_back(t%10);
        t /= 10;
    }
    if(t) C.push_back(t);
    return C;

}
int main(){
    string a,b;
    vector<int>A,B;
    cin>>a>>b;
    for(int i=a.size()-1; i>=0; i--)    A.push_back(a[i] - '0');//由低位向高位存储,方便后续添加进位
    for(int i=b.size()-1; i>=0; i--)    B.push_back(b[i] - '0');

    auto C = add(A,B);

    for(int i=C.size()-1; i>=0 ; i-- )    printf("%d", C[i]);

    return 0;
}

//AcWing 790. 数的三次方根

#include<iostream>
#include<math.h>
using namespace std;


//只要问题的答案是有边界的，就可以考虑二分
int main(){
    double x;
    scanf("%lf",&x);
    double l = -10000, r = 10000, mid;
    while(r-l>1e-8){
        mid = (l+r) / 2;
        if(mid*mid*mid > x) r = mid;
        else l = mid;
    }
    printf("%.6lf",mid);
    return 0;
}

//AcWing 789. 数的范围
//二分找到所查询数的左端点和右端点

#include<iostream>

using namespace std;

const int N = 1e5+10;
int a[N];

int main(){
    int n,q;
    cin>>n>>q;
    for(int i=0;i<n;i++)    scanf("%d", &a[i]);
    while(q--){
        int x;
        scanf("%d", &x);
        int l = 0, r = n-1;
        while(l<r){
            int mid = l+r>>1;//配套使用
            if(a[mid]>=x)   r = mid;//配套使用
            else l = mid+1;//配套使用
        }
        if(a[l] != x)   cout<<"-1 -1"<<endl;
        else{
            cout<<l<<" ";

            int l = 0, r = n-1;
            while(l<r){
                int mid = l+r+1>>1;//配套使用 //下一行更新 l = mid,此处必须+1，因为c++除法是向下取整，+1保是 l 向右偏，不会导致无效更新从而陷入死循环
                if(a[mid] <= x) l = mid;//配套使用
                else    r = mid - 1;//配套使用
            }
            cout<<l<<endl;
        }

    }
    return 0;
}