Subseqüències felices a posicions creixents en una matriu X12077

Statement

Donada una matriu $M$ de $n\times{}m$ caràcters, una subseqüència feliç a posicions creixents és una tripleta de posicions $(i_1,j_1),(i_2,j_2),(i_3,j_3)$ tal que $M[i_1][j_1]$ =’:’, $M[i_2][j_2]$ =’-’, $M[i_3][j_3]$ =’)’ i $0\leq{}i_1<i_2<i_3<n$ i $0\leq{}j_1<j_2<j_3<m$ .

Implementeu un programa que llegeix matrius de caràcters d’entrada, i escriu el nombre de subseqüències felices a posicions creixents en cada matriu.

Entrada

L’entrada té varis casos. Cada cas comença amb una línia amb dos naturals positius $n,m$ . Després venen $n$ línies amb $m$ caràcters cadascuna, escollits d’entre {’:’,’-’,’)’}. Dos casos consecutius estan separats per una línia en blanc.

Sortida

Per a cada cas, el programa escriu el nombre de subseqüències felices a posicions creixents de la matriu d’entrada en una línia.

Observació

Avaluació sobre 10 punts:

Solució lenta: 5 punts.
solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost lineal i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.

Public test cases

Input

7 4
:-)-
-::-
)-)-
)-::
--))
::))
)---


3 10
::):----::
:))-))):)-
-)):))--::


8 5
))-:-
)::::
):)):
)-::)
)::))
-::):
---::
):-)-


2 8
))::-)-)
)-:)-)-:


8 2
:)
:)
:-
:-
):
:)
-)
))


2 9
)):)::-)-
::))-):-)


9 10
))-)--)-:-
))::)-:--)
)-)):-)-)-
:-))::::)-
--)))---::
::):)::)))
-)-:)))-:)
:)-::-))):
):-)--)-:-


1 2
-)


7 1
-
:
:
)
)
-
:


5 9
::)::)):-
)):):--)-
:-))-::-:
)-))):-):
::-::-:))


3 9
::)):)::-
:--)-:)--
))):)):-:


3 5
))-:)
-:))-
:)--)


4 9
)):))::-:
-)-)):):-
--)---)-)
--)::---)


2 5
:::--
:::::


9 4
:--)
::-:
):):
:))-
--:)
)-::
)--)
::-:
)::)


8 9
))-)):--)
)::))):-)
))-):::)-
:)-)-:--)
):)-:))::
-:)::))):
:::)::::)
:)::--)))


9 6
)--:::
-):-:-
)-::)-
--)-:-
))::)-
:)))):
:-----
)::--)
:-):):


9 4
)):-
-::-
:::-
)-):
:)--
::--
--)-
----
:-:)


2 3
):)
)-)


2 8
:-)):)))
----::)-

Output

Information

Author: PRO1
Language: Catalan
Other languages: English Spanish
Official solutions: C++
User solutions: C++