在图论的数学学科中，二分图（bipartite graph）是一种无向图，其顶点可以划分为两个不相交的集合 $U$ 和 $V$，使得每一条边都连接 $U$ 中的某个顶点和 $V$ 中的某个顶点。顶点集 $U$ 和 $V$ 都是独立集，通常被称为图的两个部分。等价地，二分图是不包含任何奇数长度环的图。图中的匹配（matching）是一组没有公共顶点的边。完美匹配（perfect matching）是指每个顶点都被匹配中的一条边所覆盖的匹配。

Little Q 误解了二分图的定义。他认为 $U$ 的大小等于 $V$ 的大小，并且对于 $U$ 中的每个顶点 $p$，从 $p$ 出发恰好有两条边。基于这样的加权图，他将完美匹配的权值定义为该匹配中所有边权值的乘积，并将图的权值定义为所有完美匹配权值之和。

你的任务是编写一个程序，计算 Little Q 所构造的加权图的权值。

输入格式

第一行包含一个整数 $n$，表示 $U$ 的大小（$1 \le n \le 3 \cdot 10^5$）。$U$ 和 $V$ 中的顶点分别用整数 $1, 2, \dots, n$ 标记。

接下来的 $n$ 行中，第 $i$ 行包含四个整数 $v_{i,1}, w_{i,1}, v_{i,2}$ 和 $w_{i,2}$，表示存在一条连接 $U_i$ 和 $V_{v_{i,1}}$ 的边，权值为 $w_{i,1}$；以及另一条连接 $U_i$ 和 $V_{v_{i,2}}$ 的边，权值为 $w_{i,2}$（$1 \le v_{i,j} \le n, 1 \le w_{i,j} \le 10^9$）。

保证给定的图至少存在一个完美匹配，且每对顶点之间最多只有一条边。

输出格式

输出一行，包含一个整数：给定图的权值。由于答案可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

样例

输入 1

2
2 1 1 4
1 4 2 3

输出 1

16