November 14 is Good Stone Day in Japan. At the holiday exhibition, Mika carries the stones entered in the contest from one platform to another. After the first downpour, the spectators asked the judges to add figure skating with a stone to the program.
The platforms form two rows of $$$n+1$$$ platforms each. The columns are numbered from $$$0$$$ to $$$n$$$ from left to right. Row $$$0$$$ is the upper row, and row $$$1$$$ is the lower row. Platform $$$(x,y)$$$ is in column $$$x$$$ and row $$$y$$$.
In each column, a vertical walkway connects the two platforms. In each row, a horizontal walkway connects the platforms in each pair of adjacent columns. Each passable walkway can be used in either direction.
Zone $$$i$$$ contains the vertical walkway in column $$$i$$$ and, if $$$i \gt 0$$$, both horizontal walkways between columns $$$i-1$$$ and $$$i$$$. For example, both horizontal walkways between columns $$$0$$$ and $$$1$$$ belong to zone $$$1$$$.
The weather in each zone is either dry or rainy. Each walkway has one of two types. An all-weather walkway is passable in any weather, while a slippery walkway is passable only when its zone is dry.
A path is passable if all its walkways are passable. Its length is the number of walkways traversed. For $$$0 \le x \le y \le n$$$, let $$$P_{x,y}$$$ be the number of passable paths from $$$(x,0)$$$ to $$$(y,1)$$$ of length exactly $$$y-x+1$$$.
Process $$$q$$$ queries in the given order.
$$$$$$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}.$$$$$$
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of columns excluding column $$$0$$$ and the number of queries.
The second line contains a binary string $$$w$$$ of length $$$n+1$$$, describing the weather in zones $$$0$$$ through $$$n$$$ in order. The character 0 means dry weather, and 1 means rain.
The third line contains a binary string $$$v$$$ of length $$$n+1$$$, describing the types of the vertical walkways in columns $$$0$$$ through $$$n$$$ in order.
The fourth line contains a binary string $$$u$$$ of length $$$n$$$, describing the types of the upper horizontal walkways in zones $$$1$$$ through $$$n$$$ in order.
The fifth line contains a binary string $$$d$$$ of length $$$n$$$, describing the types of the lower horizontal walkways in zones $$$1$$$ through $$$n$$$ in order.
In the strings $$$v$$$, $$$u$$$, and $$$d$$$, the character 0 denotes an all-weather walkway, and 1 denotes a slippery walkway.
Each of the next $$$q$$$ lines contains one query in one of the following formats.
For each query of type $$$3$$$, output two integers $$$A \bmod 998\,244\,353$$$ and $$$B \bmod 998\,244\,353$$$ on a separate line.
If there are no queries of type $$$3$$$, the output is empty.
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
In the first example, all walkways are passable. There are two paths of length $$$1$$$, one along the vertical walkway in each column, and two paths of length $$$2$$$ from $$$(0,0)$$$ to $$$(1,1)$$$. The two paths reach the lower row in different columns.
In the second example, there are initially three paths of length $$$1$$$, four paths of length $$$2$$$, and three paths of length $$$3$$$. After the first weather switch, a path can reach the lower row only in column $$$0$$$. From there it can reach any of the three lower platforms. After the second weather switch, the only passable vertical walkway is in column $$$1$$$. A path can start in column $$$0$$$ or $$$1$$$ and end in column $$$1$$$ or $$$2$$$. This gives four paths of lengths $$$2$$$, $$$3$$$, $$$1$$$, and $$$2$$$.
In the third example, the vertical walkway in column $$$0$$$ is initially the only passable walkway. The first type switch opens the lower horizontal walkway, adding a path of length $$$2$$$. The second switch opens the vertical walkway in column $$$1$$$, adding a path of length $$$1$$$. The third switch opens the upper horizontal walkway, adding another path of length $$$2$$$.
In the fourth example, all walkways are initially slippery and it is raining in every zone, so there are no paths. After the first query of type $$$2$$$, a path can use the vertical walkway in column $$$0$$$. When the walkway becomes slippery again, its zone is dry, so it can be used until it rains again.
In the fifth example, the only passable vertical walkways are initially in columns $$$0$$$ and $$$3$$$. Each of these columns gives two paths, one of length $$$1$$$ and one of length $$$2$$$. Then the weather in zone $$$2$$$ becomes dry, opening its two horizontal walkways and its vertical walkway. Four paths reach the lower row in column $$$0$$$, six in column $$$2$$$, and four in column $$$3$$$.