#P18283. Little, Cyan, Fish!

Little, Cyan, Fish!

Little, Cyan, Fish!

有一个 nn 列、nn 行的棋盘,共 n×nn\times n 个格子。列和行均从 11 开始编号;第 xx 列、第 yy 行的格子记为 (x,y)(x,y)。

你需要依次进行 qq 次标记操作。操作有以下三种:

  • Little 标记:给定两个满足 y1=y2y_1=y_2 的格子 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2),为它们之间的所有格子添加 Little 标记。
  • Cyan 标记:给定两个满足 x1=x2x_1=x_2 的格子 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2),为它们之间的所有格子添加 Cyan 标记。
  • Fish 标记:给定两个满足 x2−x1=y2−y1x_2-x_1=y_2-y_1 的格子 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2),为它们之间斜线上的所有格子添加 Fish 标记。

所有操作都包含两个端点。两个端点互不相同,但可以反向给出。重复添加同一种标记不会增加该种标记的数量。

完成所有操作后,求所有同时拥有 Little、Cyan、Fish 三种标记的格子 (x,y)(x,y) 的 axbya_x b_y 之和,对 998244353998244353 取模。

输入格式

第一行包含两个正整数 n,qn,q(1≤n,q≤1051\le n,q\le10^5),表示棋盘边长和操作次数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai<9982443530\le a_i<998244353)。

第三行包含 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n(0≤bi<9982443530\le b_i<998244353)。

接下来 qq 行,每行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2(1≤x1,x2,y1,y2≤n1\le x_1,x_2,y_1,y_2\le n,(x1,y1)≠(x2,y2)(x_1,y_1)\ne(x_2,y_2)),描述一次操作。保证它属于上述三种类型中的一种,类型由两个端点的坐标确定。

输出格式

输出一行一个整数,表示答案对 998244353998244353 取模的结果。

样例

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