E. Узкие компоненты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана матрица $$$a$$$, состоящая из $$$3$$$ строк и $$$n$$$ столбцов. Каждая клетка матрицы либо свободна, либо занята.

Свободная клетка $$$y$$$ достижима из свободной клетки $$$x$$$, если выполняется хотя бы одно из следующих условий:

  • $$$x$$$ и $$$y$$$ имеют общую сторону;
  • существует такая свободная клетка $$$z$$$, что $$$z$$$ достижима из $$$x$$$, а $$$y$$$ достижима из $$$z$$$.

Компонента связности — это такой набор свободных клеток матрицы, что все клетки в нем достижимы друг из друга, а добавление любой другой свободной клетки в него нарушает это правило.

К матрице задаются $$$q$$$ запросов. Запросы следующего вида:

  • $$$l$$$ $$$r$$$ — посчитайте количество компонент связности матрицы, состоящей из столбцов с $$$l$$$ по $$$r$$$ матрицы $$$a$$$ включительно.

Выведите ответы на все запросы.

Входные данные

В первой строке записано одно целое число $$$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