Subsecuencias felices en posiciones crecientes de una matriz X12077

Statement

Dada una matriz $M$ de $n\times{}m$ caracteres, una subsecuencia feliz a posiciones crecientes es una tripleta de posiciones $(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]$ =’)’ y $0\leq{}i_1<i_2<i_3<n$ y $0\leq{}j_1<j_2<j_3<m$ .

Implementad un programa que lee matrices de caracteres de entrada, y escribe el número de subsecuencias felices a posiciones crecientes en cada matriz.

Entrada

La entrada tiene varios casos. Cada caso comienza con una linea con dos naturales positivos $n,m$ . Después vienen $n$ lineas con $m$ caracteres cada una, escogidos de entre {’:’,’-’,’)’}. Casos consecutivos están separados por una linea en blanco.

Salida

Para cada caso, el programa escribe en una linea el número de subsecuencias felices a posiciones crecientes de la matriz de entrada.

Observación

Evaluación sobre 10 puntos:

Solución lenta: 5 puntos.
Solución rápida: 10 puntos.

Entendemos como solución rápida una que es correcta, de coste lineal y capaz de superar los juegos de pruebas públicos y privados. Entendemos como solución lenta una que no es rápida, pero es correcta y capaz de superar los juegos de pruebas públicos.

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: Spanish
Translator
Original language: Catalan
Other languages: Catalan English
Official solutions: C++
User solutions: C++