14 ноября в Японии отмечается День хорошего камня. На праздничной выставке смотритель Мика разносит конкурсные камни по площадкам. После первого ливня зрители предложили жюри добавить в программу фигурное катание с камнем.
Площадки образуют два ряда по $$$n+1$$$ площадке. Столбцы пронумерованы слева направо от $$$0$$$ до $$$n$$$. Верхний ряд имеет номер $$$0$$$, нижний — номер $$$1$$$. Площадка $$$(x,y)$$$ находится в столбце $$$x$$$ и ряду $$$y$$$.
В каждом столбце две площадки соединены вертикальной дорожкой. В каждом ряду площадки соседних столбцов соединены горизонтальной дорожкой. По любой проходимой дорожке можно идти в обе стороны.
Зона $$$i$$$ включает вертикальную дорожку в столбце $$$i$$$ и, если $$$i \gt 0$$$, обе горизонтальные дорожки между столбцами $$$i-1$$$ и $$$i$$$. Например, обе горизонтальные дорожки между столбцами $$$0$$$ и $$$1$$$ относятся к зоне $$$1$$$.
В каждой зоне либо сухо, либо идёт дождь. Каждая дорожка бывает одного из двух типов. Всепогодная дорожка проходима при любой погоде, а скользкая — только если в её зоне сухо.
Путь проходим, если проходимы все его дорожки. Длина пути равна числу пройденных дорожек. Для $$$0 \le x \le y \le n$$$ обозначим через $$$P_{x,y}$$$ число проходимых путей из $$$(x,0)$$$ в $$$(y,1)$$$ длины ровно $$$y-x+1$$$.
Обработайте $$$q$$$ запросов в заданном порядке.
$$$$$$A = \sum_{0 \le x \le y \le n} P_{x,y}, \qquad B = \sum_{0 \le x \le y \le n} (y-x+1) P_{x,y}.$$$$$$
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — число столбцов без учёта столбца $$$0$$$ и число запросов.
Вторая строка содержит двоичную строку $$$w$$$ длины $$$n+1$$$, описывающую погоду в зонах от $$$0$$$ до $$$n$$$ по порядку. Символ 0 означает сухую погоду, а 1 — дождь.
Третья строка содержит двоичную строку $$$v$$$ длины $$$n+1$$$, описывающую типы вертикальных дорожек в столбцах от $$$0$$$ до $$$n$$$ по порядку.
Четвёртая строка содержит двоичную строку $$$u$$$ длины $$$n$$$, описывающую типы верхних горизонтальных дорожек в зонах от $$$1$$$ до $$$n$$$ по порядку.
Пятая строка содержит двоичную строку $$$d$$$ длины $$$n$$$, описывающую типы нижних горизонтальных дорожек в зонах от $$$1$$$ до $$$n$$$ по порядку.
В строках $$$v$$$, $$$u$$$ и $$$d$$$ символ 0 обозначает всепогодную дорожку, а 1 — скользкую.
Каждая из следующих $$$q$$$ строк содержит один запрос в одном из трёх форматов.
Для каждого запроса типа $$$3$$$ выведите в отдельной строке два целых числа $$$A \bmod 998\,244\,353$$$ и $$$B \bmod 998\,244\,353$$$.
Если запросов типа $$$3$$$ нет, вывод должен быть пустым.
1 10000003
4 6
2 5000111110031 1 231 0 13
10 20 3 6 4 8
1 701011132 1 232 1 032 1 13
1 1 2 3 3 4 4 6
2 9111111111132 0 031 0 032 0 031 0 03
0 0 1 1 1 1 1 1 0 0
3 31111011001001031 2 23
4 6 14 35
В первом примере все дорожки проходимы. Есть два пути длины $$$1$$$, по вертикальной дорожке в каждом столбце, и два пути длины $$$2$$$ из $$$(0,0)$$$ в $$$(1,1)$$$. Эти два пути отличаются столбцом, в котором переходят в нижний ряд.
Во втором примере изначально есть три пути длины $$$1$$$, четыре пути длины $$$2$$$ и три пути длины $$$3$$$. После первого изменения погоды перейти в нижний ряд можно только в столбце $$$0$$$. Из него можно дойти до любой из трёх нижних площадок. После второго изменения погоды вертикальная дорожка проходима только в столбце $$$1$$$. До неё можно добраться из столбца $$$0$$$ или $$$1$$$, а после неё можно закончить путь в столбце $$$1$$$ или $$$2$$$. Получаются четыре пути длины $$$2$$$, $$$3$$$, $$$1$$$ и $$$2$$$.
В третьем примере сначала проходима только вертикальная дорожка в столбце $$$0$$$. Первое изменение типа открывает нижнюю горизонтальную дорожку и добавляет путь длины $$$2$$$. Второе изменение открывает вертикальную дорожку в столбце $$$1$$$ и добавляет путь длины $$$1$$$. Третье изменение открывает верхнюю горизонтальную дорожку и добавляет ещё один путь длины $$$2$$$.
В четвёртом примере изначально все дорожки скользкие и во всех зонах идёт дождь, поэтому путей нет. После первого запроса типа $$$2$$$ появляется путь по вертикальной дорожке в столбце $$$0$$$. Когда эта дорожка снова становится скользкой, в её зоне сухо, поэтому по ней можно пройти до следующего дождя.
В пятом примере сначала пройти по вертикальной дорожке можно только в столбцах $$$0$$$ и $$$3$$$. Каждый из них даёт по два пути длины $$$1$$$ и $$$2$$$. Затем в зоне $$$2$$$ становится сухо. Открываются обе её горизонтальные дорожки и вертикальная дорожка. Четыре пути переходят в нижний ряд в столбце $$$0$$$, шесть — в столбце $$$2$$$, ещё четыре — в столбце $$$3$$$.