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;
using Int = long long;

template <typename T,typename E>
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  typedef function<E(E,E)> H;
  typedef function<E(E,Int)> P;
  Int n;
  F f;
  G g;
  H h;
  T d1;
  E d0;
  P p;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(Int n_,F f,G g,H h,T d1,E d0,
	      vector<T> v=vector<T>(),
	      P p=[](E a,Int b){++b;return a;}):
    f(f),g(g),h(h),d1(d1),d0(d0),p(p){
    
    init(n_);
    if(n_==(Int)v.size()) build(n_,v);
  }
  void init(Int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
    laz.clear();
    laz.resize(2*n-1,d0);
  }
  void build(Int n_, vector<T> v){
    for(Int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(Int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  inline void eval(Int len,Int k){
    if(laz[k]==d0) return;
    if(k*2+1<n*2-1){
      laz[k*2+1]=h(laz[k*2+1],laz[k]);
      laz[k*2+2]=h(laz[k*2+2],laz[k]);
    }
    dat[k]=g(dat[k],p(laz[k],len));
    laz[k]=d0;
  }
  T update(Int a,Int b,E x,Int k,Int l,Int r){
    eval(r-l,k);
    if(r<=a||b<=l) return dat[k];
    if(a<=l&&r<=b){
      laz[k]=h(laz[k],x);
      return g(dat[k],p(laz[k],r-l));
    }
    return dat[k]=f(update(a,b,x,k*2+1,l,(l+r)/2),
		    update(a,b,x,k*2+2,(l+r)/2,r));
  }
  T update(Int a,Int b,E x){
    return update(a,b,x,0,0,n);
  }
  T query(Int a,Int b,Int k,Int l,Int r){
    eval(r-l,k);
    if(r<=a||b<=l) return d1;
    if(a<=l&&r<=b) return dat[k];
    T vl=query(a,b,k*2+1,l,(l+r)/2);
    T vr=query(a,b,k*2+2,(l+r)/2,r);
    return f(vl,vr);
  }
  T query(Int a,Int b){
    return query(a,b,0,0,n);
  }
  void update(Int k,T x){
    query(k,k+1);//evaluate
    k+=n-1;
    dat[k]=x;
    while(k){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
};

struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE
signed main(){
  using T = tuple<Int, Int, Int, Int>;
  
  SegmentTree<T, Int>::F f=[](T a,T b){
    Int aw,ax,ay,az;
    tie(aw,ax,ay,az)=a;
    Int bw,bx,by,bz;
    tie(bw,bx,by,bz)=b;
    Int cw=min(aw,bw);
    Int cx=(aw==bw?ax+bx:(aw<bw?ax:bx));
    Int cy=max(ay,by);
    Int cz=(ay==by?az+bz:(ay>by?az:bz));
    return T(cw,cx,cy,cz);
  };
 
  SegmentTree<T, Int>::G g=[](T a,Int b){
    Int aw,ax,ay,az;
    tie(aw,ax,ay,az)=a;
    return T(aw+b,ax,ay+b,az);
  };

  SegmentTree<T, Int>::H h=[](Int a,Int b){
    return a+b;
  };

  Int H,W,Q;
  cin>>H>>W>>Q;
  vector<T> A,B;
  for(Int i=0;i<H;i++){
    Int v;
    cin>>v;
    A.emplace_back(v,1,v,1);
  }
  for(Int i=0;i<W;i++){
    Int v;
    cin>>v;
    B.emplace_back(v,1,v,1);
  }
  
  const Int INF = 1e17;
  T d1(INF,0,-INF,0);
  SegmentTree<T, Int> segY(H,f,g,h,d1,0,A);
  SegmentTree<T, Int> segX(W,f,g,h,d1,0,B);

  auto calc=[](Int t,T a,T b,Int p,Int q){
    Int aw,ax,ay,az;
    tie(aw,ax,ay,az)=a;
    Int bw,bx,by,bz;
    tie(bw,bx,by,bz)=b;
    Int res=t==3?
    min({aw*bw,aw*by,ay*bw,ay*by}):
    max({aw*bw,aw*by,ay*bw,ay*by});
    Int cnt=0;
    Int n=p-(!aw?ax:!ay?az:0ll);
    Int m=q-(!bw?bx:!by?bz:0ll);
    if(res==0) cnt=p*q-n*m;
    else{
      if(aw==ay) az=0;
      if(bw==by) bz=0;
      if(res==aw*bw) cnt+=ax*bx;
      if(res==aw*by) cnt+=ax*bz;
      if(res==ay*bw) cnt+=az*bx;
      if(res==ay*by) cnt+=az*bz;
    }
    
    cout<<res<<" "<<cnt<<endl;
  };
  
  for(Int i=0;i<Q;i++){
    Int t;
    cin>>t;
    if(t==1){
      Int a,b,v;
      cin>>a>>b>>v;
      segY.update(--a,b,v);
    }
    if(t==2){
      Int c,d,v;
      cin>>c>>d>>v;
      segX.update(--c,d,v);
    }
    if(t==3||t==4){
      Int a,b,c,d;
      cin>>a>>b>>c>>d;
      T y=segY.query(--a,b);
      T x=segX.query(--c,d);
      calc(t,y,x,b-a,d-c);
    }
  }
  
  return 0;
}