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 <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

const long long INF = 1LL<<60;
typedef long long DELAY;

struct VAL {
  long long minv;
  long long maxv;
  long long minnum;
  long long maxnum;
  VAL() {
	minv = maxv = 0;
	minnum = maxnum = 1;
  }
  VAL(long long a, long long b, long long c, long long d) {
	minv = a;
	maxv = b;
	minnum = c;
	maxnum = d;
  }
  friend ostream& operator << (ostream& s, const VAL& v) {
	return s << "(<" << v.minv << "," << v.minnum << ">, <" << v.maxv << ", " << v.maxnum << ">)";
  }
};



template<class Monoid, class Action> struct SegTree {
    int size_seg = 1;
    vector<Monoid> val;
    vector<Action> delay;
    Monoid UNITY_MONOID = VAL(INF, -INF, 0, 0); // to be set
    Action UNITY_ACTION = 0;                    // to be set
    
    SegTree(int n = 1) { init(n); }
    SegTree(int n, const Monoid &init_monoid, const Action &init_action) { init(n, init_monoid, init_action); }
    
    void init(int n = 1) {
        size_seg = 1;
        while (size_seg < n) size_seg <<= 1;
        val.resize(size_seg * 2 - 1); delay.resize(size_seg * 2 - 1);
        for (int i = 0; i < size_seg * 2 - 1; ++i) {
            val[i] = UNITY_MONOID;
            delay[i] = UNITY_ACTION;
        }
    }
    
    void init(int n, const Monoid &init_monoid, const Action &init_action) {
        size_seg = 1;
        while (size_seg < n) size_seg <<= 1;
        val.resize(size_seg * 2 - 1); delay.resize(size_seg * 2 - 1);
        for (int i = 0; i < size_seg * 2 - 1; ++i) {
            val[i] = init_monoid;
            delay[i] = init_action;
        }
    }
    
    inline void init_set(int a, const Monoid &x) {
        a += size_seg - 1;
        val[a] = x;
    }
    
    inline void init_tree(int k = 0, int l = 0, int r = -1) {
        if (r == -1) r = size_seg;
        if (r - l > 1) {
            init_tree(k*2+1, l, (l+r)/2);
            init_tree(k*2+2, (l+r)/2, r);
            val[k] = merge(val[k*2+1], val[k*2+2]);
        }
    }
    
    inline Monoid merge(const Monoid &x, const Monoid &y) {
        Monoid res = UNITY_MONOID;
        
        if (x.minv > y.minv) {
            res.minv = y.minv;
            res.minnum = y.minnum;
        }
        else if (x.minv == y.minv) {
            res.minv = x.minv;
            res.minnum = x.minnum + y.minnum;
        }
        else {
            res.minv = x.minv;
            res.minnum = x.minnum;
        }
        
        if (x.maxv < y.maxv) {
            res.maxv = y.maxv;
            res.maxnum = y.maxnum;
        }
        else if (x.maxv == y.maxv) {
            res.maxv = x.maxv;
            res.maxnum = x.maxnum + y.maxnum;
        }
        else {
            res.maxv = x.maxv;
            res.maxnum = x.maxnum;
        }
        
        return res;
    }

    inline void add(Action &d, const Action &e) {
        // d += e;
        d += e;
    }
    
    inline void reflect(Monoid &x, const Action &d, int l, int r) {
        // x += d;
        x.minv += d;
        x.maxv += d;
    }
    
    inline void redelay(int k, int l, int r) {
        reflect(val[k], delay[k], l, r);
        if (k < size_seg-1) {
            add(delay[k*2+1], delay[k]);
            add(delay[k*2+2], delay[k]);
        }
        delay[k] = UNITY_ACTION;
    }
    
    inline void renode(int k, int l, int r) {
        val[k] = merge(val[k*2+1], val[k*2+2]);
    }
    
    inline void set(int a, int b, DELAY x, int k = 0, int l = 0, int r = -1) {
        if (r == -1) r = size_seg;
        if (a <= l && r <= b) {                 // included
            add(delay[k], x);
            redelay(k, l, r);
        }
        else if (a < r && l < b) {              // intersected
            redelay(k, l, r);
            set(a, b, x, k*2+1, l, (l+r)/2);
            set(a, b, x, k*2+2, (l+r)/2, r);
            renode(k, l, r);
        }
        else {                                  // no-intersected
            redelay(k, l, r);
        }
    }
  
    inline Monoid get(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r == -1) r = size_seg;
        redelay(k, l, r);
        if (a <= l && r <= b) {                 // included
            return val[k];
        }
        else if (a < r && l < b) {              // intersected
            Monoid t1 = get(a, b, k*2+1, l, (l+r)/2);
            Monoid t2 = get(a, b, k*2+2, (l+r)/2, r);
            renode(k, l, r);
            return merge(t1, t2);
        }
        else {                                  // no-intersected
            return UNITY_MONOID;
        }
    }
  
    inline Monoid operator [] (int i) {return get(i, i+1);}
  
    void print() {
        long long t = 2;
        for (int i = 0; i < size_seg*2-1; ++i) {
            cout << make_pair(val[i], delay[i]) << ",";
            if (i == t-2) {cout << endl; t *= 2;}
        }
        for (int i = 0; i < size_seg; ++i) {
            cout << get(i, i+1) << ", ";
        }
        cout << endl << endl;
    }
};

SegTree<VAL,int> xseg, yseg;



long long H, W, Q;


int main() {
  while (cin >> H >> W >> Q) {
	xseg.init((int)max(H, W)+2, VAL(0, 0, 1, 1), 0);
	yseg.init((int)max(H, W)+2, VAL(0, 0, 1, 1), 0);
	for (int i = 0; i < H; ++i) {
	  int x;
	  cin >> x;
	  xseg.set(i, i+1, x);
	}
	for (int i = 0; i < W; ++i) {
	  int y;
	  cin >> y;
	  yseg.set(i, i+1, y);
	}

	

	for (int q = 0; q < Q; ++q) {
	  int t;
	  cin >> t;
	  if (t == 1) {
		int a, b;
		long long v;
		cin >> a >> b >> v;
		--a, --b;
		xseg.set(a, b+1, v);
	  }
	  else if (t == 2) {
		int c, d;
		long long v;
		cin >> c >> d >> v;
		--c, --d;
		yseg.set(c, d+1, v);
	  }
	  else if (t == 3 || t == 4) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		--a, --b, --c, --d;
	    VAL x = xseg.get(a, b+1);
		VAL y = yseg.get(c, d+1);

		long long res = INF;
		if (t == 4) res = -INF;
		long long resnum = 0;
		if (t == 3) {
		  chmin(res, x.minv * y.minv);
		  chmin(res, x.minv * y.maxv);
		  chmin(res, x.maxv * y.minv);
		  chmin(res, x.maxv * y.maxv);
		}
		else {
		  chmax(res, x.minv * y.minv);
		  chmax(res, x.minv * y.maxv);
		  chmax(res, x.maxv * y.minv);
		  chmax(res, x.maxv * y.maxv);
		}
		if (res == 0) {
		  long long xnonzero = b - a + 1;
		  if (x.minv == 0) xnonzero -= x.minnum;
		  else if (x.maxv == 0) xnonzero -= x.maxnum;
		  long long ynonzero = d - c + 1;
		  if (y.minv == 0) ynonzero -= y.minnum;
		  else if (y.maxv == 0) ynonzero -= y.maxnum;
		  resnum = (b-a+1) * (d-c+1) - xnonzero * ynonzero;
		}
		else {
		  if (res == x.minv * y.minv) resnum += x.minnum * y.minnum;
		  if (res == x.maxv * y.minv && x.maxv != x.minv)
			resnum += x.maxnum * y.minnum;
		  if (res == x.minv * y.maxv && y.maxv != y.minv)
			resnum += x.minnum * y.maxnum;
		  if (res == x.maxv * y.maxv && x.maxv != x.minv && y.maxv != y.minv)
			resnum += x.maxnum * y.maxnum;
		}

		cout << res << " " << resnum << endl;
	  }

	  /*
	  COUT("----------");
	  COUT(q);
	  xseg.print();
	  yseg.print();
	  */
	  
	}
  }
}