問題文

長さが $N$ の数列 $A$ と $B$ が与えられます。

ここで、$N \times N$ の二次元グリッド $S$ を以下のように定義します。

• $S_{i, j} = \max(A_i, B_j)$

クエリが $Q$ 個与えられるので、順番に処理してください。$i$ 番目のクエリは以下の通りです。

• l d r u: $l \leq x \leq r$, $d \leq y \leq u$ を満たす $(x, y)$ の組について、$S_{x, y}$ の総和を出力する。

制約

• $1 \leq N \leq 20000$
• $1 \leq Q \leq 10^{5}$
• $1 \leq A_i, B_i \leq 10^{5}$
• $1 \leq l \leq r \leq N$
• $1 \leq d \leq u \leq N$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$
$\text{query}_{1}$  
$\text{query}_{2}$  
$\vdots$

$\text{query}_{Q}$ 

各クエリは以下に示す形式で与えられる。

$l$ $d$ $r$ $u$

出力

$Q$ 行出力せよ。

$i$ 行目には、$i$ 番目のクエリに対する答えを出力せよ。

サンプル

5 4
8 6 2 4 1
2 3 5 7 11
2 3 3 4
4 2 5 4
1 1 3 3
1 1 5 5

25
31
52
166