Задана матрица $$$a$$$, состоящая из $$$3$$$ строк и $$$n$$$ столбцов. Каждая клетка матрицы либо свободна, либо занята.
Свободная клетка $$$y$$$ достижима из свободной клетки $$$x$$$, если выполняется хотя бы одно из следующих условий:
Компонента связности — это такой набор свободных клеток матрицы, что все клетки в нем достижимы друг из друга, а добавление любой другой свободной клетки в него нарушает это правило.
К матрице задаются $$$q$$$ запросов. Запросы следующего вида:
Выведите ответы на все запросы.
В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — количество столбцов матрицы $$$a$$$.
В $$$i$$$-й из следующих трех строк описывается $$$i$$$-я строка матрицы $$$a$$$ — строка, состоящая из $$$n$$$ символов. Каждый символ — это либо $$$1$$$ (обозначающий свободную клетку), либо $$$0$$$ (обозначающий занятую клетку).
В следующей строке записано одно целое число $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — количество запросов.
В $$$j$$$-й из следующих $$$q$$$ строк записаны два целых числа $$$l_j$$$ и $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — описание $$$j$$$-го запроса.
Выведите $$$q$$$ целых чисел — $$$j$$$-е значение должно быть равно количеству компонент связности матрицы, состоящей из столбцов с $$$l_j$$$ по $$$r_j$$$ матрицы $$$a$$$ включительно.
12 100101011101 110110010110 010001011101 8 1 12 1 1 1 2 9 9 8 11 9 12 11 12 4 6
7 1 1 2 1 3 3 3
Название |
---|