There is a grid with H rows and W columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left. Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares. Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions. 1≤a<b≤H 1≤c<d≤W There was one cookie on each square (i,j) such that a≤i≤b,c≤j≤d, and no cookie on the other squares. However, Snuke took and ate one of the cookies on the grid. The square that contained that cookie is now empty. As the input, you are given the state of the grid after Snuke ate the cookie. The state of the square (i,j) is given as the character S i,j ​ , where # means a square with a cookie, and . means a square without one. Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

To solve this problem, we can iterate over all possible positions of the removed cookie and check if the remaining cookies form a valid rectangle.

We can start by iterating over all possible positions of the removed cookie. For each position, we can check if the remaining cookies form a rectangle by iterating over all rows and columns and checking if there is exactly one cookie in each row and column within the boundaries of the rectangle.

If we find a rectangle where there is exactly one cookie missing, we can output the position of the missing cookie.

Here's the Python code to implement this algorithm:

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            valid = True
            for k in range(H):
                if k != i and grid[k][j] == '#':
                    valid = False
                    break
            for k in range(W):
                if k != j and grid[i][k] == '#':
                    valid = False
                    break
            if valid:
                print(i+1, j+1)
                exit()

The code reads the input grid and iterates over all positions of the removed cookie. For each position, it checks if the remaining cookies form a valid rectangle and outputs the position of the missing cookie if it finds one.