Largest Compatible Maze Background
Consider an \$n\times n\$ grid, where each cell is either empty (denoted by .) or a wall (denoted by #). We say that two cells are adjacent if they share an edge (a corner is not enough). A path is a sequence of distinct empty cells \$s_0,s_1,\ldots,s_k\$ such that cells \$s_i\$ and \$s_{i+1}\$ are adjacent for \$0\le i&lt;k\$.
We say that a grid is a maze if the following conditions hold.

There is at most one path between any two empty cells.
The following two \$2\times 2\$ patterns do not occur anywhere in the grid.

  #.             .#
  .#             #.

A maze is not required to be connected (i.e. it is allowed to have two empty cells without any paths between them).
Here are a few examples of mazes.
.###                 #...                 ....
.###                 ###.                 #.##
.#..                 ..#.                 #.##
.###                 #...                 ....

Here are a few examples of grids which are not mazes.
....                 ##.#      Do not satisfy rule 1.
#.#.                 #..#
#...                 #..#
##.#                 #.##

##..                 ##.#      Do not satisfy rule 2.
..#.                 ##.#
#.#.                 .#.#
#...                 #..#

Challenge
Here is a \$128\times 128\$ maze. It has \$991\$ empty cells and \$15393\$ walls. Your task is to tear down as many walls as possible, making sure that the grid you obtain is still a maze.
More formally, let \$M\$ be the maze given above. A submission to this challenge consists of a \$128\times 128\$ maze \$M'\$ such that every empty cell in \$M\$ is also empty in \$M'\$.
Scoring
This is code-challenge: the more walls you manage to tear down, the better.
Your score will be equal to the number of walls (#) in the maze you submit. Lower score is better.
Notes

The maze \$M\$ given above doesn't have any special properties, to the best of my knowledge. It was generated as randomly as possible, fixing the average density of empty cells.
Here is a python script that checks whether your submission is valid and tells you your score (just paste the maze in the &quot;Input&quot; section)
Score: 8066 8065 walls
I found an 8066 wall solution using dynamic programming over solutions that can be recursively decomposed by splitting on a row or column consisting entirely of floors or entirely of walls.  The implementation of this apparently simple idea was rather more complicated than its description, since there are 17 different types of subproblems depending on the borders and the connectivity between them.
I then removed one wall by hand-editing seven cells in rows 119–122, columns 60–63.
This is an optimal solution.  Proof:
Add a one-cell border using \$516\$ extra walls. Consider the planar graph whose vertices are the \$w\$ centers of walls, and whose edges are the \$a\$ wall-wall adjacencies. This graph is connected (because any component of walls not connected to the border would be encircled by a forbidden cycle of floors), and has \$f \ge 2\$ faces (at least an inside and outside). By Euler’s formula, \$w - a + f = 2\$, so \$w - a \le 0\$.
Now consider the different planar graph whose vertices are the \$131^2\$ corner points of walls, and whose edges are the \$4w - a\$ sides of walls. None of these \$131^2\$ vertices are missing (because an isolated one would again be encircled by a forbidden cycle of floors). This graph is again connected and has \$f' \ge w + 2\$ faces. By Euler’s formula, \$131^2 - (4w - a) + f' = 2\$, so \$131^2 - 3w + a \le 0\$.
Adding these two inequalities gives \$131^2 - 2w \le 0\$, so \$w \ge \frac{131^2}{2} = 8064.5 + 516\$.
Validate
.#.#.#.#...#...#.#..#..#.#.#.#...#.#.#.#.#.#.#.#................................................................................
.#.#.#.##.##.###...##.##.#.#.###.....#.#.#.#...#.##########.###########.########.##################.#################.#.#.#.#.#.
.#.#.#.#...#...#.#..#..#.#.#...#.##.##.#.#.#.###...#.#.#.#..#.#.#.#.#.###.#.#..#.#.#.#.#.#.#.#.#.#..#.#.#.#..#.#.#.#..##########
.#.#.#.##.###.##.####.##.#.#.###.#...#.#.#.#.#...###.#.#.####.....#.#.#.#.#.##.###.#.#.#.#.#.#.#.####.#.#.#.##.#.#.####.#.#.#.#.
.#.#.#.#...#...#....#..#.#.#.#...#####.#.#.#.###...#.#.#.#..##.####.............................................................
.#.#.#.##.###.##.####.##.#.#.###.....#.#.#.#.#.#.###.#.#.#.##.....####.####################################################.###.
.#.#.#.#...#...#....#..#.#.#.#...#####.#.#.#.#.....#.#.#.#..###.###.#...#..#.#.#.#.#.#.#.#.#.#.#.#..#.#.#.#.#.#.#.#.#.#.#.###.#.
.#.#.#.##.###.##.####.##.#.#.###.#.#.#.#.#.#.###.###.#.#.#.##.#.#.#.##.###.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.##
................................................................................................................................
##.##.###.#############.#############################################################.#######################################.##
.###...#...#.....#.#..#..#..#.#.#.#.#..#.#.#.#..#..#..#....#..#.#.#..#.#..#.#..#.#.#..#.#.#...#.#..#.#.#.#.#.#.#................
.#.##.##.#.####.##.#.######.#.#.#.#.##.#.#.#.##.#.##.####.##.##.#...##.##.#.##.#.#.####.#.##.##.##.#.#.#.#.....##########.######
.#.#...#####.....#.#..#..#..#.#.#...#..#.#.#.#..#..#..#....#..#.#.#..#.#..#.#..#.#.#..#.#.#...#.#..#.#.#.###.###................
.#.##.##.#.####.##.#.##.###.#.#.##.###.#.#.#.##.#.##.####.##.##.#.####.##.#.##.#.#.##.#.#.##.##.##.#.#.#.#...#.####.############
.#.#...#...#..#..#.#..#..#..#.#.#...#..#.#.#.#..#..#..#....#..#.#....#.#..#.#..#.#.#..#.#.#...#.#..#.#.#.###...#..###...........
.#.##.###.###...##.#.##.###.#.#.##.###.#.#.#.##.#.##.###.###.##.###.##.##.#.##.#.#.##.#.#.##.##.##.#.#.#.#.#.###.##.#.##########
.#.#...#...#..#..#.#..#..#..#.#.#...#..#.#.#.#..#..#..#..#.#....................................................................
.#.##.###.#####.##.#.##.###.#.#.##.###.#.#.#.##.#.##.###...######.#############.#####.#################.########################
.#.#...#...#.....#.#..#..#..#.#.#...#..#.#.#.#..#..#..#..###.#.#...#..#...#.#.###..#..#.#...#.#.#...............................
.#.##.###.#####.##.#.##.###.#.#.##.###.#.#.#.##.#.##.###.#.#.#.##.###.##.##.#.#.##.####.##.##.#.################################
................................................................................................................................
#.#######.##################.######################.#.####.###################.#####################.##.####.##################.
#.......#.#.#.#.#.#.#.#.#.......#.............#.#.#.#.#.#...#.#.#..#.#..#.#..###.#.#.#.#.#.#.#.#.#.#.#..#.#....#.#.#.#.#.#.#..##
..####.####...#.#.#.#.#.####################.##.#.#.#...##.##.#.##.#.#.##.#.##.#.#.#.#.#.#.#.#.#.#.######.###.##.#.#.#.#.#.##.#.
#.#.....#.#.###.#.#.#.#.#.......#.............#.#.#.#.#.#...#...................................................................
..#######.#...#.#.#.#.#.#####.#####.###########.#.############.#####################.##.##.#.#.#.##.##.######.##################
#.......#.#.###.#.#.#.#.#.......#...#.#.#.#.#.#.#.#...#.#.#.#..#.#.#.#..#.#.#.#.#..#..#..#.#.#.#.#..#..#........................
..#######.#...#.#.#.#.#.######.####...........#.#.#.###.....####.#.#.#.##.#.#.#.##.#############################################
#.......#.#.###.#.#.#.#.#.......#.#.###########.#.#...###.###..#.#.#.#..#.#.#.#....#.#.#.#.#.#.#.#..#..#..#.#...................
..#######.#.#.#.#.#.#.#.######.##.............#.#.#.###.#.#.#.##.#.#.#.##.#.#.###.##.#.#.#.#.#.#.##.##.#.##.######.#############
#.#.#.#.#.#.#.#.#.#.#.#.#.......####.##########.................................................................................
........#.#...#.#.#.#.#.#####.###.#..#.#.#....#######.#####.#############################.#.#.#############.#############.######
#.##.####.##.##.#.#.#.#.#.#.#.#.#.##.#.#.###.##.#.#.###.#.###.#.#.#.#.#...#.#.#.#.#.#.#.#####...#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.
..#.....#.#...#.#.#.#.#.#.......#.#..#...#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#..#..#.#...............................
#.#######.##.##.#.#.#.#.######.##.##.##.##.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##################################
................................................................................................................................
########.#############.##################.#.##.##.#######.#.#.###########.######################################################
.....#......#.#..#..#..#...#.#.#.#..#...#.#.#..#..#.#...#######.#...#..#...#.#...#.#...#.#..#.#.#..#.....#.#.#.#................
###.####.##.#.#.###.##.#.###.#.#.#.##.#############.#.###.#.#.#.#.###.##.#.#.#.###.###.#.##.#.#.#.######.........###############
.....#...#..#.#..#..#..#...#.#.#.#..#...#.........#.#...#...#.#.#...#..#####.#...#.#.#.#..#.#.#.#..#...#.#.#.#.#................
###.####.####.#.###.##.#.###.#.#.#.##.#########.###.#.####.##.#.#.###.##...#.#.###...#.#.##.#.#.#.####.#.#######################
.....#......#.#..#..#..#...#.#.#.#..#...#.#.#.#.#.#.#...#...#.#.#...#..#.###.#...#.###.#.#..#.#.#..#.#..........................
##.#.###.####.#.###.##.#.###.#.#.#.##.###.........#.#.####.##.#.#.#.#.##...#.##.##.#...#.##.#.#.#.##...#.#################.#####
.#.###...#..#.#..#..#..#...#.#.#.#..#...#####.#####.#...#...#.#.#.###..#.###.#...#.###.#.#..#.#.#..#####...#....................
.....###...##.#.###.##.#.###.#.#.#.##.###.#.#.....#.#.####.##.#.#...#.##.#.#.##.##.#...#.##.#.#.#.##.....###.#.##############.##
##.###...#..#.#..#..#..#.#.#.#.#.#..#.#.#.....#.###.#...#...#.#.#.###..#...#.#...#.###.#.#..#.#.#..#####.#.#.#.#................
.#.#.###.####.#.###.####.#.#.#.#.#.##...#####.#...#.##.###.##.#.#...#.###.##.##.##.#.#.#.##.#.#.#.##.#.#.#.#####################
.....#...#..#.#..#..#..#...#.#.#.#..#.###..#..#####.#...#...#.#.#.###...........................................................
###.####.#.##.#.###.#.###.##.#.#.#.##.#.##.##.#.#.#.##.###.##.#.#.#.##########################################################.#
................................................................................................................................
#.###.###.################################.####################.################.###########.#######.###################.##.####
....#..#..#.#..#.#.#.#.#.#..#.#.#.#.#.#.#...#.#.#..#.#.#.#.#.#..#.#.#.#..#.#.#.###.#.#..#.#..#.#.#.###.#.#.#.#.#.#.#.#.#.#......
#.#########.##.#.#.#.#.#.#.##.#...#.#.#.#.#.#.#.#.##.#.#.#.#.####.#.#.#.##.#.#.#.#.#.##.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#########
....#..#..#.#..#.#.#.#.#.#..#.#.###.#.#.#####...................................................................................
#.####.#.##.##.#.#.#.#.#.#.##.#...#.#.#.#...##########.######.##################################.########.#.##############.#####
....#..#..#.#..#.#.#.#.#.#..#.#.###.#.#.#.###.#.#..#.###.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#..#.#.#.###.#.#.#..###.#.#...............
#.#.##.#.##.##.#.#.#.#.#.#.##.#...#.#.#.#.#.#.#.##.#.#.#.#.####.#.#.#.#.#.#.#.#.#...#.##.#.#.#.#.#.#.#.####.#.#.#########.######
..###..#..#.#..#.#.#.#.#.#..#.#.###.#.#.#...#.#.#..#.#.#.#.#..#.#.#.#.#.#.#.#.#.#.###.#..#......................................
#.#.##.#.##.##.#.#.#.#.#.#.##.#.#.#.#.#.##.##.#.##.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.##.#######################################
................................................................................................................................
###.#################################.##########.######.#.#.####################.###############################################
.#....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#...#.#.#######.#.#.#.#.#.#.#.#.#.....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.##.###.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.#...#.#.#.#.#.#..#..#.#.#.#.#.#.#.#...#######...........................................
.#..#.#.#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.##.##.#####.#.##.#.##.#.#.#.#.#.#.##.##.#.#.####.#######################################
.##.............................................................................................................................
.#..########################################.###################################################################################
.##...#.......#.#.#.......#.#.#.#.#.#...#.#...#.#.#.#...........................................................................
.#..#.#####.###.#.######.##.#.#.#.#.#.###.#####.#...###############.############.#.##.#.#.#.#.#.#.#.#.#.#.###.#.#.##.#####.#####
.##.###.#.#.#.#.#.#.......#.#.#.#.#.#.#.#.#.#.#...###.#.#.#...#.#.....#...#..#.###..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.........
.#....#.......#.#.###.#.###.#.#.#.#.#...#.#...#.#...#.#.#.#.###.###.###.###.##.#.####.#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.#.#.#.
.##.######.####.#.#.###.#.#.#.#.#.#.##.##.##.##.#####.#.#.#.#.#.#.....#.#.#.........############################################
.#....#.......#.#.#.......#.#.#.#.#.#...#.#...#.....#.#.#.#...#.###.###...#######.###.#.#.#.#.#.#.#.#.#.#.......................
.##.#######.###.#.######.##.#.#.#.#.##.##.##.##.#####.#.#.##.##.#.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.################.#######
................................................................................................................................
##.########.#.#.#.#.##.#.#.############################################.#############################.######.#.#.#.######.###.##
....#.#..#..#######..#.#.#.#.......#.#.#..#..#.#..#.#.#.#.#.#....#.#.#..#.#..#.#.#.#.#.#..#..#..#.#.###..#.#.#.#.#..#.#.###.#.#.
.#.##.##.####.....###############.##...#.##.##.##.#.#.#.#.#.#.####.#.####.#.##.#.#.#.#.#.##.###.#.#.#.##.#.#.#.#.#.##.#.........
.#..#.#..#..####.##..#.....#.......#.###..#..#.#..#.#.#.#.#.#....#.#.#..#.#..#.#.#.#.#.#..#..#..#.#.#.#..#.#.#.#.#....####.#####
##.##.##.#.##.....#.#####.#######.##.#.#.##.##.##.#.#.#.#.#.#.####.#.#.##.#.##.#.#.#.#.#.##.###.#.#.#.##.#.#.#.#.#.#.##.........
....#.#..#..###.###..#.....#.......#...#..#..#.#..#.#.#.#.#.#.#..#.#.#..#.#..#.#.#.#.#.#..#..#..#.#.#.#..#.#.#.#.#.#..#.#.#.#.#.
##.##.##.#.##.#.#.#.###.######.#.####.##.##.##.##.#.#.#.#.#.#.##.#.#.#.##.#.##.#.#.#.#.#.##.###.#.#.#.##.#.#####################
.....................#.....#.###.#.#............................................................................................
##.######################.##.......#####.############.######.########.#.#################################################.######
.....................#.....######.##.#......#...#.#.###.........#.#.#####.#.#.#.#.#.............................................
##.######################.##.......#.###.####.###.#.#.#.##.##.###.#.#...#.#.#.#...##############################################
.....................#.....######.##.#......#.#.#.#.#.#.#..#..#.#.#.##.##.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....
##.###################.#.###.......#.#.#.####...#.#.#.#######...#.#.#...#.#.#.#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.#...###.##
.....................###.#.######.##.###....##.##.#.#.#...#.#.###.#.##.##.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#.
##.########.#.#.##.#.#.....#.......#.#...##.#...#.#.#.#.###.....#...............................................................
....#.#.#.#.#.#..#.#.####.#######.##.###.#..##.##.#.#.#.#.###.######.#######.###################.###.#.##.######################
##.##.#.#.############.....#.......#.#...####...#.#.#.#.........#.#..#.#.#....#.#.#.#.#.#.#.#.#..#.###.#..#.#..#.#..............
.....................####.#######.##.###....##.##.#.#.###.#######.####.#.#.#.##.#.#.#.#.#.#.#.####.#.######.##.#...#.#.#.###.###
##.###################.....#.......#.#...####...#.#.#.#.........#.#..#.#.###..#.#.#.#.#.#.#.#.#..#.#.#.#..#.#..#.#.#.#.#.#...#..
.....................####.#######.##.###....##.##.#.#.###########.#.##.#.#.#.##.#.#.#.#.#.#.#.##.#.#.#.##.#.##.#.#.#.#.#.###...#
.#.####.##############.....#.......#.#...#.##...#.#.#.#.........#.#..#.#.#....#.#.#.#.#.#.#.#.#..#.#.#.#..#.#..#.#.#.#.#.#...#..
##.#.................####.###.######.###.#..##.##.#.#.########.##.#.##.#.###.##.#.#.#.#.#.#.#.##.#.#.#.##.#.##.#.###############
...###################.....#.......#.#.#.####...................................................................................
##...................####.######.#.#.#......##.##########################.######################################.#####.#########
...###################.....#.#.#.###.###.####...#.#..#.#.#.#.#..#.#.#.#.###.#...#.#.#.#.#.#..#.#.#.#.#.#.#.#.#.###.#.###........
##.#.#.#.#.#.#.#.#.#.####.##.......#.#......##.##.#.##.#.#.#.#.##.#.#.#.#.#.##.##.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.###.#####
.....................#.....######.##.###.####...................................................................................
##.###########.#.#.#.###.###.......#.#......####.####.###############################.###.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.......#.#.#...#######.....###.#.###.###.##.#.#...#.....#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.###.################
##.#####...#####.....####.##.###.#.#.#....###.#######.###.###...#.#.......#.#.#.#...#...#.#.#.#####.#.#.#.#.#...#.#.#.#.#.#.#.#.
.......##.##.#.##.####.....#.#.#.#.#.###.##.#.#...#.....#.#.##.##.##.###.##.#.#.##.##.###.#.#.#.....#.#.#.#.###.................
##.#.#.#.............###.###.......#.#....#.#.#.#####.###...#...#.#..#....#.#.#.#...#...#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.
.#.################.##.#.#.######.##.###.##.#.#.#.#.#.#.##.###.##.##.######.#.#.##.#############################################
................................................................................................................................
.###.####.##########.####################################################.#######################.#.#.#.#.#.#.#.#.#.##.#########
...#..#.#...#.....#.......#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...........
.###.##...#####.###.##.####.#.#.#.#.#.#.#...#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.###.#.#...#.#...################################
...#..###...#.#.#.#.#..#..#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.###.##...###.....#.##...##.....................................................................................................
...#..###...####.##.#..#..##########.#################.################.######################################.######.#.#.#.#.#.
.###.##...###.....#########.#.#.#.#...#.#.#.#.#.#.#.#..#.#.#.#.#.#.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..###.#..############
...#..###.#.####.##.#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.####.#.#.#.#.#.#.####.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.##.#.#.#.#.#.#.
.###.##.........................................................................................................................
...#..#.#.###.#####.##.##.#.#.#.#.#.#.#.#.#.#.#################################.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.##.
.###.##.#.#.#.....#.#...#.#.###.#.#####.#.###..#.#.#.#....#.#..#.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#.#..
.#.#..#.#...#.#####.##.##.#.#...#.#.....#.#...##.#.#.##.###...##.#.##.#.#.#.#.##################################################
...#.##.#.###.....#.#...#.#.###.#.#####.#.###..#.#.#.#..#.#.#..#.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..............
.###..#.#.#.#.#.#.#.##.##.#.#...#.#.....#..#..##.#.#.##.#.####.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.############.##
...#.##.#...#.#####.#...#.#.###.#.##.##.#.###...................................................................................
.###..#.#.###.#.#.#.##.##.#.#...#.#..#..#..#..###.#.#.####.###.##.#.#.#.#.##.##.##############.#################################
...#.##.#...#.....#.#...#.#.###.#.#####.#.###.#.#.#.#.#.....#...#.#.#.#.#.#...#...#.............................................
.###..#.#.###.##.##.##.##.#.#.#.#.#.....#.#.....#.#.#.###########.#.#.#.#.##.##.#######################.########################
...#.##.#.#.#.#...#.#...#.#...#.#.#####.#.#.#.###.#.#.......#.#.#.#.#.#.#.#...#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#..#.#...#.#.#.#.#.#.#.#.#.#.#.#.....#.#.#...#.#.#.#.#.#.#.....#.#.#.#.#.#.#.#.#.............................................

Score: 8066
This is the unedited solution from the dynamic programming algorithm.
Validate
.#.#.#.#...#...#.#..#..#.#.#.#...#.#.#.#.#.#.#.#................................................................................
.#.#.#.##.##.###...##.##.#.#.###.....#.#.#.#...#.##########.###########.########.##################.#################.#.#.#.#.#.
.#.#.#.#...#...#.#..#..#.#.#...#.##.##.#.#.#.###...#.#.#.#..#.#.#.#.#.###.#.#..#.#.#.#.#.#.#.#.#.#..#.#.#.#..#.#.#.#..##########
.#.#.#.##.###.##.####.##.#.#.###.#...#.#.#.#.#...###.#.#.####.....#.#.#.#.#.##.###.#.#.#.#.#.#.#.####.#.#.#.##.#.#.####.#.#.#.#.
.#.#.#.#...#...#....#..#.#.#.#...#####.#.#.#.###...#.#.#.#..##.####.............................................................
.#.#.#.##.###.##.####.##.#.#.###.....#.#.#.#.#.#.###.#.#.#.##.....####.####################################################.###.
.#.#.#.#...#...#....#..#.#.#.#...#####.#.#.#.#.....#.#.#.#..###.###.#...#..#.#.#.#.#.#.#.#.#.#.#.#..#.#.#.#.#.#.#.#.#.#.#.###.#.
.#.#.#.##.###.##.####.##.#.#.###.#.#.#.#.#.#.###.###.#.#.#.##.#.#.#.##.###.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.##
................................................................................................................................
##.##.###.#############.#############################################################.#######################################.##
.###...#...#.....#.#..#..#..#.#.#.#.#..#.#.#.#..#..#..#....#..#.#.#..#.#..#.#..#.#.#..#.#.#...#.#..#.#.#.#.#.#.#................
.#.##.##.#.####.##.#.######.#.#.#.#.##.#.#.#.##.#.##.####.##.##.#...##.##.#.##.#.#.####.#.##.##.##.#.#.#.#.....##########.######
.#.#...#####.....#.#..#..#..#.#.#...#..#.#.#.#..#..#..#....#..#.#.#..#.#..#.#..#.#.#..#.#.#...#.#..#.#.#.###.###................
.#.##.##.#.####.##.#.##.###.#.#.##.###.#.#.#.##.#.##.####.##.##.#.####.##.#.##.#.#.##.#.#.##.##.##.#.#.#.#...#.####.############
.#.#...#...#..#..#.#..#..#..#.#.#...#..#.#.#.#..#..#..#....#..#.#....#.#..#.#..#.#.#..#.#.#...#.#..#.#.#.###...#..###...........
.#.##.###.###...##.#.##.###.#.#.##.###.#.#.#.##.#.##.###.###.##.###.##.##.#.##.#.#.##.#.#.##.##.##.#.#.#.#.#.###.##.#.##########
.#.#...#...#..#..#.#..#..#..#.#.#...#..#.#.#.#..#..#..#..#.#....................................................................
.#.##.###.#####.##.#.##.###.#.#.##.###.#.#.#.##.#.##.###...######.#############.#####.#################.########################
.#.#...#...#.....#.#..#..#..#.#.#...#..#.#.#.#..#..#..#..###.#.#...#..#...#.#.###..#..#.#...#.#.#...............................
.#.##.###.#####.##.#.##.###.#.#.##.###.#.#.#.##.#.##.###.#.#.#.##.###.##.##.#.#.##.####.##.##.#.################################
................................................................................................................................
#.#######.##################.######################.#.####.###################.#####################.##.####.##################.
#.......#.#.#.#.#.#.#.#.#.......#.............#.#.#.#.#.#...#.#.#..#.#..#.#..###.#.#.#.#.#.#.#.#.#.#.#..#.#....#.#.#.#.#.#.#..##
..####.####...#.#.#.#.#.####################.##.#.#.#...##.##.#.##.#.#.##.#.##.#.#.#.#.#.#.#.#.#.#.######.###.##.#.#.#.#.#.##.#.
#.#.....#.#.###.#.#.#.#.#.......#.............#.#.#.#.#.#...#...................................................................
..#######.#...#.#.#.#.#.#####.#####.###########.#.############.#####################.##.##.#.#.#.##.##.######.##################
#.......#.#.###.#.#.#.#.#.......#...#.#.#.#.#.#.#.#...#.#.#.#..#.#.#.#..#.#.#.#.#..#..#..#.#.#.#.#..#..#........................
..#######.#...#.#.#.#.#.######.####...........#.#.#.###.....####.#.#.#.##.#.#.#.##.#############################################
#.......#.#.###.#.#.#.#.#.......#.#.###########.#.#...###.###..#.#.#.#..#.#.#.#....#.#.#.#.#.#.#.#..#..#..#.#...................
..#######.#.#.#.#.#.#.#.######.##.............#.#.#.###.#.#.#.##.#.#.#.##.#.#.###.##.#.#.#.#.#.#.##.##.#.##.######.#############
#.#.#.#.#.#.#.#.#.#.#.#.#.......####.##########.................................................................................
........#.#...#.#.#.#.#.#####.###.#..#.#.#....#######.#####.#############################.#.#.#############.#############.######
#.##.####.##.##.#.#.#.#.#.#.#.#.#.##.#.#.###.##.#.#.###.#.###.#.#.#.#.#...#.#.#.#.#.#.#.#####...#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.
..#.....#.#...#.#.#.#.#.#.......#.#..#...#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#..#..#.#...............................
#.#######.##.##.#.#.#.#.######.##.##.##.##.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##################################
................................................................................................................................
########.#############.##################.#.##.##.#######.#.#.###########.######################################################
.....#......#.#..#..#..#...#.#.#.#..#...#.#.#..#..#.#...#######.#...#..#...#.#...#.#...#.#..#.#.#..#.....#.#.#.#................
###.####.##.#.#.###.##.#.###.#.#.#.##.#############.#.###.#.#.#.#.###.##.#.#.#.###.###.#.##.#.#.#.######.........###############
.....#...#..#.#..#..#..#...#.#.#.#..#...#.........#.#...#...#.#.#...#..#####.#...#.#.#.#..#.#.#.#..#...#.#.#.#.#................
###.####.####.#.###.##.#.###.#.#.#.##.#########.###.#.####.##.#.#.###.##...#.#.###...#.#.##.#.#.#.####.#.#######################
.....#......#.#..#..#..#...#.#.#.#..#...#.#.#.#.#.#.#...#...#.#.#...#..#.###.#...#.###.#.#..#.#.#..#.#..........................
##.#.###.####.#.###.##.#.###.#.#.#.##.###.........#.#.####.##.#.#.#.#.##...#.##.##.#...#.##.#.#.#.##...#.#################.#####
.#.###...#..#.#..#..#..#...#.#.#.#..#...#####.#####.#...#...#.#.#.###..#.###.#...#.###.#.#..#.#.#..#####...#....................
.....###...##.#.###.##.#.###.#.#.#.##.###.#.#.....#.#.####.##.#.#...#.##.#.#.##.##.#...#.##.#.#.#.##.....###.#.##############.##
##.###...#..#.#..#..#..#.#.#.#.#.#..#.#.#.....#.###.#...#...#.#.#.###..#...#.#...#.###.#.#..#.#.#..#####.#.#.#.#................
.#.#.###.####.#.###.####.#.#.#.#.#.##...#####.#...#.##.###.##.#.#...#.###.##.##.##.#.#.#.##.#.#.#.##.#.#.#.#####################
.....#...#..#.#..#..#..#...#.#.#.#..#.###..#..#####.#...#...#.#.#.###...........................................................
###.####.#.##.#.###.#.###.##.#.#.#.##.#.##.##.#.#.#.##.###.##.#.#.#.##########################################################.#
................................................................................................................................
#.###.###.################################.####################.################.###########.#######.###################.##.####
....#..#..#.#..#.#.#.#.#.#..#.#.#.#.#.#.#...#.#.#..#.#.#.#.#.#..#.#.#.#..#.#.#.###.#.#..#.#..#.#.#.###.#.#.#.#.#.#.#.#.#.#......
#.#########.##.#.#.#.#.#.#.##.#...#.#.#.#.#.#.#.#.##.#.#.#.#.####.#.#.#.##.#.#.#.#.#.##.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#########
....#..#..#.#..#.#.#.#.#.#..#.#.###.#.#.#####...................................................................................
#.####.#.##.##.#.#.#.#.#.#.##.#...#.#.#.#...##########.######.##################################.########.#.##############.#####
....#..#..#.#..#.#.#.#.#.#..#.#.###.#.#.#.###.#.#..#.###.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#..#.#.#.###.#.#.#..###.#.#...............
#.#.##.#.##.##.#.#.#.#.#.#.##.#...#.#.#.#.#.#.#.##.#.#.#.#.####.#.#.#.#.#.#.#.#.#...#.##.#.#.#.#.#.#.#.####.#.#.#########.######
..###..#..#.#..#.#.#.#.#.#..#.#.###.#.#.#...#.#.#..#.#.#.#.#..#.#.#.#.#.#.#.#.#.#.###.#..#......................................
#.#.##.#.##.##.#.#.#.#.#.#.##.#.#.#.#.#.##.##.#.##.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.##.#######################################
................................................................................................................................
###.#################################.##########.######.#.#.####################.###############################################
.#....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#...#.#.#######.#.#.#.#.#.#.#.#.#.....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.##.###.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.#...#.#.#.#.#.#..#..#.#.#.#.#.#.#.#...#######...........................................
.#..#.#.#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.##.##.#####.#.##.#.##.#.#.#.#.#.#.##.##.#.#.####.#######################################
.##.............................................................................................................................
.#..########################################.###################################################################################
.##...#.......#.#.#.......#.#.#.#.#.#...#.#...#.#.#.#...........................................................................
.#..#.#####.###.#.######.##.#.#.#.#.#.###.#####.#...###############.############.#.##.#.#.#.#.#.#.#.#.#.#.###.#.#.##.#####.#####
.##.###.#.#.#.#.#.#.......#.#.#.#.#.#.#.#.#.#.#...###.#.#.#...#.#.....#...#..#.###..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.........
.#....#.......#.#.###.#.###.#.#.#.#.#...#.#...#.#...#.#.#.#.###.###.###.###.##.#.####.#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.#.#.#.
.##.######.####.#.#.###.#.#.#.#.#.#.##.##.##.##.#####.#.#.#.#.#.#.....#.#.#.........############################################
.#....#.......#.#.#.......#.#.#.#.#.#...#.#...#.....#.#.#.#...#.###.###...#######.###.#.#.#.#.#.#.#.#.#.#.......................
.##.#######.###.#.######.##.#.#.#.#.##.##.##.##.#####.#.#.##.##.#.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.################.#######
................................................................................................................................
##.########.#.#.#.#.##.#.#.############################################.#############################.######.#.#.#.######.###.##
....#.#..#..#######..#.#.#.#.......#.#.#..#..#.#..#.#.#.#.#.#....#.#.#..#.#..#.#.#.#.#.#..#..#..#.#.###..#.#.#.#.#..#.#.###.#.#.
.#.##.##.####.....###############.##...#.##.##.##.#.#.#.#.#.#.####.#.####.#.##.#.#.#.#.#.##.###.#.#.#.##.#.#.#.#.#.##.#.........
.#..#.#..#..####.##..#.....#.......#.###..#..#.#..#.#.#.#.#.#....#.#.#..#.#..#.#.#.#.#.#..#..#..#.#.#.#..#.#.#.#.#....####.#####
##.##.##.#.##.....#.#####.#######.##.#.#.##.##.##.#.#.#.#.#.#.####.#.#.##.#.##.#.#.#.#.#.##.###.#.#.#.##.#.#.#.#.#.#.##.........
....#.#..#..###.###..#.....#.......#...#..#..#.#..#.#.#.#.#.#.#..#.#.#..#.#..#.#.#.#.#.#..#..#..#.#.#.#..#.#.#.#.#.#..#.#.#.#.#.
##.##.##.#.##.#.#.#.###.######.#.####.##.##.##.##.#.#.#.#.#.#.##.#.#.#.##.#.##.#.#.#.#.#.##.###.#.#.#.##.#.#####################
.....................#.....#.###.#.#............................................................................................
##.######################.##.......#####.############.######.########.#.#################################################.######
.....................#.....######.##.#......#...#.#.###.........#.#.#####.#.#.#.#.#.............................................
##.######################.##.......#.###.####.###.#.#.#.##.##.###.#.#...#.#.#.#...##############################################
.....................#.....######.##.#......#.#.#.#.#.#.#..#..#.#.#.##.##.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....
##.###################.#.###.......#.#.#.####...#.#.#.#######...#.#.#...#.#.#.#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.#...###.##
.....................###.#.######.##.###....##.##.#.#.#...#.#.###.#.##.##.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#.
##.########.#.#.##.#.#.....#.......#.#...##.#...#.#.#.#.###.....#...............................................................
....#.#.#.#.#.#..#.#.####.#######.##.###.#..##.##.#.#.#.#.###.######.#######.###################.###.#.##.######################
##.##.#.#.############.....#.......#.#...####...#.#.#.#.........#.#..#.#.#....#.#.#.#.#.#.#.#.#..#.###.#..#.#..#.#..............
.....................####.#######.##.###....##.##.#.#.###.#######.####.#.#.#.##.#.#.#.#.#.#.#.####.#.######.##.#...#.#.#.###.###
##.###################.....#.......#.#...####...#.#.#.#.........#.#..#.#.###..#.#.#.#.#.#.#.#.#..#.#.#.#..#.#..#.#.#.#.#.#...#..
.....................####.#######.##.###....##.##.#.#.###########.#.##.#.#.#.##.#.#.#.#.#.#.#.##.#.#.#.##.#.##.#.#.#.#.#.###...#
.#.####.##############.....#.......#.#...#.##...#.#.#.#.........#.#..#.#.#....#.#.#.#.#.#.#.#.#..#.#.#.#..#.#..#.#.#.#.#.#...#..
##.#.................####.###.######.###.#..##.##.#.#.########.##.#.##.#.###.##.#.#.#.#.#.#.#.##.#.#.#.##.#.##.#.###############
...###################.....#.......#.#.#.####...................................................................................
##...................####.######.#.#.#......##.##########################.######################################.#####.#########
...###################.....#.#.#.###.###.####...#.#..#.#.#.#.#..#.#.#.#.###.#...#.#.#.#.#.#..#.#.#.#.#.#.#.#.#.###.#.###........
##.#.#.#.#.#.#.#.#.#.####.##.......#.#......##.##.#.##.#.#.#.#.##.#.#.#.#.#.##.##.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.###.#####
.....................#.....######.##.###.####...................................................................................
##.###########.#.#.#.###.###.......#.#......####.####.###############################.###.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.......#.#.#...#######.....###.#.###.###.##.#.#...#.....#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.###.################
##.#####...#####.....####.##.###.#.#.#....###.#######.###.###...#.#.......#.#.#.#...#...#.#.#.#####.#.#.#.#.#...#.#.#.#.#.#.#.#.
.......##.##.#.##.####.....#.#.#.#.#.###.##.#.#...#.....#.#.##.##.##.###.##.#.#.##.##.###.#.#.#.....#.#.#.#.###.................
##.#.#.#.............###.###.......#.#....#.#.#.#####.###...#...#.#..#....#.#.#.#...#...#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.
.#.################.##.#.#.######.##.###.##.#.#.#.#.#.#.##.###.##.##.######.#.#.##.#############################################
................................................................................................................................
.###.####.##########.####################################################.#######################.#.#.#.#.#.#.#.#.#.##.#########
...#..#.#...#.....#.......#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...........
.###.##...#####.###.##.####.#.#.#.#.#.#.#...#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.###.#.#...#.#...################################
...#..###...#.#.#.#.#..#..#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.###.##...###.....#.##...##.....................................................................................................
...#..###...####.##.#..#..##########.#################.################.######################################.######.#.#.#.#.#.
.###.##...###.....#########.#.#.#.#...#.#.#.#.#.#.#.#..#.#.#.#.#.#.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..###.#..############
...#..###.#.####.##.#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.####.#.#.#.#.#.#.####.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.##.#.#.#.#.#.#.
.###.##.........................................................................................................................
...#..#.#.###.#####.##.##.#.#.#.#.#.#.#.#.#.#.#################################.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.##.
.###.##.#.#.#.....#.#...#.#.###.#.#####.#.###..#.#.#.#....#.#.##.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#.#..
.#.#..#.#...#.#####.##.##.#.#...#.#.....#.#...##.#.#.##.###....#.#.##.#.#.#.#.##################################################
...#.##.#.###.....#.#...#.#.###.#.#####.#.###..#.#.#.#..#.##.###.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..............
.###..#.#.#.#.#.#.#.##.##.#.#...#.#.....#..#..##.#.#.##.#.##.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.############.##
...#.##.#...#.#####.#...#.#.###.#.##.##.#.###...................................................................................
.###..#.#.###.#.#.#.##.##.#.#...#.#..#..#..#..###.#.#.####.###.##.#.#.#.#.##.##.##############.#################################
...#.##.#...#.....#.#...#.#.###.#.#####.#.###.#.#.#.#.#.....#...#.#.#.#.#.#...#...#.............................................
.###..#.#.###.##.##.##.##.#.#.#.#.#.....#.#.....#.#.#.###########.#.#.#.#.##.##.#######################.########################
...#.##.#.#.#.#...#.#...#.#...#.#.#####.#.#.#.###.#.#.......#.#.#.#.#.#.#.#...#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#..#.#...#.#.#.#.#.#.#.#.#.#.#.#.....#.#.#...#.#.#.#.#.#.#.....#.#.#.#.#.#.#.#.#.............................................