CF1661E.Narrow Components

You are given a matrix $a$, consisting of $3$ rows and $n$ columns. Each cell of the matrix is either free or taken.

A free cell $y$ is reachable from a free cell $x$ if at least one of these conditions hold:

• $x$ and $y$ share a side;
• there exists a free cell $z$ such that $z$ is reachable from $x$ and $y$ is reachable from $z$.

A connected component is a set of free cells of the matrix such that all cells in it are reachable from one another, but adding any other free cell to the set violates this rule.

You are asked $q$ queries about the matrix. Each query is the following:

• $l$ $r$ — count the number of connected components of the matrix, consisting of columns from $l$ to $r$ of the matrix $a$, inclusive.

Print the answers to all queries.

给你一个由 $3$ 行 $n$ 列组成的矩阵 $a$。矩阵中的每个单元格要么是空闲的，要么是被占据的。

若满足以下任一条件，则称空闲单元格 $y$ 可从空闲单元格 $x$ 到达：

• $x$ 与 $y$ 共享一条边；
• 存在某个空闲单元格 $z$，使得 $z$ 可从 $x$ 到达，且 $y$ 可从 $z$ 到达。

连通分量是指矩阵中一组空闲单元格，其中任意两个单元格均可互相到达，但向该集合中添加任何其他空闲单元格都会破坏这一性质。

你需要处理关于该矩阵的 $q$ 个查询。每个查询的形式如下：

• $l$ $r$ —— 计算矩阵 $a$ 中第 $l$ 列至第 $r$ 列（含端点）所构成子矩阵的连通分量数量。

请输出所有查询的答案。

The first line contains an integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the number of columns of matrix $a$.

The $i$-th of the next three lines contains a description of the $i$-th row of the matrix $a$ — a string, consisting of $n$ characters. Each character is either $1$ (denoting a free cell) or $0$ (denoting a taken cell).

The next line contains an integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.

The $j$-th of the next $q$ lines contains two integers $l_j$ and $r_j$ ($1 \le l_j \le r_j \le n$) — the description of the $j$-th query.

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）——矩阵 $a$ 的列数。

接下来三行中的第 $i$ 行描述矩阵 $a$ 的第 $i$ 行——一个由 $n$ 个字符组成的字符串。每个字符为 $1$（表示空闲单元格）或 $0$（表示已被占据的单元格）。

下一行包含一个整数 $q$（$1 \le q \le 3 \cdot 10^5$）——查询的数量。

接下来 $q$ 行中的第 $j$ 行包含两个整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$）——第 $j$ 个查询的描述。

Print $q$ integers — the $j$-th value should be equal to the number of the connected components of the matrix, consisting of columns from $l_j$ to $r_j$ of the matrix $a$, inclusive.

输出 $q$ 个整数——第 $j$ 个值应等于由矩阵 $a$ 的第 $l_j$ 列到第 $r_j$ 列（含端点）所组成的子矩阵的连通块数量。