Snake Game

Limits 1s, 512 MB

If you had played the Snake game in old Nokia phones then you had an awesome childhood because all the memories we have with these legendary phones of our parents are unparalleled. In this problem, your task is about to do something similar to the Snake game. The task is described in the following,

Imagine a python starts moving from the top left corner of a (M by N) grid. The initial moving direction of the python is always to the right. It moves one edge adjacent cell if the next cell is empty or the next cell is within the M by N grid. The snake turns clockwise if there is no space to move to the next forward cell. It stops moving when it can't move anymore. Some rules of the path that the python follows are as follows,

  1. The python always starts moving from the top left corner of the cell in the right direction.
  2. It never moves along two consecutive rows or columns.
  3. It never goes outside the M by N grid. After reaching the boundary, it changes its direction clockwise.
  4. It never crosses or touches the path that it traveled. (See the image and sample cases for clarification)
  5. It can't move backward.
  6. It stops moving when there is no cell to go.

Your task is to print the path representing with '#' hash character and empty cells with a space character.

Input

Each test case contains two integers M & N in one line that denotes the row and column numbers of the grid.

3 <= M, N <= 10^3

Output

Print the M by N grid with the path of the python representing with '#' characters.

Samples

InputOutput
10 10
##########
         #
######## #
#      # #
# #### # #
# #  # # #
# #    # #
# ###### #
#        #
##########
InputOutput
11 10
##########
         #
######## #
#      # #
# #### # #
# #  # # #
# # ## # #
# #    # #
# ###### #
#        #
##########