Биолог Т. изучает синтетические генные последовательности. Генная последовательность — это строка, состоящая из символов {A, C, G, T}.

В рамках одного исследования рассматриваются три генные последовательности $X$, $Y$ и $Z$. Т. выбирает произвольную непрерывную подстроку $X_1$ из $X$, произвольную непрерывную подстроку $Y_1$ из $Y$ и произвольную непрерывную подстроку $Z_1$ из $Z$, а затем объединяет их в порядке следования, получая $X_1 + Y_1 + Z_1$. Пусть $f(X, Y, Z)$ — количество различных генных последовательностей, которые можно получить таким образом. (Заметьте, что любая из выбранных подстрок может быть пустой).

У Т. есть три генные последовательности $A$, $B$ и $C$ длины $n$, а также $Q$ запросов. Каждый запрос описывается шестью положительными целыми числами $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$.