Biologist Little T is currently researching the synthesis of gene strings, where a gene string is defined as a string over the alphabet {A, C, G, T}.

For a research task, the objects are three gene strings $X$, $Y$, and $Z$. Little T selects an arbitrary contiguous substring $X_1$ from $X$, an arbitrary contiguous substring $Y_1$ from $Y$, and an arbitrary contiguous substring $Z_1$ from $Z$, and then concatenates them in order to obtain $X_1 + Y_1 + Z_1$. Let $f(X, Y, Z)$ be the number of distinct gene strings that can be formed in this way. (Note that any of the aforementioned arbitrary contiguous substrings can be an empty string.)

Little T now has three gene strings $A$, $B$, and $C$, each of length $n$, and $Q$ research tasks. Each task is described by six positive integers $A_l$, $A_r$, $B_l$, $B_r$, $C_l$, and $C_r$, representing the need to calculate the value of $f(A[A_l:A_r], B[B_l:B_r], C[C_l:C_r]) \bmod 998244353$.

Input

The first line contains two positive integers $n$ and $Q$.

The next three lines each contain a string of length $n$ consisting of characters from {A, C, G, T}, representing the gene strings $A$, $B$, and $C$ respectively.

The next $Q$ lines each contain six positive integers $A_l$, $A_r$, $B_l$, $B_r$, $C_l$, and $C_r$, describing a query.

Output

Output $Q$ lines, each containing a non-negative integer representing the answer.

Examples

Input 1

2 1
AC
CC
AA
1 2 1 2 1 1

Output 1

15

Input 2

3 1
ACG
GCA
TTT
1 3 1 3 2 1

Output 2

35

Note

If $l > r$, then $S[l:r]$ is an empty string, and an empty string is a contiguous substring of any string.

Constraints

• For 100% of the data, $n, Q \leq 10^5$, $1 \leq A_l, A_r, B_l, B_r, C_l, C_r \leq n$.
• Constraint 1 is defined as: for all queries, $B_l > B_r$ and $C_l > C_r$.
• Constraint 2 is defined as: for all queries, $C_l > C_r$.