Matrix

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

inputFormat

outputFormat

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

样例

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

4 1
9 1
1 1
1 1
2 2
12 1

</p>