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)$ v $ to $

Query 2
$ 2 $ $ c $ $ d $ $ v $
$B_j (c \ leq j \ leq d)$ v $ to $

Query 3
$ 3 $ $ a $ $ b $ $ c $ $ d $
$C_ {i, j} (a \ leq i \ leq b, c \ leq j \ leq d)$ and its number

Query 4
$ 4 $ $ a $ $ b $ $ c $ $ d $
$C_ {i, j} (a \ leq i \ leq b, c \ leq j \ leq d)$ 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

见题面

见题面