集合

本题是对 NOI2024 "集合" 的严格加强.

题面描述上, 原题和本题唯一区别是: 原题只需查询是否存在一个排列符合条件, 但是本题查询符合条件的排列的数量.

题目描述

小 Y 和小 S 在玩一个游戏。

给定正整数 $m$，定义基本集合为大小为 $3$，元素在 $1\sim m$ 内的集合。例如：给定 $m=4$，则集合 $\{1,2,3\}$ 与集合 $\{2,3,4\}$ 都是基本集合。

定义集合序列为由基本集合构成的序列，例如，$A=[\{1,2,3\},\{2,3,4\}]$ 是一个集合序列，其中 $A[1]=\{1,2,3\}$，$A[2]=\{2,3,4\}$ 都是基本集合。

对于一个 $1\sim m$ 的排列 $p[1],p[2],\dots,p[m]$ 与集合 $S\subseteq \{1,2,\dots,m\}$，定义 $f_p(S)$ 为将 $S$ 内每一个元素 $x$ 置换为 $p[x]$ 后所得到的集合，即 $f_p(S)=\{p[x]|x\in S\}$。

有 $q$ 次询问，每次询问给出 $l,r$, 请你求出，有多少个 $1\sim m$ 的排列 $p$，使得在区间 $[l,r]$ 中， $A$ 置换排列 $p$ 后可以得到 $B$，即对于所有 $l\leq i\leq r$，$f_p(A[i])=B[i]$。

时光荏苒，小 S 和小 Y 也会散去。而我们和一个人保持连接的方式就是记住，仅此而已。

输入格式

输入的第一行包含三个正整数 $n,m,q$，分别表示集合序列的长度，元素范围和询问次数。

输入的第二行包含 $3n$ 个正整数，第 $3i-2,3i-1,3i$（$1\leq i\leq n$）个正整数分别表示 $A[i]$ 的三个元素。保证这三个元素均在 $[1,m]$ 范围内且互不相同。

输入的第三行包含 $3n$ 个正整数，第 $3i-2,3i-1,3i$（$1\leq i\leq n$）个正整数分别表示 $B[i]$ 的三个元素。保证这三个元素均在 $[1,m]$ 范围内且互不相同。

接下来 $q$ 行，每行包含两个正整数 $l,r$，表示一次询问。

输出格式

输出 $q$ 行，每行包含一个整数，表示满足条件的排列个数模 $998244353$ 意义下的结果。

样例 #1

样例输入 #1

4 4 10
1 2 3 1 2 3 1 2 4 1 2 3
1 2 4 2 3 4 1 2 3 2 3 4
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

样例输出 #1

6
0
0
0
6
2
2
6
2
6

提示

对于样例1的解释：

以下用 $(l,r)$ 表示对 $l,r$ 的询问：

• 对于询问 $(1,1)$，排列 $p=[1,2,4,3]$，$p=[1,4,2,3]$，$p=[2,1,4,3]$，$p=[2,4,1,3]$，$p=[4,1,2,3]$，$p=[4,2,1,3]$，时满足条件。
• 对于询问 $(1,2),(1,3),(1,4)$，由于 $A[1]=A[2]$ 但 $B[1]\neq B[2]$，因此这些询问都不存在满足条件的排列。

对于所有测试数据保证：$1\leq n\leq 2\times 10^5$，$3\leq m\leq 6\times 10^5$，$1\leq q\leq 10^6$，$1\leq l\leq r\leq n$。