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
.#.#.#.#...#...#.#..#..#.#.#.#...#.#.#.#.#.#.#.#................................................................................
.#.#.#.##.##.###...##.##.#.#.###.....#.#.#.#...#.##########.###########.########.##################.#################.#.#.#.#.#.
.#.#.#.#...#...#.#..#..#.#.#...#.##.##.#.#.#.###...#.#.#.#..#.#.#.#.#.###.#.#..#.#.#.#.#.#.#.#.#.#..#.#.#.#..#.#.#.#..##########
.#.#.#.##.###.##.####.##.#.#.###.#...#.#.#.#.#...###.#.#.####.....#.#.#.#.#.##.###.#.#.#.#.#.#.#.####.#.#.#.##.#.#.####.#.#.#.#.
.#.#.#.#...#...#....#..#.#.#.#...#####.#.#.#.###...#.#.#.#..##.####.............................................................
.#.#.#.##.###.##.####.##.#.#.###.....#.#.#.#.#.#.###.#.#.#.##.....####.####################################################.###.
.#.#.#.#...#...#....#..#.#.#.#...#####.#.#.#.#.....#.#.#.#..###.###.#...#..#.#.#.#.#.#.#.#.#.#.#.#..#.#.#.#.#.#.#.#.#.#.#.###.#.
.#.#.#.##.###.##.####.##.#.#.###.#.#.#.#.#.#.###.###.#.#.#.##.#.#.#.##.###.#.#.#.#.#.#.#.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.##
................................................................................................................................
##.##.###.#############.#############################################################.#######################################.##
.###...#...#.....#.#..#..#..#.#.#.#.#..#.#.#.#..#..#..#....#..#.#.#..#.#..#.#..#.#.#..#.#.#...#.#..#.#.#.#.#.#.#................
.#.##.##.#.####.##.#.######.#.#.#.#.##.#.#.#.##.#.##.####.##.##.#...##.##.#.##.#.#.####.#.##.##.##.#.#.#.#.....##########.######
.#.#...#####.....#.#..#..#..#.#.#...#..#.#.#.#..#..#..#....#..#.#.#..#.#..#.#..#.#.#..#.#.#...#.#..#.#.#.###.###................
.#.##.##.#.####.##.#.##.###.#.#.##.###.#.#.#.##.#.##.####.##.##.#.####.##.#.##.#.#.##.#.#.##.##.##.#.#.#.#...#.####.############
.#.#...#...#..#..#.#..#..#..#.#.#...#..#.#.#.#..#..#..#....#..#.#....#.#..#.#..#.#.#..#.#.#...#.#..#.#.#.###...#..###...........
.#.##.###.###...##.#.##.###.#.#.##.###.#.#.#.##.#.##.###.###.##.###.##.##.#.##.#.#.##.#.#.##.##.##.#.#.#.#.#.###.##.#.##########
.#.#...#...#..#..#.#..#..#..#.#.#...#..#.#.#.#..#..#..#..#.#....................................................................
.#.##.###.#####.##.#.##.###.#.#.##.###.#.#.#.##.#.##.###...######.#############.#####.#################.########################
.#.#...#...#.....#.#..#..#..#.#.#...#..#.#.#.#..#..#..#..###.#.#...#..#...#.#.###..#..#.#...#.#.#...............................
.#.##.###.#####.##.#.##.###.#.#.##.###.#.#.#.##.#.##.###.#.#.#.##.###.##.##.#.#.##.####.##.##.#.################################
................................................................................................................................
#.#######.##################.######################.#.####.###################.#####################.##.####.##################.
#.......#.#.#.#.#.#.#.#.#.......#.............#.#.#.#.#.#...#.#.#..#.#..#.#..###.#.#.#.#.#.#.#.#.#.#.#..#.#....#.#.#.#.#.#.#..##
..####.####...#.#.#.#.#.####################.##.#.#.#...##.##.#.##.#.#.##.#.##.#.#.#.#.#.#.#.#.#.#.######.###.##.#.#.#.#.#.##.#.
#.#.....#.#.###.#.#.#.#.#.......#.............#.#.#.#.#.#...#...................................................................
..#######.#...#.#.#.#.#.#####.#####.###########.#.############.#####################.##.##.#.#.#.##.##.######.##################
#.......#.#.###.#.#.#.#.#.......#...#.#.#.#.#.#.#.#...#.#.#.#..#.#.#.#..#.#.#.#.#..#..#..#.#.#.#.#..#..#........................
..#######.#...#.#.#.#.#.######.####...........#.#.#.###.....####.#.#.#.##.#.#.#.##.#############################################
#.......#.#.###.#.#.#.#.#.......#.#.###########.#.#...###.###..#.#.#.#..#.#.#.#....#.#.#.#.#.#.#.#..#..#..#.#...................
..#######.#.#.#.#.#.#.#.######.##.............#.#.#.###.#.#.#.##.#.#.#.##.#.#.###.##.#.#.#.#.#.#.##.##.#.##.######.#############
#.#.#.#.#.#.#.#.#.#.#.#.#.......####.##########.................................................................................
........#.#...#.#.#.#.#.#####.###.#..#.#.#....#######.#####.#############################.#.#.#############.#############.######
#.##.####.##.##.#.#.#.#.#.#.#.#.#.##.#.#.###.##.#.#.###.#.###.#.#.#.#.#...#.#.#.#.#.#.#.#####...#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.
..#.....#.#...#.#.#.#.#.#.......#.#..#...#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#..#..#.#...............................
#.#######.##.##.#.#.#.#.######.##.##.##.##.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.##.##################################
................................................................................................................................
########.#############.##################.#.##.##.#######.#.#.###########.######################################################
.....#......#.#..#..#..#...#.#.#.#..#...#.#.#..#..#.#...#######.#...#..#...#.#...#.#...#.#..#.#.#..#.....#.#.#.#................
###.####.##.#.#.###.##.#.###.#.#.#.##.#############.#.###.#.#.#.#.###.##.#.#.#.###.###.#.##.#.#.#.######.........###############
.....#...#..#.#..#..#..#...#.#.#.#..#...#.........#.#...#...#.#.#...#..#####.#...#.#.#.#..#.#.#.#..#...#.#.#.#.#................
###.####.####.#.###.##.#.###.#.#.#.##.#########.###.#.####.##.#.#.###.##...#.#.###...#.#.##.#.#.#.####.#.#######################
.....#......#.#..#..#..#...#.#.#.#..#...#.#.#.#.#.#.#...#...#.#.#...#..#.###.#...#.###.#.#..#.#.#..#.#..........................
##.#.###.####.#.###.##.#.###.#.#.#.##.###.........#.#.####.##.#.#.#.#.##...#.##.##.#...#.##.#.#.#.##...#.#################.#####
.#.###...#..#.#..#..#..#...#.#.#.#..#...#####.#####.#...#...#.#.#.###..#.###.#...#.###.#.#..#.#.#..#####...#....................
.....###...##.#.###.##.#.###.#.#.#.##.###.#.#.....#.#.####.##.#.#...#.##.#.#.##.##.#...#.##.#.#.#.##.....###.#.##############.##
##.###...#..#.#..#..#..#.#.#.#.#.#..#.#.#.....#.###.#...#...#.#.#.###..#...#.#...#.###.#.#..#.#.#..#####.#.#.#.#................
.#.#.###.####.#.###.####.#.#.#.#.#.##...#####.#...#.##.###.##.#.#...#.###.##.##.##.#.#.#.##.#.#.#.##.#.#.#.#####################
.....#...#..#.#..#..#..#...#.#.#.#..#.###..#..#####.#...#...#.#.#.###...........................................................
###.####.#.##.#.###.#.###.##.#.#.#.##.#.##.##.#.#.#.##.###.##.#.#.#.##########################################################.#
................................................................................................................................
#.###.###.################################.####################.################.###########.#######.###################.##.####
....#..#..#.#..#.#.#.#.#.#..#.#.#.#.#.#.#...#.#.#..#.#.#.#.#.#..#.#.#.#..#.#.#.###.#.#..#.#..#.#.#.###.#.#.#.#.#.#.#.#.#.#......
#.#########.##.#.#.#.#.#.#.##.#...#.#.#.#.#.#.#.#.##.#.#.#.#.####.#.#.#.##.#.#.#.#.#.##.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#########
....#..#..#.#..#.#.#.#.#.#..#.#.###.#.#.#####...................................................................................
#.####.#.##.##.#.#.#.#.#.#.##.#...#.#.#.#...##########.######.##################################.########.#.##############.#####
....#..#..#.#..#.#.#.#.#.#..#.#.###.#.#.#.###.#.#..#.###.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#..#.#.#.###.#.#.#..###.#.#...............
#.#.##.#.##.##.#.#.#.#.#.#.##.#...#.#.#.#.#.#.#.##.#.#.#.#.####.#.#.#.#.#.#.#.#.#...#.##.#.#.#.#.#.#.#.####.#.#.#########.######
..###..#..#.#..#.#.#.#.#.#..#.#.###.#.#.#...#.#.#..#.#.#.#.#..#.#.#.#.#.#.#.#.#.#.###.#..#......................................
#.#.##.#.##.##.#.#.#.#.#.#.##.#.#.#.#.#.##.##.#.##.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.##.#######################################
................................................................................................................................
###.#################################.##########.######.#.#.####################.###############################################
.#....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#...#.#.#######.#.#.#.#.#.#.#.#.#.....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.##.###.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.#...#.#.#.#.#.#..#..#.#.#.#.#.#.#.#...#######...........................................
.#..#.#.#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.##.##.#####.#.##.#.##.#.#.#.#.#.#.##.##.#.#.####.#######################################
.##.............................................................................................................................
.#..########################################.###################################################################################
.##...#.......#.#.#.......#.#.#.#.#.#...#.#...#.#.#.#...........................................................................
.#..#.#####.###.#.######.##.#.#.#.#.#.###.#####.#...###############.############.#.##.#.#.#.#.#.#.#.#.#.#.###.#.#.##.#####.#####
.##.###.#.#.#.#.#.#.......#.#.#.#.#.#.#.#.#.#.#...###.#.#.#...#.#.....#...#..#.###..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.........
.#....#.......#.#.###.#.###.#.#.#.#.#...#.#...#.#...#.#.#.#.###.###.###.###.##.#.####.#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.#.#.#.
.##.######.####.#.#.###.#.#.#.#.#.#.##.##.##.##.#####.#.#.#.#.#.#.....#.#.#.........############################################
.#....#.......#.#.#.......#.#.#.#.#.#...#.#...#.....#.#.#.#...#.###.###...#######.###.#.#.#.#.#.#.#.#.#.#.......................
.##.#######.###.#.######.##.#.#.#.#.##.##.##.##.#####.#.#.##.##.#.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.################.#######
................................................................................................................................
##.########.#.#.#.#.##.#.#.############################################.#############################.######.#.#.#.######.###.##
....#.#..#..#######..#.#.#.#.......#.#.#..#..#.#..#.#.#.#.#.#....#.#.#..#.#..#.#.#.#.#.#..#..#..#.#.###..#.#.#.#.#..#.#.###.#.#.
.#.##.##.####.....###############.##...#.##.##.##.#.#.#.#.#.#.####.#.####.#.##.#.#.#.#.#.##.###.#.#.#.##.#.#.#.#.#.##.#.........
.#..#.#..#..####.##..#.....#.......#.###..#..#.#..#.#.#.#.#.#....#.#.#..#.#..#.#.#.#.#.#..#..#..#.#.#.#..#.#.#.#.#....####.#####
##.##.##.#.##.....#.#####.#######.##.#.#.##.##.##.#.#.#.#.#.#.####.#.#.##.#.##.#.#.#.#.#.##.###.#.#.#.##.#.#.#.#.#.#.##.........
....#.#..#..###.###..#.....#.......#...#..#..#.#..#.#.#.#.#.#.#..#.#.#..#.#..#.#.#.#.#.#..#..#..#.#.#.#..#.#.#.#.#.#..#.#.#.#.#.
##.##.##.#.##.#.#.#.###.######.#.####.##.##.##.##.#.#.#.#.#.#.##.#.#.#.##.#.##.#.#.#.#.#.##.###.#.#.#.##.#.#####################
.....................#.....#.###.#.#............................................................................................
##.######################.##.......#####.############.######.########.#.#################################################.######
.....................#.....######.##.#......#...#.#.###.........#.#.#####.#.#.#.#.#.............................................
##.######################.##.......#.###.####.###.#.#.#.##.##.###.#.#...#.#.#.#...##############################################
.....................#.....######.##.#......#.#.#.#.#.#.#..#..#.#.#.##.##.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....
##.###################.#.###.......#.#.#.####...#.#.#.#######...#.#.#...#.#.#.#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.#...###.##
.....................###.#.######.##.###....##.##.#.#.#...#.#.###.#.##.##.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.###.#.#.
##.########.#.#.##.#.#.....#.......#.#...##.#...#.#.#.#.###.....#...............................................................
....#.#.#.#.#.#..#.#.####.#######.##.###.#..##.##.#.#.#.#.###.######.#######.###################.###.#.##.######################
##.##.#.#.############.....#.......#.#...####...#.#.#.#.........#.#..#.#.#....#.#.#.#.#.#.#.#.#..#.###.#..#.#..#.#..............
.....................####.#######.##.###....##.##.#.#.###.#######.####.#.#.#.##.#.#.#.#.#.#.#.####.#.######.##.#...#.#.#.###.###
##.###################.....#.......#.#...####...#.#.#.#.........#.#..#.#.###..#.#.#.#.#.#.#.#.#..#.#.#.#..#.#..#.#.#.#.#.#...#..
.....................####.#######.##.###....##.##.#.#.###########.#.##.#.#.#.##.#.#.#.#.#.#.#.##.#.#.#.##.#.##.#.#.#.#.#.###...#
.#.####.##############.....#.......#.#...#.##...#.#.#.#.........#.#..#.#.#....#.#.#.#.#.#.#.#.#..#.#.#.#..#.#..#.#.#.#.#.#...#..
##.#.................####.###.######.###.#..##.##.#.#.########.##.#.##.#.###.##.#.#.#.#.#.#.#.##.#.#.#.##.#.##.#.###############
...###################.....#.......#.#.#.####...................................................................................
##...................####.######.#.#.#......##.##########################.######################################.#####.#########
...###################.....#.#.#.###.###.####...#.#..#.#.#.#.#..#.#.#.#.###.#...#.#.#.#.#.#..#.#.#.#.#.#.#.#.#.###.#.###........
##.#.#.#.#.#.#.#.#.#.####.##.......#.#......##.##.#.##.#.#.#.#.##.#.#.#.#.#.##.##.#.#.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.###.#####
.....................#.....######.##.###.####...................................................................................
##.###########.#.#.#.###.###.......#.#......####.####.###############################.###.#.#.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.......#.#.#...#######.....###.#.###.###.##.#.#...#.....#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.###.################
##.#####...#####.....####.##.###.#.#.#....###.#######.###.###...#.#.......#.#.#.#...#...#.#.#.#####.#.#.#.#.#...#.#.#.#.#.#.#.#.
.......##.##.#.##.####.....#.#.#.#.#.###.##.#.#...#.....#.#.##.##.##.###.##.#.#.##.##.###.#.#.#.....#.#.#.#.###.................
##.#.#.#.............###.###.......#.#....#.#.#.#####.###...#...#.#..#....#.#.#.#...#...#.#.#.#.#.#.#.#.#.#..#..#.#.#.#.#.#.#.#.
.#.################.##.#.#.######.##.###.##.#.#.#.#.#.#.##.###.##.##.######.#.#.##.#############################################
................................................................................................................................
.###.####.##########.####################################################.#######################.#.#.#.#.#.#.#.#.#.##.#########
...#..#.#...#.....#.......#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...........
.###.##...#####.###.##.####.#.#.#.#.#.#.#...#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.###.#.#...#.#...################################
...#..###...#.#.#.#.#..#..#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.#.#.#.##.##.##.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.###.##...###.....#.##...##.....................................................................................................
...#..###...####.##.#..#..##########.#################.################.######################################.######.#.#.#.#.#.
.###.##...###.....#########.#.#.#.#...#.#.#.#.#.#.#.#..#.#.#.#.#.#.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..###.#..############
...#..###.#.####.##.#.#.#.#.#.#.#.##.##.#.#.#.#.#.#.####.#.#.#.#.#.#.####.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.##.#.#.#.#.#.#.
.###.##.........................................................................................................................
...#..#.#.###.#####.##.##.#.#.#.#.#.#.#.#.#.#.#################################.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.#.##.
.###.##.#.#.#.....#.#...#.#.###.#.#####.#.###..#.#.#.#....#.#.##.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#.#..
.#.#..#.#...#.#####.##.##.#.#...#.#.....#.#...##.#.#.##.###....#.#.##.#.#.#.#.##################################################
...#.##.#.###.....#.#...#.#.###.#.#####.#.###..#.#.#.#..#.##.###.#.#..#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#..............
.###..#.#.#.#.#.#.#.##.##.#.#...#.#.....#..#..##.#.#.##.#.##.#.#.#.##.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.##.############.##
...#.##.#...#.#####.#...#.#.###.#.##.##.#.###...................................................................................
.###..#.#.###.#.#.#.##.##.#.#...#.#..#..#..#..###.#.#.####.###.##.#.#.#.#.##.##.##############.#################################
...#.##.#...#.....#.#...#.#.###.#.#####.#.###.#.#.#.#.#.....#...#.#.#.#.#.#...#...#.............................................
.###..#.#.###.##.##.##.##.#.#.#.#.#.....#.#.....#.#.#.###########.#.#.#.#.##.##.#######################.########################
...#.##.#.#.#.#...#.#...#.#...#.#.#####.#.#.#.###.#.#.......#.#.#.#.#.#.#.#...#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#..#.#...#.#.#.#.#.#.#.#.#.#.#.#.....#.#.#...#.#.#.#.#.#.#.....#.#.#.#.#.#.#.#.#.............................................
.
\$\endgroup\$code-golf
. \$\endgroup\$