A nearby meadow consists of quadratic fields organized in \(n\) rows and \(m\) columns. The rows are denoted
with numbers from 1 to \(n\) from top to bottom, and the columns with numbers from 1 to \(m\) from left to
right. Some fields are grass fields (denoted with “1”), whereas some are underwater because of the heavy
spring rainfall (denoted with “0”). Two grass fields are connected if it is possible to get from one field to
another using a series of moves where, in each step, we move to the adjacent grass field located up, down,
left or right. A component is a set of mutually connected grass fields that is maximal in the sense that, if
\(A\) is a field in the component \(K\), then all the adjacent grass fields of \(A\) are also in the component \(K\).
For a given meadow \(P\) and indices \(a\) and \(b\) (\(1 \le a \le b \le n\)), \(P\) ^{a}
{b} ^{is} ^{a} ^{meadow} ^{consisting} ^{of} ^{rows} ^{between}
the \(a^{th}\) and the \(b^{th}\) row of the original meadow \(P\) (including both \(a^{th}\) and \(b^{th}\) row). The complexity of
meadow \(P\) ^{a}
} ^{is} ^{the} ^{number} ^{of} ^{components} ^{of} ^{the} ^{grass} ^{fields} ^{located} ^{on} ^{the} ^{meadow.} ^{Determine} ^{the} ^{sum
of the complexities of all possible meadows \(P\) ^{a}
\(b\) ^{.}

Subtask 1 (9 points): \(n \le 100\), \(m \le 50\)

Subtask 2 (17 points): \(n \le 1\,000\), \(m \le 50\)

Subtask 3 (35 points): \(n \le 100\,000\), \(m \le 15\)

Subtask 4 (39 points): \(n \le 100\,000\), \(m \le 50\)

The first line of input contains the positive integers \(n\) and \(m\) — dimensions of the meadow. Each of the
following \(n\) lines contains a string of exactly \(m\) characters that denotes one row of the meadow. Each
character of the string is either the digit “0” or the digit “1”.

You must output the required sum of all complexities.

생성자가 기록되지 않았습니다.

출처 COCI 2016/2017 Olympiad