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 <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

using P = pair<ll, ll>;

P mergema(P a, P b) {
    if (a.first > b.first) return a;
    if (a.first < b.first) return b;
    a.second += b.second;
    return a;
}

P mergemi(P a, P b) {
    if (a.first < b.first) return a;
    if (a.first > b.first) return b;
    a.second += b.second;
    return a;
}

struct Node {
    using NP = Node*;
    int sz;
    NP l, r;

    P mi, ma;
    ll lz;
    void update() {
        mi = mergemi(l->mi, r->mi);
        ma = mergema(l->ma, r->ma);
    }
    void push() {
        if (lz == 0) return;
        l->lzdata(lz);
        r->lzdata(lz);
        lz = 0;
    }
    void lzdata(ll x) {
        lz += x;
        mi.first += x;
        ma.first += x;
    }
    
    Node(int sz, ll fi[]) : sz(sz) {
        lz = 0;
        if (sz == 1) {
            mi = ma = P(fi[0], 1);
            return;
        }
        l = new Node(sz/2, fi);
        r = new Node(sz-sz/2, fi+sz/2);
        update();
    }

    void add(int a, int b, ll x) {
        if (b <= 0 || sz <= a) return;
        if (a <= 0 && sz <= b) {
            lzdata(x);
            return;
        }
        push();
        l->add(a, b, x);
        r->add(a-sz/2, b-sz/2, x);
        update();
    }

    P getma(int a, int b) {
        if (b <= 0 || sz <= a) return P(-TEN(18), 0);
        if (a <= 0 && sz <= b) {
            return ma;
        }
        push();
        P pl = l->getma(a, b);
        P pr = r->getma(a-sz/2, b-sz/2);
        return mergema(pl, pr);
    }


    P getmi(int a, int b) {
        if (b <= 0 || sz <= a) return P(TEN(18), 0);
        if (a <= 0 && sz <= b) {
            return mi;
        }
        push();
        P pl = l->getmi(a, b);
        P pr = r->getmi(a-sz/2, b-sz/2);
        return mergemi(pl, pr);
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20);

    int h, w, q;
    cin >> h >> w >> q;
    V<ll> a(h), b(w);
    for (int i = 0; i < h; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < w; i++) {
        cin >> b[i];
    }

    auto tra = new Node(h, a.data());
    auto trb = new Node(w, b.data());

    for (int ph = 0; ph < q; ph++) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int a, b; ll v;
            cin >> a >> b >> v; a--;
            tra->add(a, b, v);
        } else if (ty == 2) {
            int a, b; ll v;
            cin >> a >> b >> v; a--;
            trb->add(a, b, v);
        } else if (ty == 3) {
            int a, b, c, d;
            cin >> a >> b >> c >> d; a--; c--;
            P pami = tra->getmi(a, b);
            P pbmi = trb->getmi(c, d);
            P pama = tra->getma(a, b);
            P pbma = trb->getma(c, d);


            P ans = P(TEN(18), 0);

            for (int f = 0; f <= 1; f++) {
                if (f && pami.first == pama.first) continue;
                P pa = (!f) ? pami : pama;
                for (int g = 0; g <= 1; g++) {
                    if (g && pbmi.first == pbma.first) continue;
                    P pb = (!g) ? pbmi : pbma;
                    ans = mergemi(ans, P(pa.first * pb.first, pa.second * pb.second));
                }
            }
            
            if (ans.first == 0) {
                ll za = 0, zb = 0;
                if (pami.first == 0) za = pami.second;
                else if (pama.first == 0) za = pama.second;
                if (pbmi.first == 0) zb = pbmi.second;
                else if (pbma.first == 0) zb = pbma.second;

                ans.second = za * (d-c) + zb * (b-a) - za * zb;
            }
            cout << ans.first << " " << ans.second << endl;
        } else {
            int a, b, c, d;
            cin >> a >> b >> c >> d; a--; c--;
            P pami = tra->getmi(a, b);
            P pbmi = trb->getmi(c, d);
            P pama = tra->getma(a, b);
            P pbma = trb->getma(c, d);

            P ans = P(-TEN(18), 0);

            for (int f = 0; f <= 1; f++) {
                if (f && pami.first == pama.first) continue;
                P pa = (!f) ? pami : pama;
                for (int g = 0; g <= 1; g++) {
                    if (g && pbmi.first == pbma.first) continue;
                    P pb = (!g) ? pbmi : pbma;
                    ans = mergema(ans, P(pa.first * pb.first, pa.second * pb.second));
                }
            }

            if (ans.first == 0) {
                ll za = 0, zb = 0;
                if (pami.first == 0) za = pami.second;
                else if (pama.first == 0) za = pama.second;
                if (pbmi.first == 0) zb = pbmi.second;
                else if (pbma.first == 0) zb = pbma.second;

                ans.second = za * (d-c) + zb * (b-a) - za * zb;
            }

            cout << ans.first << " " << ans.second << endl;
        }
    }
    return 0;
}