E. День хорошего камня
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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$$$ запросов в заданном порядке.

  • Запрос типа $$$1$$$ меняет погоду в каждой зоне от $$$l$$$ до $$$r$$$ включительно. Если в зоне было сухо, там начинает идти дождь, и наоборот.
  • Запрос типа $$$2$$$ меняет тип одной дорожки в зоне $$$i$$$. Всепогодная дорожка становится скользкой, и наоборот. Параметр $$$t$$$ задаёт дорожку. При $$$t=0$$$ это вертикальная дорожка в столбце $$$i$$$, при $$$t=1$$$ — верхняя горизонтальная, при $$$t=2$$$ — нижняя горизонтальная.
  • Запрос типа $$$3$$$ требует найти число всех учитываемых путей $$$A$$$ и сумму их длин $$$B$$$ при текущих погоде и типах дорожек. Другими словами,

    $$$$$$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$$$ строк содержит один запрос в одном из трёх форматов.

  • 1 $$$l$$$ $$$r$$$ ($$$0 \le l \le r \le n$$$).
  • 2 $$$i$$$ $$$t$$$ ($$$0 \le i \le n$$$, $$$0 \le t \le 2$$$). При $$$i=0$$$ допускается только $$$t=0$$$.
  • 3.
Выходные данные

Для каждого запроса типа $$$3$$$ выведите в отдельной строке два целых числа $$$A \bmod 998\,244\,353$$$ и $$$B \bmod 998\,244\,353$$$.

Если запросов типа $$$3$$$ нет, вывод должен быть пустым.

Примеры
Входные данные
1 1
00
00
0
0
3
Выходные данные
4 6
Входные данные
2 5
000
111
11
00
3
1 1 2
3
1 0 1
3
Выходные данные
10 20
3 6
4 8
Входные данные
1 7
01
01
1
1
3
2 1 2
3
2 1 0
3
2 1 1
3
Выходные данные
1 1
2 3
3 4
4 6
Входные данные
2 9
111
111
11
11
3
2 0 0
3
1 0 0
3
2 0 0
3
1 0 0
3
Выходные данные
0 0
1 1
1 1
1 1
0 0
Входные данные
3 3
1111
0110
010
010
3
1 2 2
3
Выходные данные
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$$$.