Circles — RMI contest
Task type: batch | Time limit: 1.5 s | Memory limit: 512 MB | Difficulty: 22
Algorithms: dijkstra, geometric transformation, geometry, grid traversal

# Circles

Time limit: *1500 ms*
Memory limit: *512 MB*

Two of the most mischievous Dacians in history, Danillo and Stegano, thought it would be funny to dig some tunnels that go nowhere. They knew that future historians would be extremely confused about the existence of some random tunnels and would try to speculate their purpose, but the tunnels would be, in fact, useless.

They found a huge wall in which they could start digging, but unfortunately, some patches of the wall would be unbreakable, so they would have to avoid them. The entrance to the tunnel would have to be circular for aesthetic reasons.

Formally, the wall can be described as a cartesian plane with x coordinates in the range `[0, M]` and y coordinates in the range `[0, N]`. The patches that are unbreakable are squares with sides parallel to the axes of length 1 with corners in integer coordinates. The map of the zones that can be broken can be described by a binary matrix with N lines numbered from 0 to `N - 1` and M columns numbered from 0 to `M - 1`. If the element from line l and column c is 1, then all the points (x, y) with `c <= x <= c + 1` and `l <= y <= l + 1` can be mined. **Note the difference between the coordinates (x, y) in the plane and the coordinates (l, c) of elements in the matrix**.

When mining a tunnel, the two select a point with **integer** coordinates (x, y) as the center of the tunnel, then they select a radius r, and finally, they start digging through all the points that lie inside the disc with the center in (x, y) of radius r. **Note that the disc includes all the points inside, not just on the boundary of the circle, and the disc must lie completely inside the defined plane** `[0, M] x [0, N]`. Furthermore, **all points within the chosen disc must fall within areas marked as '1' in the input matrix**.

They want the tunnel to be as noticeable as possible, so they want the tunnel with the largest radius. For easier construction, if there are multiple such tunnels, they want the one that is the easiest to dig. If the center of the tunnel is in coordinates (x, y), they want the one with the smallest y. If there are still multiple tunnels to choose from, they want the one with the smallest x.

## Standard input

The first line contains two integers N and M in this order, defining the plane dimensions and the size of the binary matrix.

The following N lines each contain a string of length M consisting of '0's and '1's, denoting the elements of the matrix described above (row by row, from row 0 to N-1).

## Standard output

On a single line, you must print three space separated integers x, y and R. x, y represent the coordinates of the center of the optimal tunnel that Danillo and Stegano will dig, and R represents the **radius of the circle, squared and rounded to the nearest integer**.

## Constraints and notes

* 1 <= N, M <= 3,000

---

**Example 1:**

*Input:*
```
5 6
011110
111110
011111
111111
011110
```
*Output:*
```
3 2 4
```

---

**Example 2:**

*Input:*
```
3 3
010
101
010
```
*Output:*
```
0 0 0
```

---

Starter code: