Little, Cyan, Fish!
有一个 n 列、n 行的棋盘,共 n×n 个格子。列和行均从 1 开始编号;第 x 列、第 y 行的格子记为 (x,y)。
你需要依次进行 q 次标记操作。操作有以下三种:
- Little 标记:给定两个满足 y1=y2 的格子 (x1,y1),(x2,y2),为它们之间的所有格子添加 Little 标记。
- Cyan 标记:给定两个满足 x1=x2 的格子 (x1,y1),(x2,y2),为它们之间的所有格子添加 Cyan 标记。
- Fish 标记:给定两个满足 x2−x1=y2−y1 的格子 (x1,y1),(x2,y2),为它们之间斜线上的所有格子添加 Fish 标记。
所有操作都包含两个端点。两个端点互不相同,但可以反向给出。重复添加同一种标记不会增加该种标记的数量。
完成所有操作后,求所有同时拥有 Little、Cyan、Fish 三种标记的格子 (x,y) 的 axby 之和,对 998244353 取模。
输入格式
第一行包含两个正整数 n,q(1≤n,q≤105),表示棋盘边长和操作次数。
第二行包含 n 个整数 a1,a2,…,an(0≤ai<998244353)。
第三行包含 n 个整数 b1,b2,…,bn(0≤bi<998244353)。
接下来 q 行,每行包含四个整数 x1,y1,x2,y2(1≤x1,x2,y1,y2≤n,(x1,y1)=(x2,y2)),描述一次操作。保证它属于上述三种类型中的一种,类型由两个端点的坐标确定。
输出格式
输出一行一个整数,表示答案对 998244353 取模的结果。
样例
5 3
1 2 3 4 5
1 2 3 4 5
1 3 5 3
3 5 3 1
5 5 1 1
9