题目描述

众所周知，B 宇宙的 president PT 是位狼灭，听闻 C 舰队往白金虫洞的远征计划后，就在 C 舰队的必经之路部署了 B 宇宙最精锐的 D 军团。

D 军团军团长 U 决定采用三列阵线阻击 C 舰队，U 军团长研究的三列阵线战术可以让 D 军团的综合战斗力大大提升，而不局限于单个士兵的战斗力。三列阵线的战斗力计算过程如下：

• 三列阵线都由 $n$ 个士兵组成，每个士兵的战斗力都是正整数，三列阵线分别为 $A,B,C$。
• 以阵线 $A$ 为例，第 $i$ 个士兵的战斗力为 $A_i$。
• 以阵线 $A$ 为例，区间 $[l,r]$ 的士兵的综合战斗力为 $f(A,l,r)=\max_{i=l}^{r}A_i-\min_{j=l}^{r}A_j$。
• 三列阵线中，区间 $[l,r]$ 的士兵的综合战斗力为 $F(l,r)=f(A,l,r)\times f(B,l,r)\times f(C,l,r)$。
• 三列阵线的综合战斗力为 $\sum_{l=1}^{n}\sum_{r=l}^{n}F(l,r)$。

U 军团长需要知道三列阵线的综合战斗力，不过因为这个值很大，所以对 $2^{32}$ 取模即可。

输入格式

从文件 team.in 中读入数据。

第一行一个整数 $n$。

之后三行，每行 $n$ 个正整数，分别表示 $A,B,C$ 三个序列。

输出格式

输出到文件 team.out 中。

一行一个数表示答案。

样例 1 输入

5
1 3 5 5 5
2 3 2 1 2
3 5 5 3 5

样例 1 输出

60

样例 1 解释

贡献非零的区间为 $[1,2],[1,3],[1,4],[1,5],[2,4],[2,5]$，贡献依次为 $4,8,16,16,8,8$，总和为 $60$。

样例 2

见选手目录下的 team/team2.in 与 team/team2.ans。

该样例满足第 $1\sim4$ 个测试点的限制，$n=2000$。

样例 3

见选手目录下的 team/team3.in 与 team/team3.ans。

该样例满足第 $5\sim8$ 个测试点的限制，$n=10^5$，三个序列分别单调不减。

样例 4

见选手目录下的 team/team4.in 与 team/team4.ans。

该样例满足第 $9\sim10$ 个测试点的限制，$n=10^5$，$A$ 序列均为 $1$。

样例 5

见选手目录下的 team/team5.in 与 team/team5.ans。

该样例满足第 $11\sim20$ 个测试点的限制，$n=10^5$。

数据范围

对于所有测试数据，保证 $1\le n\le10^5$，$1\le A_i,B_i,C_i\le10^9$。

测试点编号	$n\le$	特殊性质
$1\sim4$	$2000$	无
$5\sim8$	$10^5$	$A,B,C$ 三个序列分别单调不减
$9\sim10$		$A$ 序列均为 $1$
$11\sim20$		无

本题共 $20$ 个测试点，每个测试点 $5$ 分，按测试点独立计分