题目描述

给定两张都是 $n$ 个点，$m$ 条边的图 $G_1,G2$，点有点权，设 $f{t}(u,v)$ 表示第 $t$ 张图，从 $u$ 到 $v$ 的所有简单路径中，权值最小的简单路径

一个简单路径的权值定义为经过的点的权值最小值

求：

$$ \sum_{1 \le i < j \le n} f_1(i,j) \times f_2(i,j) $$

输入格式

第一行两个整数 $n,m$

之后一行 $n$ 个整数，表示第一张图的点权 $v{1,1},v{1,2},v{1,3},\cdots,v{1,n}$

之后一共 $m$ 行，每行两个整数 $u,v$，表示第一张图的 $u,v$ 有一条无向边

之后一行 $n$ 个整数，表示第二张图的点权 $v{2,1},v{2,2},v{2,3},\cdots,v{2,n}$

之后一共 $m$ 行，每行两个整数 $u,v$，表示第二张图的 $u,v$ 有一条无向边

输出格式

一行一个整数表示答案模 $998244353$ 意义下的值

样例

input

5 4
6 6 6 8 2
2 1
3 2
4 3
5 2
1 4 4 3 9
2 1
3 2
4 1
5 1

output

62

数据范围与提示

保证两个图都是连通图，且 $1 \le n \le 10^5, n-1 \le m \le 10^6,1 \le v \le 10^6$

感谢 @liuzhangfeiabc 提供的测试点 $6 \sim 10$