题目描述

生物学家小 T 最近在研究合成基因串的课题，所谓基因串就是字符集为 {A，C，G，T} 的字符串。
对于一次研究，对象是 3 个基因串 $X$，$Y$，$Z$。小 T 会从 $X$ 中选出一个任意连续子串 $X_1$，从 $Y$ 中选出一个任意连续子串 $Y_1$，从 $Z$ 中选出一个任意连续子串 $Z_1$，然后按顺序拼接它们得到 $X_1 + Y_1 + Z_1$。设 $f(X, Y, Z)$ 为这样能组成多少不同的基因串。（注意以上的任意连续子串都可以是空串）

现在小 T 有 3 个长度为 $n$的基因串 $A$，$B$，$C$ 和 $Q$ 次研究，每次研究由 6 个正整数 $A_l$，$A_r$，$B_l$，$B_r$，$C_l$，$C_r$ 描述，表示她需要求 $f(A[A_l:A_r], B[B_l:B_r], C[C_l:C_r]) \bmod 998244353$ 的值。

输入格式

第一行两个正整数 $n$，$Q$。

接下来三行，每行一个长度为 $n$ 的字符集为 {A，C，G，T} 的字符串，表示基因串 $A$，$B$，$C$。

接下来 $Q$ 行，每行 6 个正整数 $A_l$，$A_r$，$B_l$，$B_r$，$C_l$，$C_r$，描述一次询问。

输出格式

输出 $Q$ 行，每行一个非负整数，表示答案。

样例

样例输入一

2 1
AC
CC
AA
1 2 1 2 1 1

样例输出一

15

样例输入二

3 1
ACG
GCA
TTT
1 3 1 3 2 1

样例输出二

35

样例说明

如果 $l > r$，则 $S[l:r]$ 是空串，空串是空串的连续子串。

限制与约定

• 对于 100% 的数据，有 $n, Q \leq 10^5$，$1 \leq A_l, A_r, B_l, B_r, C_l, C_r \leq n$
• 定义限制 1 为：对于所有询问有 $B_l > B_r$ 且 $C_l > C_r$
• 定义限制 2 为：对于所有询问有 $C_l > C_r$