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:
#ifndef VS
#include<bits/stdc++.h>
#endif

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};

constexpr int INF = 1e7;
template<typename SEG> using SetInitialLeaf = function<void(SEG&, int)>;
template<typename SEG> using SetInitialSegment = function<void(SEG&, const int, const int)>;
template<typename RET, typename SEG> using GetSingleSegment = function<RET(SEG&, const int, const int)>;
template<typename RET> using GetMergedSegment = function<RET(RET, RET)>;
template<typename SEG, typename Q> using UpdateSingleSegment = function<void(SEG&, Q)>;
template<typename SEG> using LazyUpdate = function<void(SEG&, SEG&, SEG&)>;
template<typename T>
struct BufferManager {
	T *mem;
	int ptr;
	BufferManager(T* buf) {
		ptr = 0;
		mem = buf;
	}
	T* get(int m) {
		ptr += m;
		return mem + ptr - m;
	}
	void reset() {
		ptr = 0;
	}
};
struct val {
	LL value, count;
};
struct result {
	val maxi, mini;
};
struct node {
	result ret;
	LL add_value;
};
namespace NodeBuffer {
	constexpr int BufferSize = 812345;
	using NodeType = node;
	NodeType mem[BufferSize];
	BufferManager<NodeType> buffer(mem);
}

template<typename Node, typename RET>
struct SegmentTree {
	int size;
	Node *seg;
	GetSingleSegment<RET, Node> get_single_segment;
	GetMergedSegment<RET> get_merged_segment;
	LazyUpdate<Node> lazy_update;
	void init(int l, int r, SetInitialSegment<Node>& init_segment, SetInitialLeaf<Node>& init_leaf, int k = 0) {
		auto &v = seg[k];
		init_segment(v, l, r);
		if (r - l == 1) {
			//葉の時の処理
			init_leaf(v, l);
		}
		else if (r - l>1) {
			int m = (l + r) / 2;
			init(l, m, init_segment, init_leaf, k * 2 + 1);
			init(m, r, init_segment, init_leaf, k * 2 + 2);
			v.ret = get_merged_segment(
				get_single_segment(seg[k * 2 + 1], l, m),
				get_single_segment(seg[k * 2 + 2], m, r)
			);
		}
	}
	SegmentTree(
		int n,
		GetSingleSegment<RET, Node> gss,
		GetMergedSegment<RET> gms,
		SetInitialSegment<Node> sis,
		SetInitialLeaf<Node> sil,
		LazyUpdate<Node> lu,
		BufferManager<Node>& buf = NodeBuffer::buffer
	)
		:get_single_segment(gss),
		get_merged_segment(gms),
		lazy_update(lu) {
		size = 1; while (size<n)size *= 2;
		seg = buf.get(size * 2 + 10);
		init(0, size, sis, sil);
	}
#define LQ a,b,k*2+1,l,m
#define RQ a,b,k*2+2,m,r
	RET get(int a, int b, int k, int l, int r) {
		if (a <= l && r <= b)
			return get_single_segment(seg[k], l, r);
		if (r - l > 1)lazy_update(seg[k], seg[2 * k + 1], seg[2 * k + 2]);
		int m = (l + r) / 2;
		bool ll = !(m <= a || b <= l);
		bool rr = !(r <= a || b <= m);
		RET ret;
		if (ll&&rr)ret = get_merged_segment(get(LQ), get(RQ));
		else if (ll)ret = get(LQ); else ret = get(RQ);
		seg[k].ret = get_merged_segment(
			get_single_segment(seg[k * 2 + 1], l, m),
			get_single_segment(seg[k * 2 + 2], m, r)
		);
		return ret;
	}
	RET get(int a, int b) {
		return get(a, b, 0, 0, size);
	}
	template<typename Q>
	void update(int a, int b, int k, int l, int r, UpdateSingleSegment<Node, Q> &update_segment, Q value) {
		if (r <= a || b <= l)return;
		if (a <= l && r <= b) {
			update_segment(seg[k], value);
		}
		else {
			if (r - l > 1)lazy_update(seg[k], seg[2 * k + 1], seg[2 * k + 2]);
			int m = (l + r) / 2;
			update(LQ, update_segment, value);
			update(RQ, update_segment, value);
			seg[k].ret = get_merged_segment(
				get_single_segment(seg[k * 2 + 1], l, m),
				get_single_segment(seg[k * 2 + 2], m, r)
			);
		}
	}
	template<typename Q>
	void update_segment(int a, int b, UpdateSingleSegment<Node, Q> &update_segment, Q value) {
		update(a, b, 0, 0, size, update_segment, value);
	}

	template<typename Q>
	void update_element(int a, UpdateSingleSegment<Node, Q> &update_segment, Q value) {
		update(a, a + 1, 0, 0, size, update_segment, value);
	}
};

int R, C, Q;
LL A[112345];
LL B[112345];
int main() {
	while (cin >> R >> C >> Q) {
		for (int i : range(R))cin >> A[i];
		for (int i : range(C))cin >> B[i];
		SegmentTree<node,result> latte(R ,
			[](node &v, const int l, const int r) {
				return result{
					val{ v.ret.maxi.value + v.add_value, v.ret.maxi.count },
					val{ v.ret.mini.value + v.add_value, v.ret.mini.count }
				}; },
			[](result l, result r) {
				return result{
					l.maxi.value == r.maxi.value ?
					val{l.maxi.value,l.maxi.count + r.maxi.count } :
					(l.maxi.value > r.maxi.value ? l.maxi : r.maxi) ,
					l.mini.value == r.mini.value ?
					val{ l.mini.value,l.mini.count + r.mini.count } :
					(l.mini.value < r.mini.value ? l.mini : r.mini)
				}; },
			[](node &v, const int l, const int r) {v.add_value = 0; },
			[&](node &v, const int id) {v.ret.maxi = v.ret.mini = val{ A[id],1ll }; },
			[](node &v, node &l, node &r) {
				l.add_value += v.add_value;
				r.add_value += v.add_value;
				v.add_value = 0;
			}
		);
		SegmentTree<node, result> malta(C,
			[](node &v, const int l, const int r) {
				return result{
					val{ v.ret.maxi.value + v.add_value, v.ret.maxi.count },
					val{ v.ret.mini.value + v.add_value, v.ret.mini.count }
				}; },
			[](result l, result r) {
				return result{
					l.maxi.value == r.maxi.value ?
					val{ l.maxi.value,l.maxi.count + r.maxi.count } :
					(l.maxi.value > r.maxi.value ? l.maxi : r.maxi) ,
					l.mini.value == r.mini.value ?
					val{ l.mini.value,l.mini.count + r.mini.count } :
					(l.mini.value < r.mini.value ? l.mini : r.mini)
				}; },
				[](node &v, const int l, const int r) {v.add_value = 0; },
				[&](node &v, const int id) {v.ret.maxi = v.ret.mini = val{ B[id],1ll }; },
				[](node &v, node &l, node &r) {
					l.add_value += v.add_value;
					r.add_value += v.add_value;
					v.add_value = 0; 
				}
		);
		UpdateSingleSegment<node, int> add_query = [](node &v, int value) {
			v.add_value += value;
		};
		for (int q : range(Q)) {
			cin >> q;
			if (q == 1) {
				int a, b, c;
				cin >> a >> b >> c;
				latte.update_segment(a - 1, b, add_query, c);
			}
			else if (q == 2) {
				int a, b, c;
				cin >> a >> b >> c;
				malta.update_segment(a - 1, b, add_query, c);
			}
			else if (q == 3) {
				int a, b, c, d;
				cin >> a >> b >> c >> d; a--; c--;
				auto l = latte.get(a, b);
				auto r = malta.get(c, d);
				LL min_value = min({
					l.mini.value*r.mini.value,
					l.maxi.value*r.mini.value,
					l.mini.value*r.maxi.value,
					l.maxi.value*r.maxi.value
					});
				LL count = 0;
				if (min_value == 0) {
					LL lx = b - a, rx = d - c;
					LL lc = 0, rc = 0;
					if (l.mini.value == 0)lc = l.mini.count;
					if (l.maxi.value == 0)lc = l.maxi.count;
					if (r.mini.value == 0)rc = r.mini.count;
					if (r.maxi.value == 0)rc = r.maxi.count;
					count = lx * rx - (lx - lc)*(rx - rc);
				}
				else {
					if (l.mini.value == l.maxi.value && r.mini.value == r.maxi.value) {
						count = (b - a) * 1ll * (d - c);
					}
					else if (l.mini.value == l.maxi.value || r.mini.value == r.maxi.value) {
						if (l.mini.value*r.mini.value == min_value)count += l.mini.count*r.mini.count;
						if (l.maxi.value*r.maxi.value == min_value)count += l.maxi.count*r.maxi.count;
					}
					else {
						if (l.mini.value*r.mini.value == min_value)count += l.mini.count*r.mini.count;
						if (l.maxi.value*r.mini.value == min_value)count += l.maxi.count*r.mini.count;
						if (l.mini.value*r.maxi.value == min_value)count += l.mini.count*r.maxi.count;
						if (l.maxi.value*r.maxi.value == min_value)count += l.maxi.count*r.maxi.count;
					}
				}
				cout << min_value << " " << count << "\n";
			}
			else if (q == 4) {
				int a, b, c, d;
				cin >> a >> b >> c >> d; a--; c--;
				auto l = latte.get(a, b);
				auto r = malta.get(c, d);
				LL max_value = max({
					l.mini.value*r.mini.value,
					l.maxi.value*r.mini.value,
					l.mini.value*r.maxi.value,
					l.maxi.value*r.maxi.value
					});
				LL count = 0;
				if (max_value == 0) {
					LL lx = b - a, rx = d - c;
					LL lc = 0, rc = 0;
					if (l.mini.value == 0)lc = l.mini.count;
					if (l.maxi.value == 0)lc = l.maxi.count;
					if (r.mini.value == 0)rc = r.mini.count;
					if (r.maxi.value == 0)rc = r.maxi.count;
					count = lx * rx - (lx - lc)*(rx - rc);
				}
				else {
					if (l.mini.value == l.maxi.value && r.mini.value == r.maxi.value) {
						count = (b - a) * 1ll * (d - c);
					}
					else if (l.mini.value == l.maxi.value || r.mini.value == r.maxi.value) {
						if (l.mini.value*r.mini.value == max_value)count += l.mini.count*r.mini.count;
						if (l.maxi.value*r.maxi.value == max_value)count += l.maxi.count*r.maxi.count;
					}
					else {
						if (l.mini.value*r.mini.value == max_value)count += l.mini.count*r.mini.count;
						if (l.maxi.value*r.mini.value == max_value)count += l.maxi.count*r.mini.count;
						if (l.mini.value*r.maxi.value == max_value)count += l.mini.count*r.maxi.count;
						if (l.maxi.value*r.maxi.value == max_value)count += l.maxi.count*r.maxi.count;
					}
				}
				cout << max_value << " " << count << "\n";
			}
		}

		NodeBuffer::buffer.reset();
	}
}