You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

众所周知，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

大样例

dbig.in
dbig.out

数据范围与提示

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

• 对于 $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$。