军团的阵列线

题目信息

时间限制: 1s

空间限制: 256M

输入文件: team.in

输出文件: team.out

题目描述

众所周知，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 军团长需要知道三列阵线的综合战斗力，不过因为这个值很大，所以对 $\mod 2^{32}$ 取模即可。

输入格式

第一行一个整数 $n$。

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

输出格式

一行一个数表示答案。

样例

样例输入

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

样例输出

60

数据范围与提示

本题采用子任务评测，你需要通过子任务内所有测试点才可以获得对应的分数。

• 对于 $20\%$ 的数据，满足 $1\le n\le 2\times 10^3$。
• 对于另外 $20\%$ 的数据，满足 $A,B,C$ 序列分别单调不减。
• 对于另外 $10\%$ 的数据，满足 $A$ 序列均为 $1$。
• 对于 $100\%$ 的数据，满足 $1\le n\le 10^5$，$1\le A_i,B_i,C_i\le 10^9$。