|2015-2016 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)|
Col. Sheffard is going to make a training for Cpt. Plice. The colonel has a polygon containing infinite number of closed doors placed one by one in a row. Initially Cpt. Plice stands in front of the first door. The captain is able to perform the following two commands:
A sequence of commands is valid if the following conditions are met:
Col. Sheffard received a template — a rectangular grid with n rows and m columns where each cell contains one of the commands, i.e. '(' or ')'. The colonel has to choose a training plan for the captain — select a non-empty rectangle from the grid, each row of the rectangle will be an independent training for the captain. The training plan is valid, if each row of the selected rectangle is a valid sequence of commands.
You are to find the number of ways to select a valid training plan for a given grid. The selected rectangle should be continuous, i.e. without holes. Plans are different if they have different positions of their corners even if their contents are the same.
The first line contains two integers n and m (1 ≤ n, m ≤ 50000) — number of rows and number of columns in the template respectively. Each of the following n lines contains a string with m symbols '(' or ')' — commands of the template. The total number of elements in the template doesn't exceed 106.
Output a single integer — the number of rectangles on the template, corresponding to a valid training plan. Two rectangles with equal content but different positions of corners should be counted both.