生物学者の小 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 は長さ $n$ の 3 つの遺伝子鎖 $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$ の値を求める必要があります。

入力形式

1 行目に 2 つの正整数 $n, Q$ が与えられます。

続く 3 行には、それぞれ長さ $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

注記

$l > r$ の場合、$S[l:r]$ は空文字列であり、空文字列は空文字列の連続部分文字列です。

入力 2

3 1
ACG
GCA
TTT
1 3 1 3 2 1

出力 2

35

制約

• すべてのデータにおいて、$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$