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 int long long
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))

typedef long long ll;

int h,w,q;
int a[125252], b[125252];
const int B = 512;
int sa[125252], sb[125252];
int adda[125252/B], addb[125252/B];

const int INF = (1ll<<60);
const int IINF = INF>>1;

void init(){
  REP(i,125252)sa[i] = INF;
  REP(i,h)sa[i] = a[i];
  REP(i,(h+B-1)/B){
    sort(sa+i*B, sa+(i+1)*B);
    adda[i] = 0;
  }

  REP(i,125252)sb[i] = INF;
  REP(i,w)sb[i] = b[i];
  REP(i,(w+B-1)/B){
    sort(sb+i*B, sb+(i+1)*B);
    addb[i] = 0;
  }
}

void qadd(int type, int l, int r, int v){
  int *arr = (type==0 ? a : b);
  int *srt = (type==0 ? sa : sb);
  int *add = (type==0 ? adda : addb);
  if(l%B!=0){
    int id = l/B;
    int dd = add[id]; add[id] = 0;
    FOR(i,id*B,(id+1)*B)arr[i]+=dd;
    while(l<r && l%B!=0){
      arr[l] += v;
      l++;
    }
    FOR(i,id*B,(id+1)*B)srt[i]=arr[i];
    sort(srt+id*B,srt+(id+1)*B);
  }
  if(r%B!=0){
    int id = r/B;
    int dd = add[id]; add[id] = 0;
    FOR(i,id*B,(id+1)*B)arr[i]+=dd;
    while(l<r && r%B!=0){
      r--;
      arr[r] += v;
    }
    FOR(i,id*B,(id+1)*B)srt[i]=arr[i];
    sort(srt+id*B,srt+(id+1)*B);
  }
  while(l<r){
    int id = l/B;
    add[id] += v;
    l += B;
  }
}

int qmax(int type, int l, int r){
  int *arr = (type==0 ? a : b);
  int *srt = (type==0 ? sa : sb);
  int *add = (type==0 ? adda : addb);
  int ret = -INF;
  {
    int id = l/B;
    while(l<r && l%B!=0){
      CHMAX(ret, arr[l]+add[id]);
      l++;
    }
  }
  {
    int id = r/B;
    while(l<r && r%B!=0){
      r--;
      CHMAX(ret, arr[r]+add[id]);
    }
  }
  while(l<r){
    int id = l/B;
    CHMAX(ret, srt[(id+1)*B-1]+add[id]);
    l += B;
  }
  return ret;
}

int qmin(int type, int l, int r){
  int *arr = (type==0 ? a : b);
  int *srt = (type==0 ? sa : sb);
  int *add = (type==0 ? adda : addb);
  int ret = INF;
  {
    int id = l/B;
    while(l<r && l%B!=0){
      CHMIN(ret, arr[l]+add[id]);
      l++;
    }
  }
  {
    int id = r/B;
    while(l<r && r%B!=0){
      r--;
      CHMIN(ret, arr[r]+add[id]);
    }
  }
  while(l<r){
    int id = l/B;
    CHMIN(ret, srt[id*B]+add[id]);
    l += B;
  }
  return ret;
}

int qcnt(int type, int l, int r, int v){
  int *arr = (type==0 ? a : b);
  int *srt = (type==0 ? sa : sb);
  int *add = (type==0 ? adda : addb);
  int ret = 0;
  {
    int id = l/B;
    while(l<r && l%B!=0){
      // printf("l%d r%d arrl%d\n",l,r,arr[l]);
      ret += (int)(arr[l]+add[id]==v);
      l++;
    }
  }
  {
    int id = r/B;
    while(l<r && r%B!=0){
      // printf("l%d r%d arrr%d\n",l,r,arr[r]);
      r--;
      ret += (int)(arr[r]+add[id]==v);
    }
  }
  while(l<r){
    int id = l/B;
    // x + add[id] == v
    // x == v - add[id]
    ret += upper_bound(srt+id*B, srt+(id+1)*B, v-add[id])
         - lower_bound(srt+id*B, srt+(id+1)*B, v-add[id]);
    l += B;
  }
  return ret;
}

pair<ll,ll> query(int type, int l, int r, int l2, int r2){
  int amax = qmax(0, l, r);
  int amin = qmin(0, l, r);
  int bmax = qmax(1, l2, r2);
  int bmin = qmin(1, l2, r2);
  ll val = type==1 ? -INF : INF;
  if(type==1){
    CHMAX(val, (ll)amax*bmax);
    CHMAX(val, (ll)amax*bmin);
    CHMAX(val, (ll)amin*bmax);
    CHMAX(val, (ll)amin*bmin);
  }else{
    CHMIN(val, (ll)amax*bmax);
    CHMIN(val, (ll)amax*bmin);
    CHMIN(val, (ll)amin*bmax);
    CHMIN(val, (ll)amin*bmin);
  }
  if(val==0){
    int azero = qcnt(0,l,r,0);
    int bzero = qcnt(1,l2,r2,0);
    ll ret = 0;
    ret += (ll)(r-l) * (r2-l2);
    ret -= (ll)(r-l-azero) * (r2-l2-bzero);
    return make_pair(val, ret);
  }
  ll ret = 0;
  if(amax==amin && bmax==bmin){
    ret += (ll)qcnt(0,l,r,amax) * qcnt(1,l2,r2,bmax);
  }else if(amax==amin){
    if((ll)amax*bmax == val)ret += (ll)qcnt(0,l,r,amax) * qcnt(1,l2,r2,bmax);
    if((ll)amax*bmin == val)ret += (ll)qcnt(0,l,r,amax) * qcnt(1,l2,r2,bmin);
  }else if(bmax==bmin){
    if((ll)amax*bmax == val)ret += (ll)qcnt(0,l,r,amax) * qcnt(1,l2,r2,bmax);
    if((ll)amin*bmax == val)ret += (ll)qcnt(0,l,r,amin) * qcnt(1,l2,r2,bmax);
  }else{
    if((ll)amax*bmax == val)ret += (ll)qcnt(0,l,r,amax) * qcnt(1,l2,r2,bmax);
    if((ll)amax*bmin == val)ret += (ll)qcnt(0,l,r,amax) * qcnt(1,l2,r2,bmin);
    if((ll)amin*bmax == val)ret += (ll)qcnt(0,l,r,amin) * qcnt(1,l2,r2,bmax);
    if((ll)amin*bmin == val)ret += (ll)qcnt(0,l,r,amin) * qcnt(1,l2,r2,bmin);
  }
  return make_pair(val, ret);
}

signed main(){
  scanf("%lld%lld%lld",&h,&w,&q);
  REP(i,h)scanf("%lld",a+i);
  REP(i,w)scanf("%lld",b+i);
  init();
  while(q--){
    int type;
    scanf("%d",&type);
    if(type<=2){
      int l,r,v;scanf("%lld%lld%lld",&l,&r,&v);
      qadd(type-1,l-1,r,v);
    }else{
      int l,r,l2,r2;scanf("%lld%lld%lld%lld",&l,&r,&l2,&r2);
      pair<ll,ll> ans = query(type-3, l-1,r,l2-1,r2);
      printf("%lld %lld\n",ans.first, ans.second);
    }
  }
  return 0;
}