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;

using int64 = long long;

template< typename Monoid, typename OperatorMonoid = Monoid >
struct LazySegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;
  using G = function< Monoid(Monoid, OperatorMonoid, int) >;
  using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;

  int sz;
  vector< Monoid > data;
  vector< OperatorMonoid > lazy;
  const F f;
  const G g;
  const H h;
  const Monoid M1;
  const OperatorMonoid OM0;


  LazySegmentTree(int n, const F f, const G g, const H h,
                  const Monoid &M1, const OperatorMonoid OM0)
      : f(f), g(g), h(h), M1(M1), OM0(OM0) {
    sz = 1;
    while(sz < n) sz <<= 1;
    data.assign(2 * sz, M1);
    lazy.assign(2 * sz, OM0);
  }

  void set(int k, const Monoid &x) {
    data[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      data[k] = f(data[2 * k + 0], data[2 * k + 1]);
    }
  }

  void propagate(int k, int len) {
    if(lazy[k] != OM0) {
      if(k < sz) {
        lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
        lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      }
      data[k] = g(data[k], lazy[k], len);
      lazy[k] = OM0;
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r) {
    propagate(k, r - l);
    if(r <= a || b <= l) {
      return data[k];
    } else if(a <= l && r <= b) {
      lazy[k] = h(lazy[k], x);
      propagate(k, r - l);
      return data[k];
    } else {
      return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
                         update(a, b, x, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x) {
    return update(a, b, x, 1, 0, sz);
  }


  Monoid query(int a, int b, int k, int l, int r) {
    propagate(k, r - l);
    if(r <= a || b <= l) {
      return M1;
    } else if(a <= l && r <= b) {
      return data[k];
    } else {
      return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),
               query(a, b, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid query(int a, int b) {
    return query(a, b, 1, 0, sz);
  }

  Monoid operator[](const int &k) {
    return query(k, k + 1);
  }
};

const int64 INF = 1LL << 30;
const int64 LINF = 1LL << 62;


struct Tap {
  int64 large, large_count;
  int64 small, small_count;
} e((Tap) {-INF, 0, INF, 0});

int main() {
  int H, W, Q, A[100000], B[100000];
  scanf("%d %d %d", &H, &W, &Q);

  auto f = [](const Tap &x, const Tap &y) {
    Tap z;
    z.small_count = z.large_count = 0;
    z.large = max(x.large, y.large);
    if(z.large == x.large) z.large_count += x.large_count;
    if(z.large == y.large) z.large_count += y.large_count;
    z.small = min(x.small, y.small);
    if(z.small == x.small) z.small_count += x.small_count;
    if(z.small == y.small) z.small_count += y.small_count;
    return z;
  };
  auto g = [](Tap x, int64 v, int len) {
    x.large += v;
    x.small += v;
    return x;
  };
  auto h = [](int64 x, int64 y) {
    return x + y;
  };

  LazySegmentTree< Tap, int64 > latte(H, f, g, h, e, 0), malta(W, f, g, h, e, 0);
  for(int i = 0; i < H; i++) {
    int x;
    scanf("%d", &x);
    latte.set(i, (Tap) {x, 1, x, 1});
  }
  for(int i = 0; i < W; i++) {
    int x;
    scanf("%d", &x);
    malta.set(i, (Tap) {x, 1, x, 1});
  }
  latte.build();
  malta.build();
  while(Q--) {
    int t, a, b, c, d;
    scanf("%d %d %d %d", &t, &a, &b, &c);
    if(t <= 2) {
      --a;
      (t == 1 ? latte : malta).update(a, b, c);
    } else if(t == 4) {
      scanf("%d", &d);
      auto p = latte.query(--a, b), q = malta.query(--c, d);
      int64 ret = -LINF, sum = 0;
      if(p.large > 0 && q.large > 0) {
        ret = p.large * q.large;
        sum = p.large_count * q.large_count;
      }
      if(p.small < 0 && q.small < 0 && p.small * q.small >= ret) {
        if(p.small * q.small > ret) sum = 0;
        ret = p.small * q.small;
        sum += p.small_count * q.small_count;

      }
      if(ret != -LINF) {
        printf("%lld %lld\n", ret, sum);
        continue;
      }

      if(p.small == 0) {
        ret = sum = 0;
        sum += p.small_count * (d - c);
        if(q.small == 0) {
          sum += q.small_count * (b - a);
          sum -= q.small_count * p.small_count;
        } else if(q.large == 0) {
          sum += q.large_count * (b - a);
          sum -= q.large_count * p.small_count;
        }
        printf("%lld %lld\n", ret, sum);
        continue;
      }

      if(p.large == 0) {
        ret = sum = 0;
        sum += p.large_count * (d - c);
        if(q.small == 0) {
          sum += q.small_count * (b - a);
          sum -= q.small_count * p.large_count;
        } else if(q.large == 0) {
          sum += q.large_count * (b - a);
          sum -= q.large_count * p.large_count;
        }
        printf("%lld %lld\n", ret, sum);
        continue;
      }

      if(q.small == 0) {
        ret = sum = 0;
        sum += q.small_count * (b - a);
        printf("%lld %lld\n", ret, sum);
        continue;
      }

      if(q.large == 0) {
        ret = sum = 0;
        sum += q.large_count * (b - a);
        printf("%lld %lld\n", ret, sum);
        continue;
      }

      for(int lattemalta = 0; lattemalta < 2; lattemalta++) {
        swap(p, q);
        if(p.large < 0 && q.small > 0 && p.large * q.small >= ret) {
          if(p.large * q.small > ret) sum = 0;
          ret = p.large * q.small;
          sum += p.large_count * q.small_count;
        }
      }

      printf("%lld %lld\n", ret, sum);

    } else {
      scanf("%d", &d);
      auto p = latte.query(--a, b), q = malta.query(--c, d);
      int64 ret = LINF, sum = 0;

      if(p.small < 0 && q.large > 0 && p.small * q.large <= ret) {
        if(p.small * q.large < ret) sum = 0;
        ret = p.small * q.large;
        sum += p.small_count * q.large_count;
      }

      if(p.large > 0 && q.small < 0 && p.large * q.small <= ret) {
        if(p.large * q.small < ret) sum = 0;
        ret = p.large * q.small;
        sum += p.large_count * q.small_count;
      }

      if(ret != LINF) {
        printf("%lld %lld\n", ret, sum);
        continue;
      }

      if(p.large == 0) {
        ret = sum = 0;
        sum += p.large_count * (d - c);
        if(q.large == 0) {
          sum += q.large_count * (b - a);
          sum -= q.large_count * p.large_count;
        } else if(q.small == 0) {
          sum += q.small_count * (b - a);
          sum -= q.small_count * p.large_count;
        }
        printf("%lld %lld\n", ret, sum);
        continue;
      }

      if(p.small == 0) {
        ret = sum = 0;
        sum += p.small_count * (d - c);
        if(q.large == 0) {
          sum += q.large_count * (b - a);
          sum -= q.large_count * p.small_count;
        } else if(q.small == 0) {
          sum += q.small_count * (b - a);
          sum -= q.small_count * p.small_count;
        }
        printf("%lld %lld\n", ret, sum);
        continue;
      }

      if(q.small == 0) {
        ret = sum = 0;
        sum += q.small_count * (b - a);
        printf("%lld %lld\n", ret, sum);
        continue;
      }

      if(q.large == 0) {
        ret = sum = 0;
        sum += q.large_count * (b - a);
        printf("%lld %lld\n", ret, sum);
        continue;
      }

      if(p.small > 0 && q.small > 0) {
        ret = p.small * q.small;
        sum += p.small_count * q.small_count;
      }

      if(p.large < 0 && q.large < 0 && p.large * q.large <= ret) {
        if(p.large * q.large < ret) sum = 0;
        ret = p.large * q.large;
        sum += p.large_count * q.large_count;
      }
      printf("%lld %lld\n", ret, sum);
    }
  }
}