有一个 $n$ 列 $n$ 行的棋盘，总共有 $n \times n$ 个方格。列和行从 1 开始编号，第 $i$ 列第 $j$ 行的方格坐标记为 $(i, j)$。现在，你需要在这个棋盘上执行 $q$ 次操作。

操作共有三种类型：

• 用 Little Sign 标记一条水平线。具体来说，给定两个方格 $(x_1, y_1)$ 和 $(x_2, y_2)$，保证 $y_1 = y_2$，用 Little Sign 标记这两个方格之间的所有方格（包含这两个方格）。
• 用 Cyan Sign 标记一条垂直线。具体来说，给定两个方格 $(x_1, y_1)$ 和 $(x_2, y_2)$，保证 $x_1 = x_2$，用 Cyan Sign 标记这两个方格之间的所有方格（包含这两个方格）。
• 用 Fish Sign 标记一条对角线。具体来说，给定两个方格 $(x_1, y_1)$ 和 $(x_2, y_2)$，保证 $x_2 - x_1 = y_2 - y_1$，用 Fish Sign 标记这两个方格之间的所有方格（包含这两个方格）。

现在，你想要计算在 $q$ 次涂色操作后，棋盘上所有同时拥有三种标记（Little, Cyan, Fish）的方格 $(x, y)$ 的 $a_x \cdot b_y$ 之和，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含两个正整数 $n$ 和 $q$：棋盘的大小和涂色操作的次数（$1 \le n, q \le 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < 998\,244\,353$）。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \le b_i < 998\,244\,353$）。

接下来的 $q$ 行，每行包含四个正整数：$x_1, y_1, x_2, y_2$（$1 \le x_1, x_2, y_1, y_2 \le n$；$(x_1, y_1) \neq (x_2, y_2)$），其中 $x_1, y_1, x_2, y_2$ 表示涂色操作的四个参数。保证每次给定的操作都属于上述三种类型之一。

输出格式

输出一行，包含一个整数，即问题的答案对 $998\,244\,353$ 取模的结果。

样例

输入 1

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

输出 1

9