Задано клетчатое поле, состоящее из \(2\) строк и \(n\) столбцов. Каждая клетка поля либо свободна, либо заблокирована.
Свободная клетка \(y\) достижима из свободной клетки \(x\), если выполняется хотя бы одно из следующих условий:
- \(x\) и \(y\) имеют общую сторону;
- существует свободная клетка \(z\), такая что \(z\) достижима из \(x\), и \(y\) достижима из \(z\).
Связный регион — это множество свободных клеток поля, такое что все клетки в нем достижимы друг из друга, но добавление любой другой свободной клетки в множество нарушает это правило.
Например, рассмотрим следующую ситуацию, где белые клетки свободны, а темно-серые клетки заблокированы:
Здесь \(3\) региона, обозначенные красным, зеленым и синим цветами соответственно:
Заданное поле содержит не более \(1\) связного региона. Ваша задача — посчитать количество свободных клеток, удовлетворяющих следующему условию:
- если клетку заблокировать, то количество связных регионов станет равно \(3\).
Примечание
В первом наборе входных данных, если заблокировать клетку \((1, 3)\), количество регионов станет равно \(3\) (смотрите картинку в условии задачи).