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<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

template<typename T>
struct LazySegmentTree{
private:
    int n;
    vector<T> node;
    vector<int> lazy;
    T E0;
    int E1=0;

    inline void updatef(int& lazy,int& value){
        //lazy += value;
        lazy += value;
        //lazy = max(lazy, value);
        //lazy = min(lazy, value);
    }
    inline void calculatef(T& node,int& lazy,int len){
        //node += lazy * len;
        // node += lazy ;
        node.first += lazy ;
    }
    inline T queryf(T& x,T& y){
        //return x + y;
        //return x * y;
        //return max(x, y);
        if(x.first<y.first)return x;
        else if(x.first>y.first)return y;
        else return {x.first, x.second+y.second};
    }
public:
    LazySegmentTree(int sz,T nodeE,int lazyE = 0):E0(nodeE), E1(lazyE){
        n=1;
        while(n<sz)n<<=1;
        node.resize(2*n-1,E0);
        lazy.resize(2*n-1,E1);
    }

    LazySegmentTree(vector<T>& v,T E0,int E1=0 ):E0(E0),E1(E1){
        n=1;
        int sz=v.size();
        while(n<sz)n<<=1;
        node.resize(2*n-1,E0);
        lazy.resize(2*n-1,E1);
        rep(i,sz)node[i+n-1] = v[i];
        for(int i=n-2; i>=0; --i){
            node[i] = queryf(node[2*i+1],node[2*i+2]);
        }
    }

    void eval(int k,int l,int r){
        if(lazy[k]==E1)return ;
        calculatef(node[k], lazy[k], r-l);
        if(r-l>1){
            updatef(lazy[2*k+1], lazy[k]);
            updatef(lazy[2*k+2], lazy[k]);
        }
        lazy[k]=E1;
    }

    void update(int a, int b, int x,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        eval(k,l,r);
        if(r<=a||b<=l)return;
        if(a<=l&&r<=b){
            updatef(lazy[k], x);
            eval(k,l,r);
        }
        else {
            update(a,b,x,2*k+1,l,(l+r)/2);
            update(a,b,x,2*k+2,(l+r)/2,r);
            node[k]=queryf(node[2*k+1], node[2*k+2]);
        }
    }

    T query(int a,int b,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        eval(k,l,r);
        if(r<=a||b<=l)return E0;
        if(a<=l&&r<=b)return node[k];
        T xl=query(a,b,2*k+1,l,(l+r)/2);
        T xr=query(a,b,2*k+2,(l+r)/2,r);
        return queryf(xl, xr);
    }
};

pair<ll,ll> fun(pair<ll,ll> p,pair<ll,ll>q){
    if(p.first<q.first)return p;
    if(p.first>q.first)return q;
    else return {p.first,p.second+q.second};
}
pair<ll,ll> mul(pair<ll,ll> p,pair<ll,ll>q){
    return {p.first*q.first, p.second*q.second};
}


int main(){
    int h,w,q;
    cin>>h>>w>>q;
    vector<pair<ll,ll>> h1(h),h2(h),w1(w),w2(w);
    rep(i,h){
        cin>>h1[i].first;
        h2[i].first=-h1[i].first;
        h1[i].second=h2[i].second=1;
    } 
    rep(i,w){
        cin>>w1[i].first;
        w2[i].first=-w1[i].first;
        w1[i].second=w2[i].second=1;
    } 
    pair<ll,ll> e={longinf,1};
    LazySegmentTree<pair<ll,ll>> hmin(h1,e),hmax(h2,e),wmin(w1,e),wmax(w2,e);
    while(q--){
        int type;
        cin>>type;
        if(type==1){
            int a,b,c;
            cin>>a>>b>>c;
            hmin.update(a-1,b,c);
            hmax.update(a-1,b,-c);
        }
        else if(type==2){
            int a,b,c;
            cin>>a>>b>>c;
            wmin.update(a-1,b,c);
            wmax.update(a-1,b,-c);
        }
        else if(type==3){
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            auto Hmin=hmin.query(a-1, b);
            auto Hmax=hmax.query(a-1, b);
            auto Wmin=wmin.query(c-1, d);
            auto Wmax=wmax.query(c-1, d);
            Hmax.first*=-1;
            Wmax.first*=-1;
            if(Hmin.second==b-a+1)Hmax={Hmin.first,0};
            if(Wmin.second==d-c+1)Wmax={Wmin.first,0};
            pair<ll,ll> ans={longinf,1};
            ans=fun(ans,mul(Hmin,Wmin));
            ans=fun(ans,mul(Hmax,Wmin));
            ans=fun(ans,mul(Hmin,Wmax));
            ans=fun(ans,mul(Hmax,Wmax));
            if(ans.first==0){
                ll cnth=0,cntw=0;
                if(Hmax.first==0)cnth=Hmax.second;
                if(Hmin.first==0)cnth=Hmin.second;
                if(Wmax.first==0)cntw=Wmax.second;
                if(Wmin.first==0)cntw=Wmin.second;
                ans.second=(ll)(d-c+1)*(b-a+1)-(b-a+1-cnth)*(d-c+1-cntw);
            }
            cout<<ans.first<<" "<<ans.second<<endl;
        }
        else if(type==4){
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            auto Hmin=hmin.query(a-1, b);
            auto Hmax=hmax.query(a-1, b);
            auto Wmin=wmin.query(c-1, d);
            auto Wmax=wmax.query(c-1, d);
            Hmax.first*=-1;
            Wmin.first*=-1;
            if(Hmin.second==b-a+1)Hmax={Hmax.first,0};
            if(Wmin.second==d-c+1)Wmax={Wmax.first,0};
            pair<ll,ll> ans={longinf,1};
            ans=fun(ans,mul(Hmin,Wmin));
            ans=fun(ans,mul(Hmax,Wmin));
            ans=fun(ans,mul(Hmin,Wmax));
            ans=fun(ans,mul(Hmax,Wmax));
            if(ans.first==0){
                ll cnth=0,cntw=0;
                if(Hmax.first==0)cnth=Hmax.second;
                if(Hmin.first==0)cnth=Hmin.second;
                if(Wmax.first==0)cntw=Wmax.second;
                if(Wmin.first==0)cntw=Wmin.second;
                ans.second=(ll)(d-c+1)*(b-a+1)-(b-a+1-cnth)*(d-c+1-cntw);
            }
            cout<<-ans.first<<" "<<ans.second<<endl;
        }
    } 
    return 0;
}