Задана матрица \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач