给定一个矩阵 $$$a$$$,由 $$$3$$$ 行和 $$$n$$$ 列组成。矩阵的每个单元格要么是空闲的,要么是被占用的。
如果至少满足以下条件之一,则可以从空闲单元格 $$$x$$$ 访问空闲单元格 $$$y$$$:
- $$$x$$$ 和 $$$y$$$ 共享一边;
- 存在一个空闲单元$$$z$$$,使得$$$z$$$可以从$$$x$$$到达并且$$$y$$$可以从$$$z$$$到达。
连接组件是矩阵的一组空闲单元,其中的所有单元都可以相互访问,但向该组添加任何其他空闲单元会违反此规则。
系统会向您询问有关矩阵的 $$$q$$$ 个查询。每个查询如下:
- $$$l$$$ $$$r$$$ - 计算矩阵的连通分量的数量,由矩阵 $$$a$$$ 的从 $$$l$$$ 到 $$$r$$$ 的列组成,包括边界值。
打印所有问题的答案。
输入
第一行包含一个整数 $$$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$$$ 查询的描述。
输出
打印 $$$q$$$ 整数 - 第 $$$j$$$ 个值应等于矩阵的连通分量的数量,该矩阵由矩阵 $$$a$$$ 的从 $$$l_j$$$ 到 $$$r_j$$$ 的列组成(含)。
示例
输入 #1
12 100101011101 110110010110 010001011101 8 1 12 1 1 1 2 9 9 8 11 9 12 11 12 4 6
输出 #1
7 1 1 2 1 3 3 3