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 <vector>
#include <algorithm>
using namespace std;

class SegmentTree {
public:
	vector<int>dat, mx, num, sum; int B = 350;

	void init(int size_) {
		size_ += B; size_ /= B; size_ *= B;
		dat.resize(size_, 0);
		sum.resize(size_ / B, 0);
		mx.resize(size_ / B, 0);
		num.resize(size_ / B, 0);
	}
	void naive_add(int a, int b, int x) {
		for (int i = a; i <= b; i++) {
			dat[i] += x;
		}
		int id = a / B; mx[id] = -1000000007; num[id] = 0;
		for (int i = id*B; i < (id + 1)*B; i++) mx[id] = max(mx[id], dat[i]);
		for (int i = id*B; i < (id + 1)*B; i++) { if (mx[id] == dat[i]) num[id]++; }
	}
	void add(int a, int b, int x) {
		// 閉区間でやりたい
		if (a / B == b / B) naive_add(a, b, x);
		else {
			naive_add(a, (a / B + 1)*B - 1, x);
			naive_add((b / B)*B, b, x);
			for (int i = (a / B) + 1; i < b / B; i++) {
				sum[i] += x;
			}
		}
	}
	int naive_max(int a, int b) {
		int ret1 = -(1 << 30), id = a / B;
		for (int i = a; i <= b; i++) {
			ret1 = max(ret1, dat[i] + sum[id]);
		}
		return ret1;
	}
	int naive_sum(int a, int b, int x) {
		int ret2 = 0, id = a / B;
		for (int i = a; i <= b; i++) {
			if (dat[i] + sum[id] == x) ret2++;
		}
		return ret2;
	}
	pair<int, int> query(int a, int b) {
		if (a / B == b / B) {
			int G = naive_max(a, b);
			int I = naive_sum(a, b, G);
			return make_pair(G, I);
		}
		else {
			int L1 = a / B + 1, R1 = b / B;
			int G1 = naive_max(a, L1*B - 1); int I1 = naive_sum(a, L1*B - 1, G1);
			int G2 = naive_max(R1*B, b); int I2 = naive_sum(R1*B, b, G2);

			int maxn = max(G1, G2), sum2 = 0;
			if (G1 == maxn) sum2 += I1;
			if (G2 == maxn) sum2 += I2;
			for (int i = L1; i < R1; i++) {
				if (mx[i] + sum[i] > maxn) {
					maxn = mx[i] + sum[i];
					sum2 = num[i];
				}
				else if (mx[i] + sum[i] == maxn) {
					sum2 += num[i];
				}
			}
			return make_pair(maxn, sum2);
		}
	}
};

long long H, W, Q, A[100009], B[100009];

int main() {
	cin >> H >> W >> Q;
	SegmentTree X1, X2, Y1, Y2;
	X1.init(H + 2); X2.init(W + 2);
	Y1.init(H + 2); Y2.init(W + 2);

	for (int i = 1; i <= H; i++) { cin >> A[i]; X1.add(i, i, A[i]); Y1.add(i, i, -A[i]); }
	for (int i = 1; i <= W; i++) { cin >> B[i]; X2.add(i, i, B[i]); Y2.add(i, i, -B[i]); }

	for (int i = 1; i <= Q; i++) {
		long long q, a, b, c, d;
		cin >> q;
		if (q == 1) {
			cin >> a >> b >> c;
			X1.add(a, b, c);
			Y1.add(a, b, -c);
		}
		if (q == 2) {
			cin >> a >> b >> c;
			X2.add(a, b, c);
			Y2.add(a, b, -c);
		}
		if (q == 3) {
			cin >> a >> b >> c >> d;
			pair<long long, long long> E1 = X1.query(a, b);
			pair<long long, long long> F1 = X2.query(c, d);
			pair<long long, long long> E2 = Y1.query(a, b); E2.first *= -1;
			pair<long long, long long> F2 = Y2.query(c, d); F2.first *= -1;

			long long minx = min({ E1.first*F1.first,E2.first*F1.first,E1.first*F2.first,E2.first*F2.first });
			long long sum1 = 0;
			if (E1.first*F1.first == minx) sum1 += E1.second*F1.second;
			if (E2.first*F1.first == minx && E1.first != E2.first) sum1 += E2.second*F1.second;
			if (E1.first*F2.first == minx && F1.first != F2.first) sum1 += E1.second*F2.second;
			if (E2.first*F2.first == minx && E1.first != E2.first && F1.first != F2.first) sum1 += E2.second*F2.second;

			if (minx != 0) {
				cout << minx << " " << sum1 << endl;
			}
			if (minx == 0) {
				sum1 = 0;
				long long V1 = 0, V2 = 0;
				if (E1.first == 0) V1 += E1.second;
				if (E2.first == 0 && E1.first != E2.first) V1 += E2.second;
				if (F1.first == 0) V2 += F1.second;
				if (F2.first == 0 && F1.first != F2.first) V2 += F2.second;

				sum1 += V1*(d - c + 1);
				sum1 += (b - a + 1)*V2;
				sum1 -= V1*V2;
				cout << minx << " " << sum1 << endl;
			}
		}
		if (q == 4) {
			cin >> a >> b >> c >> d;
			pair<long long, long long> E1 = X1.query(a, b);
			pair<long long, long long> F1 = X2.query(c, d);
			pair<long long, long long> E2 = Y1.query(a, b); E2.first *= -1;
			pair<long long, long long> F2 = Y2.query(c, d); F2.first *= -1;

			long long maxn = max({ E1.first*F1.first,E2.first*F1.first,E1.first*F2.first,E2.first*F2.first });
			long long sum1 = 0;
			if (E1.first*F1.first == maxn) sum1 += E1.second*F1.second;
			if (E2.first*F1.first == maxn && E1.first != E2.first) sum1 += E2.second*F1.second;
			if (E1.first*F2.first == maxn && F1.first != F2.first) sum1 += E1.second*F2.second;
			if (E2.first*F2.first == maxn && E1.first != E2.first && F1.first != F2.first) sum1 += E2.second*F2.second;

			if (maxn != 0) {
				cout << maxn << " " << sum1 << endl;
			}
			if (maxn == 0) {
				sum1 = 0;
				long long V1 = 0, V2 = 0;
				if (E1.first == 0) V1 += E1.second;
				if (E2.first == 0 && E1.first != E2.first) V1 += E2.second;
				if (F1.first == 0) V2 += F1.second;
				if (F2.first == 0 && F1.first != F2.first) V2 += F2.second;

				sum1 += V1*(d - c + 1);
				sum1 += (b - a + 1)*V2;
				sum1 -= V1*V2;
				cout << maxn << " " << sum1 << endl;
			}
		}
	}
	return 0;
}