Biolog T. zajmuje się ostatnio badaniem syntetycznych nici genetycznych. Nić genetyczna to ciąg znaków ze zbioru {A, C, G, T}.

W ramach jednego badania obiektami są 3 nici genetyczne $X$, $Y$ oraz $Z$. T. wybiera dowolny spójny podciąg $X_1$ z $X$, dowolny spójny podciąg $Y_1$ z $Y$ oraz dowolny spójny podciąg $Z_1$ z $Z$, a następnie łączy je w kolejności, otrzymując $X_1 + Y_1 + Z_1$. Niech $f(X, Y, Z)$ oznacza liczbę różnych nici genetycznych, które można w ten sposób utworzyć. (Uwaga: każdy z powyższych dowolnych spójnych podciągów może być ciągiem pustym).

Obecnie T. posiada 3 nici genetyczne $A$, $B$ oraz $C$ o długości $n$ i przeprowadza $Q$ badań. Każde badanie jest opisane przez 6 liczb całkowitych dodatnich $A_l$, $A_r$, $B_l$, $B_r$, $C_l$, $C_r$, co oznacza, że musi obliczyć wartość $f(A[A_l:A_r], B[B_l:B_r], C[C_l:C_r]) \bmod 998244353$.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite dodatnie $n$ oraz $Q$.

W kolejnych trzech liniach znajdują się trzy nici genetyczne o długości $n$, składające się ze znaków {A, C, G, T}, reprezentujące nici $A$, $B$ oraz $C$.

W kolejnych $Q$ liniach znajduje się po 6 liczb całkowitych dodatnich $A_l$, $A_r$, $B_l$, $B_r$, $C_l$, $C_r$, opisujących pojedyncze zapytanie.

Wyjście

Wypisz $Q$ linii, z których każda zawiera jedną nieujemną liczbę całkowitą będącą wynikiem zapytania.

Przykład

Przykład 1

2 1
AC
CC
AA
1 2 1 2 1 1

Wyjście 1

15

Przykład 2

3 1
ACG
GCA
TTT
1 3 1 3 2 1

Wyjście 2

35

Uwagi

Jeśli $l > r$, to $S[l:r]$ jest ciągiem pustym; ciąg pusty jest spójnym podciągiem ciągu pustego.

Ograniczenia

• Dla 100% danych: $n, Q \leq 10^5$, $1 \leq A_l, A_r, B_l, B_r, C_l, C_r \leq n$.
• Definicja ograniczenia 1: dla wszystkich zapytań $B_l > B_r$ oraz $C_l > C_r$.
• Definicja ograniczenia 2: dla wszystkich zapytań $C_l > C_r$.