Problem: Problem

Given a sequence $ A $ of length $ H $ and a sequence $ B $ of length $ W $.

Define the matrix $ C $ consisting of $ H $ rows and $ W $ columns as follows.
$ C_ {i, j} = A_i \ times B_j (1 \ leq i \ leq H, 1 \ leq j \ leq W) $

Process the following four types of queries a total of $ Q $ times.

Query 1
$ 1 $ $ a $ $ b $ $ v $
$ A_i (a \ leq i \ leq b) Add $ v $ to $

Query 2
$ 2 $ $ c $ $ d $ $ v $
$ B_j (c \ leq j \ leq d) Add $ v $ to $

Query 3
$ 3 $ $ a $ $ b $ $ c $ $ d $
$ C_ {i, j} (a \ leq i \ leq b, c \ leq j \ leq d) Output the minimum value of $ and its number

Query 4
$ 4 $ $ a $ $ b $ $ c $ $ d $
$ C_ {i, j} (a \ leq i \ leq b, c \ leq j \ leq d) Output the maximum value of $ and its number

For details, refer to sample input / output.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq H, W, Q \ leq 10 ^ 5 $
* $ -1000 \ leq A_i \ leq 1000 $
* $ -1000 \ leq B_j \ leq 1000 $



For each query, the input satisfies the following conditions.


* $ 1 \ leq a \ leq b \ leq H $
* $ 1 \ leq c \ leq d \ leq W $
* $ -1000 \ leq v \ leq 1000 $

Input

The input is given in the following format.


$ H $ $ W $ $ Q $
$ A_1 $ $ A_2 $ ... $ A_H $
$ B_1 $ $ B_2 $ ... $ B_W $
$ query_1 $
$ query_2 $
...
$ query_Q $


Each query is given in one of the following four formats.


$ 1 $ $ a $ $ b $ $ v $
$ 2 $ $ c $ $ d $ $ v $
$ 3 $ $ a $ $ b $ $ c $ $ d $
$ 4 $ $ a $ $ b $ $ c $ $ d $


All inputs are given as integers.
$ H $, $ W $, $ Q $ are given on the first line, separated by blanks.
In the second row, the element $ A_i $ ($ 1 \ leq i \ leq H $) of the sequence $ A $ is given, separated by blanks.
In the third row, the element $ B_j $ ($ 1 \ leq j \ leq W $) of the sequence $ B $ is given, separated by blanks.
Queries are given on the 4th and subsequent $ Q $ lines, separated by line breaks.
All numbers in each query are separated by blanks.

Output

For each query 3 and query 4, output the value and number on one line, separated by blanks.

Examples

Input

4 4 7
1 2 3 4
1 2 3 4
3 2 3 2 3
4 2 3 2 3
3 1 1 1 1
4 1 1 1 1
1 1 1 1
3 1 4 1 2
4 2 3 2 4


Output

4 1
9 1
1 1
1 1
2 2
12 1


Input

4 4 6
1 1 1 1
1 1 1 1
3 1 4 1 4
4 1 4 1 4
1 2 3 1
2 2 3 1
3 1 4 1 4
4 1 4 1 4


Output

1 16
1 16
1 4
4 4


Input

4 4 7
0 1 0 1
1 0 1 0
3 2 4 1 3
4 1 4 1 4
1 1 4 -1
3 1 3 1 3
1 3 3 2
2 3 3 -2
3 2 4 2 4


Output

0 5
1 4
-1 4
-1 1


Input

36 4 20
-523 -460 -536 -885 652 782 513 -558 -521 -808 124 -708 -943 52 -856 -755 -958 913 380 -767 373 -731 -492 213 538 392 -39 509 -840 135 78 -285 -241 522 -572 -915
-691 -16 812 -385
4 7 17 4 4
3 24 33 1 1
4 3 35 2 4
3 28 32 4 4
2 3 3 438
3 7 15 1 1
4 2 17 4 4
3 24 28 2 4
4 15 16 4 4
4 18 29 1 1
3 24 27 2 4
2 2 3 -828
3 18 23 3 3
1 27 31 -701
2 2 3 298
1 21 32 237
2 3 3 -71
1 14 29 772
4 13 19 3 3
3 19 34 1 2


Output

368830 1
-371758 1
741356 1
-195965 1
-354483 1
368830 1
-207130 1
329560 1
580440 1
-207130 1
-323674 1
1093565 1
-1068977 1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;


#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

typedef long long ll;
typedef pair<ll,ll>pint;
int INF=1001001001;

struct seg{
    static const int SEG=1<<18;
    vint dat,put,way;
    seg():dat(SEG*2),put(SEG*2),way(SEG*2,1){
        for(int i=SEG-2;i>=0;i--){
            way[i]=way[i*2+1]+way[i*2+2];
        }
    }
    inline void push(int k){
        dat[k]+=put[k];
        if(k<SEG-1){
            put[k*2+1]+=put[k];
            put[k*2+2]+=put[k];
        }
        put[k]=0;
    }
    void add(int a,int b,int x,int k=0,int l=0,int r=SEG){
        push(k);
        if(r<=a||b<=l)return;
        if(a<=l&&r<=b){
            put[k]+=x;
            push(k);
            return;
        }
        add(a,b,x,k*2+1,l,(l+r)/2);
        add(a,b,x,k*2+2,(l+r)/2,r);
        dat[k]=max(dat[k*2+1],dat[k*2+2]);
        way[k]=0;
        if(dat[k]==dat[k*2+1])way[k]+=way[k*2+1];
        if(dat[k]==dat[k*2+2])way[k]+=way[k*2+2];
    }
    pint query(int a,int b,int k=0,int l=0,int r=SEG){
        push(k);
        if(r<=a||b<=l)return {-INF,114514};
        if(a<=l&&r<=b)return {dat[k],way[k]};
        pint p=query(a,b,k*2+1,l,(l+r)/2);
        pint q=query(a,b,k*2+2,(l+r)/2,r);
        if(p<q)swap(p,q);
        if(p.fi==q.fi)p.se+=q.se;
        return p;
    }
};


pint uku(pint a,pint b){

    return {a.fi*b.fi,a.se*b.se};
}

constexpr int X=200;
unordered_map<int,int>ukuA[1111],ukuB[1111];
int eiA[1111],eiB[1111];
int A[111111],B[111111];
signed main(){
    int H,W,Q;
    scanf("%d%d%d",&H,&W,&Q);

    rep(i,H)scanf("%d",&A[i]);
    rep(i,W)scanf("%d",&B[i]);

    rep(i,H)ukuA[i/X][A[i]]++;
    rep(i,W)ukuB[i/X][B[i]]++;


    seg segHma,segHmi,segWma,segWmi;
    rep(i,H){
        segHma.add(i,i+1,A[i]);
        segHmi.add(i,i+1,-A[i]);
    }
    rep(i,W){
        segWma.add(i,i+1,B[i]);
        segWmi.add(i,i+1,-B[i]);
    }

    while(Q--){
        int t,a,b,c,d,v;
        scanf("%d%d%d",&t,&a,&b);
        if(t<=2)scanf("%d",&v);
        else scanf("%d%d",&c,&d);

        a--;c--;

        if(t==1){
            segHma.add(a,b,v);
            segHmi.add(a,b,-v);
            int k=a/X;
            int lim=(a+X-1)/X*X;
            while(a<lim&&a<b){
                if(--ukuA[k][A[a]]==0)ukuA[k].erase(A[a]);
                A[a]+=v;
                ukuA[k][A[a]]++;
                a++;
            }
            k=b/X;
            lim=b/X*X;
            while(lim<b&&a<b){
                b--;
                if(--ukuA[k][A[b]]==0)ukuA[k].erase(A[b]);
                A[b]+=v;
                ukuA[k][A[b]]++;
            }
            k=a/X;
            while(a<b){
                eiA[k]+=v;
                a+=X;
                k++;
            }
        }
        else if(t==2){
            segWma.add(a,b,v);
            segWmi.add(a,b,-v);
            int k=a/X;
            int lim=(a+X-1)/X*X;
            while(a<lim&&a<b){
                if(--ukuB[k][B[a]]==0)ukuB[k].erase(B[a]);
                B[a]+=v;
                ukuB[k][B[a]]++;
                a++;
            }
            k=b/X;
            lim=b/X*X;
            while(lim<b&&a<b){
                b--;
                if(--ukuB[k][B[b]]==0)ukuB[k].erase(B[b]);
                B[b]+=v;
                ukuB[k][B[b]]++;
            }
            k=a/X;
            while(a<b){
                eiB[k]+=v;
                a+=X;
                k++;
            }
        }
        else{
            pint x,y,z,w;
            x=segHma.query(a,b);
            y=segHmi.query(a,b);y.fi*=-1;
            z=segWma.query(c,d);
            w=segWmi.query(c,d);w.fi*=-1;

            if(x.fi==y.fi)y.se=0;
            if(z.fi==w.fi)w.se=0;
            vector<pint> latte;
            latte.pb(uku(x,z));
            latte.pb(uku(x,w));
            latte.pb(uku(y,z));
            latte.pb(uku(y,w));
            sort(all(latte));
            vector<pint> malta;
            rep(i,latte.size()){
                if(malta.size()==0||malta.back().fi!=latte[i].fi){
                    malta.pb(latte[i]);
                }
                else{
                    malta.back().se+=latte[i].se;
                }
            }

            ll ans,hoge;
            if(t==3){
                tie(ans,hoge)=malta.front();
            }
            else{
                tie(ans,hoge)=malta.back();
            }
            if(ans==0){
                ll cntA=0,cntB=0;
                ll lenA=b-a;
                ll lenB=d-c;
                int k=a/X;
                int lim=(a+X-1)/X*X;
                while(a<lim&&a<b){
                    if(A[a]+eiA[k]==0)cntA++;
                    a++;
                }
                k=b/X;
                lim=b/X*X;
                while(lim<b&&a<b){
                    b--;
                    if(A[b]+eiA[k]==0)cntA++;
                }
                k=a/X;
                while(a<b){
                    if(ukuA[k].count(-eiA[k]))cntA+=ukuA[k][-eiA[k]];
                    a+=X;
                    k++;
                }


                k=c/X;
                lim=(c+X-1)/X*X;

                while(c<lim&&c<d){
                    if(B[c]+eiB[k]==0)cntB++;
                    c++;
                }
                k=d/X;
                lim=d/X*X;
                while(lim<d&&c<d){
                    d--;
                    if(B[d]+eiB[k]==0)cntB++;
                }
                k=c/X;
                while(c<d){
                    if(ukuB[k].count(-eiB[k]))cntB+=ukuB[k][-eiB[k]];
                    c+=X;
                    k++;
                }
                hoge=cntA*lenB+lenA*cntB-cntA*cntB;
            }
            printf("%lld %lld\n",ans,hoge);
        }
    }
    return 0;
}


/*

5 5 1141514
1 1 0 0 0
0 1 3 3 3
3 1 5 1 5
1 1 5 -1
3 1 5 1 5
2 1 5 -3
3 1 5 1 5

*/