Highest perimeter polyomino This is code golf. The winner is the valid code with the smallest number of bytes.



Challenge

Given inputs M and N, the width and height of a rectangular grid of squares, output a polygon that satisfies the following:


The polygon edges are made up only of square edges: there are no diagonal edges - all are vertical or horizontal.
The polygon has no holes: every square outside the polygon may be reached by orthogonal steps on squares outside the polygon, starting from a square outside the polygon on the outer boundary of the rectangle.
The polygon has no self-intersection: of the square edges meeting at a vertex, no more than 2 may be part of the polygon perimeter.
The polygon is connected: any square in the polygon must be reachable from any other square in the polygon via orthogonal steps that stay within the polygon.
The polygon has the maximum possible perimeter: according to the formula shown below.


Your code must work for M and N from 1 to 255.



Formula for maximum perimeter

The challenge here is finding the most golfable of those polygons with the maximum perimeter. The maximum perimeter itself is always defined by the formula:



This is true because for a maximum perimeter every square vertex must be on the perimeter. For an odd number of vertices this is not possible and the best that can be attained is one vertex less (since the perimeter is always even).



Output

Output the shape as a string of newline separated characters (N rows of exactly M characters). Here I am using space for squares outside the polygon, and '#' for squares inside the polygon, but you may use any two visually distinct characters, provided their meaning is consistent for all inputs.

You may include up to one leading newline and up to one trailing newline.

If you wish, you may instead output M rows of exactly N characters, and you may choose M by N output for some inputs and N by M output for others.



Examples

Invalid due to a hole:

###
# #
###


Invalid due to intersection (touching diagonally - a vertex with 4 square edges on the perimeter) and, incidentally, a hole:

##
# #
###


Invalid due to being disconnected:

#
# #
  #


Valid polygon of maximum perimeter:

# #
# #
###




Credits

I initially underestimated how quickly the value of the maximum perimeter could be calculated, and was going to just ask for that value as the output. Thanks to the wonderfully helpful people in chat for explaining how to work out the maximum perimeter for arbitrary N and M and helping turn this into a challenge that will last for more than one answer...

Specifically thanks to:

Sparr, Zgarb, feersum, jimmy23013.
Ruby, Rev 1, 66
-&gt;(m,n){n.times{|i|puts (&quot;#&quot;*m**(1-i%2)).rjust(m,i&gt;n-2?&quot;# &quot;:&quot; &quot;)}}

Used raising m to power 0 o 1 to decide whether 1 or m #'s will be printed.
Used &gt; to test for last row instead of ==.
Can't get rid of the space after puts, nor any brackets!
Ruby, Rev 0, 69
-&gt;(m,n){n.times{|i|puts (&quot;#&quot;*(i%2==0?m:1)).rjust(m,i==n-1?&quot;# &quot;:&quot; &quot;)}}

This is an anonymous lambda function. Use it like this:
f=-&gt;(m,n){n.times{|i|puts (&quot;#&quot;*(i%2==0?m:1)).rjust(m,i==n-1?&quot;# &quot;:&quot; &quot;)}}

M=gets.to_i
N=gets.to_i
f.call(M,N)

In the end, after asking if M and N could be interchanged I didnt need it.

Typical outputs for N odd. If we delete the # on their own on the right hand side, clearly we will have (N+1)(M+1). Including them to join the shape removes 2 squares of horizontal perimeter and adds 2 squares of vertical perimeter, so there is no change.
Here we rely on the expression &quot;#&quot;*(i%2==0?m:1) to give alternating rows of M# symbols and one # symbol, and right justify to M characters.
5                        6
5                        5
#####                    ######
    #                         #
#####                    ######
    #                         #
#####                    ######


Typical outputs for N even. 5 6 clearly has the same perimeter as 6 5, or an increment of M+1=6 compared with 5 5 by addition of vertical perimeter due to the crenelation of the bottom row. 6 6 has the same as 6 5 plus an increment of (M+1)-1=6 in the vertical perimeter. Thus they are in accordance with the formula.
5                        6
6                        6
#####                    ######
    #                         #
#####                    ######
    #                         #
#####                    ######
# # #                    # # ##

It's very handy that Ruby's rjust allows you to specify the padding to use for the empty cells. Normally the padding is set to &quot; &quot; but for the last row we switch to &quot;# &quot; (note that padding will only be needed on the last row if N is even. Where N is odd the last row will be complete and there will be no justifying, so you won't see the crenelations.)
Check it out here.