Cross-Shaped Market Stalls

A market floor is given as a list of equal-length strings floor, where '.' is an open tile and '#' is a pillar. A cross stall is a centre tile plus four straight arms going up, down, left and right from it. Each arm is a run of tiles directly next to the centre in its direction, and each arm has its own length, which must be at least min_arm. Every tile of the stall (centre and arms) must be open and inside the floor.

Two stalls are different if their centres differ or any arm length differs. Return the number of different cross stalls.

Examples

Input:  floor = ["...", "...", "..."], min_arm = 1
Output: 1
Explanation: only the centre tile has room for an arm in all four directions.

Input:  floor = [".....", ".....", ".....", ".....", "....."], min_arm = 1
Output: 100

Input:  floor = [".....", ".....", ".....", ".....", "....."], min_arm = 2
Output: 1

Input:  floor = [".#.", "...", "..."], min_arm = 1
Output: 0

Constraints

• 1 <= len(floor), len(floor[0]) <= 400
• 1 <= min_arm <= 400
• The largest tests are 400 x 400 floors with long open runs; walking outward from every centre is too slow.

Goals

• Precompute open runs in all four directions with four sweeps
• Turn a count of shapes into a product of independent choices
• Avoid rescanning the same cells for every centre