生物學家小 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$ 行，每行一個非負整數，表示答案。

範例

範例輸入 1

2 1
AC
CC
AA
1 2 1 2 1 1

範例輸出 1

15

範例輸入 2

3 1
ACG
GCA
TTT
1 3 1 3 2 1

範例輸出 2

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$