A particularly interesting math problem catches your eye! The problem is asking about an ~M~ by ~N~ grid. Some of these squares are coloured black while the rest are white. The grid in this problem is coloured in such a way that no four distinct black squares form a rectangle with sides parallel to the sides of the grid.
You are trying to see what kind of colourings of the ~M~ by ~N~ grid have this property. As such, you have given yourself a colouring of the grid. However, you aren't sure if the way you coloured it actually works.
Given a colouring of an ~M~ by ~N~ grid, determine whether or not there exist four distinct black squares which form a rectangle with sides parallel to the sides of the grid.
Clarification: These four distinct black squares must be exactly the four corners of the rectangle they form.
Subtask 1 [20%]
~1 \le M, N \le 70~
Subtask 2 [30%]
~1 \le M, N \le 400~
Subtask 3 [50%]
~1 \le M, N \le 2\,000~
The first line will contain two space-separated integers, ~M~ and ~N~ in that order.
The next ~M~ lines will each contain a single string of length ~N~. Each character will either be a
. representing a white tile, or a
# representing a black tile.
Output the answer on a single line. This answer should be
yes if this colouring does not have a rectangle formed by four black squares. Otherwise, output
Sample Input 1
3 4 #.## ##.. ..##
Sample Output 1
Sample Input 2
1 4 ####
Sample Output 2