Задана матрица \(a\), состоящая из \(3\) строк и \(n\) столбцов. Каждая клетка матрицы либо свободна, либо занята.
Свободная клетка \(y\) достижима из свободной клетки \(x\), если выполняется хотя бы одно из следующих условий:
- \(x\) и \(y\) имеют общую сторону;
- существует такая свободная клетка \(z\), что \(z\) достижима из \(x\), а \(y\) достижима из \(z\).
Компонента связности — это такой набор свободных клеток матрицы, что все клетки в нем достижимы друг из друга, а добавление любой другой свободной клетки в него нарушает это правило.
К матрице задаются \(q\) запросов. Запросы следующего вида:
- \(l\) \(r\) — посчитайте количество компонент связности матрицы, состоящей из столбцов с \(l\) по \(r\) матрицы \(a\) включительно.
Выведите ответы на все запросы.
Выходные данные
Выведите \(q\) целых чисел — \(j\)-е значение должно быть равно количеству компонент связности матрицы, состоящей из столбцов с \(l_j\) по \(r_j\) матрицы \(a\) включительно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|