Maximizing Fly Swatter Kills

You are given a window of size \(R \times S\) on which several flies are present. Each cell of the window is either empty (denoted by '.') or has a fly (denoted by '*'). You are also given a fly swatter which, when placed, covers a \(K \times K\) square region. However, the swatter kills only the flies strictly inside the chosen square, i.e. it does not affect the flies on the boundary of the square. Formally, if the swatter is placed with its top-left corner at \((i, j)\), then it will kill all flies located in cells \((r, c)\) where

[ i+1 \le r \le i+K-2 \quad \text{and} \quad j+1 \le c \le j+K-2, ]

Your task is to choose a placement of the fly swatter (the entire \(K \times K\) square must lie within the window) so that the number of killed flies is maximized. If there are multiple optimal placements, output any one.

inputFormat

The first line contains three integers \(R\), \(S\), and \(K\) (the dimensions of the window and the side length of the swatter). \(R\) and \(S\) denote the number of rows and columns respectively. It is guaranteed that \(K \le R\) and \(K \le S\).

The following \(R\) lines each contain a string of length \(S\), consisting only of characters '.' and '*'. A '*' represents a fly.

outputFormat

Output two lines. The first line should contain the maximum number of flies that can be killed. The second line should contain two integers representing the row and column (1-indexed) of the top-left corner of the chosen \(K \times K\) region.

sample

5 6 3
......
.**.*.
..**..
...*..
......

1
2 2