```#!/usr/bin/env python

# Lego
# Phil Bordelon

import os
import sys

DEBUG = os.getenv("DEBUG", False)

# This program is a recursive hog.  We have to set the maximum
# recursion depth a little higher than usual.
sys.setrecursionlimit(1600)

# As usual, we use classes as structures.
class Struct(object):
pass

####
# printConstruction prints a construction.
def printConstruction(cons):

for i in range(cons.height + 2):
to_print = ""
for j in range(cons.width + 2):
loc = cons.map[i][j]
if loc.empty:
if loc.wet:
to_print += "~"
else:
to_print += "."
else:
to_print += "X"
print(to_print)

####
# immerse dunks a construction under water and fills it up.
def immerse(cons):
####

# We could empty the entire structure, but we're lazy; if
# water is in there from a previous run, we'll make use of
# it.  First things first: fill up the entire border with
# water.
for i in (0, cons.height + 1):
for j in range(cons.width + 2):
cons.map[i][j].wet = True
for i in range(1, cons.height + 1):
for j in (0, cons.width + 1):
cons.map[i][j].wet = True

# Now, we loop through the structure, filling any cells
# that are adjacent to extant water, finishing when nothing
# new was filled.

done = False
while not done:

# Assume we're done.  If anything gets wet, we'll unset this.
done = True

for i in range(len(cons.map)):
for j in range(len(cons.map[0])):
this_loc = cons.map[i][j]

if this_loc.empty and not this_loc.wet:

# See if this location gets wet due to being adjacent
# to water.
for i_delta in (-1, 0, 1):
for j_delta in (-1, 0, 1):
new_i = i + i_delta
new_j = j + j_delta
if (new_i >= 0 and new_i < len(cons.map) and new_j >= 0
and new_j < len(cons.map[0])):
if cons.map[new_i][new_j].wet:
this_loc.wet = True
done = False

if DEBUG:
print("After immersion:")
printConstruction(cons)

####
# recursePool recursively marks pools of water with an id.
def recursePool(cons, i, j, pool_id):

this_loc = cons.map[i][j]

# Bail if this location is already marked, isn't water, etc.
if this_loc.pool_id or not this_loc.empty or not this_loc.wet:
return None

# Mark ...
this_loc.pool_id = pool_id

to_return = [(i, j)]

# And recurse on our eight neighbours.
for i_loop in (i - 1, i, i + 1):
for j_loop in (j - 1, j, j + 1):
if (i_loop >= 0 and i_loop < len(cons.map) and
j_loop >= 0 and j_loop < len(cons.map[0])):
pool_locs = recursePool(cons, i_loop, j_loop, pool_id)
if pool_locs:
to_return.extend(pool_locs)

####
# markPools marks the various pools in the construction with unique integers.
def markPools(cons):

# First, mark all locations as unpooled.
for i in range(len(cons.map)):
for j in range(len(cons.map[0])):
cons.map[i][j].pool_id = None

# Now, loop through each location; if it's water,
# we check to see if it's already pooled.  If not, we call recursePool()
# to have it flagged as part of a pool.  Easy!

curr_pool_id = 0
cons.pool_dict = {}
for i in range(len(cons.map)):
for j in range(len(cons.map[0])):
this_loc = cons.map[i][j]
if this_loc.empty and this_loc.wet and not this_loc.pool_id:
curr_pool_id += 1
pool_locs = recursePool(cons, i, j, curr_pool_id)
cons.pool_dict[curr_pool_id] = pool_locs

# Return the number of pools thus found.
return curr_pool_id

####
# drain drains the water from a construction.
def drain(cons):

# Draining is a repeated process.  We drain water down and also
# sideways.  Basically, as long as you don't have to go up to an
# already drained location, you're okay.

# We did the border for a reason, and here it is: we know the entire
# border will drain, giving us guaranteed dry bits to run against.
# Use that.
for i in (0, cons.height + 1):
for j in range(cons.width + 2):
cons.map[i][j].wet = False
for i in range(1, cons.height + 1):
for j in (0, cons.width + 1):
cons.map[i][j].wet = False

# Now we do the simulation.  Up is, conveniently, always (-1, 0).
# The directions that water can drain are all of the other standard
# deltas.
deltas = ((0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
up_delta = (-1, 0)
done = False
while not done:

# As before, we assume we're done and unmark this if we do things.
done = True
for i in range(1, cons.height + 1):
for j in range(1, cons.width + 1):
this_loc = cons.map[i][j]
if this_loc.empty and this_loc.wet:

for delta in deltas:
adj_loc = cons.map[i + delta[0]][j + delta[1]]

# Drain!
this_loc.wet = False
done = False

if DEBUG:
print("After basic draining:")
printConstruction(cons)

# We've done the easy bit.  Now we have to handle pools.  The way we do
# this is:
#
# * We mark every bit of water with a unique number.
# * We coalesce those numbers so that connected water all has the same
#   number.
# * For each number, we find the lowest surface according to the delta,
#   and eliminate all water higher than that with the same number.
#
# Surfaces have empty space above them, /not/ blocks, as the empty space
# implies draining.
#
# Of course, we can combine those first two steps by doing a recursive
# mark-and-fill run on each bit of water we touch.  Which is precisely
# what we'll do.
#
# Problems occur when this draining makes the water separate into different
# pools.  That means we have to run this until no pools drain any more
# water, and only drain the highest level of water from a pool.

done = False
while not done:

# Assume draining is complete.  Unmark otherwise.
done = True

pool_count = markPools(cons)

# Determine what directions are "ups" for finding surfaces.
ups = ((-1, -1), (-1, 0), (-1, 1))

# We now go through the pool dictionary, finding surfaces and emptying
# spaces that are higher than the lowest surface.
for pool_list in cons.pool_dict.values():
lowest_surface = None
highest_height = None
for i, j in pool_list:
for up in ups:
up_loc = cons.map[i + up[0]][j + up[1]]
if up_loc.empty and not up_loc.wet:

# Surface!  If we haven't found a surface yet, this is
# obviously the lowest; otherwise, we check the deltas.
surface_height = i + up[0]
if not lowest_surface:
lowest_surface = surface_height
elif surface_height > lowest_surface:
lowest_surface = surface_height

# Also track the highest height of water.
if not highest_height:
highest_height = i
elif i < highest_height:
highest_height = i

# Now that we know the lowest surface and the highest bits of water,
# drain the water that's at the highest level if it's higher than
# the lowest surface.
for i, j in pool_list:
if i <= lowest_surface and i == highest_height:

# Too high.  Drain and note we're not done.
cons.map[i][j].wet = False
done = False

if DEBUG:
print("After pool draining:")
printConstruction(cons)

####
# countWater counts the amount of water remaining in a construction.
def countWater(cons):

total = 0
for i in range(len(cons.map)):
for j in range(len(cons.map[0])):
if cons.map[i][j].wet:
total += 1

####
# rotate rotates the construction.
def rotate(cons):

new_map = []

# Build it.  Loop through the rows as columns and vice versa.
width = len(cons.map[0])
for j in range(width):
new_row = []
for i in range(len(cons.map)):
new_row.append(cons.map[i][width - 1 - j])
new_map.append(new_row)

# Replace the old map with the new one.
cons.map = new_map

# Switch the height and width.
cons.height, cons.width = cons.width, cons.height

####
# simulate runs the dunk-and-empty simulation.
def simulate(cons):

# We'll track the water held in the four directions via a list.
water_held = []

# There are four directions that water can flow, and therefore four
# deltas to run simulations on.  That said, we don't actually care about
# the deltas themselves, as we're just going to rotate the entire structure
# three times.  (I tried doing clever things with the deltas, but the math
# got ridiculous.)

for direction in range(4):

# Part 1: Immersion.
immerse(cons)

# Part 2: Draining.
drain(cons)

# Part 3: Counting.  Count the number of cells that still have water.
water_remaining = countWater(cons)

water_held.append(water_remaining)

# Lastly, rotate the entire structure if this isn't the last run (no
# need to waste CPU on a last rotation).
if direction < 3:
rotate(cons)

return water_held

####
# getEmpty builds an empty location.
def getEmpty():

loc = Struct()
loc.empty = True
loc.wet = False

return loc

####
# getBlock returns a location with a block.
def getBlock():
loc = Struct()
loc.empty = False
loc.wet = False

return loc

def main():

for dataset_loop in range(dataset_count):

# New construction.
cons = Struct()

cons.height, cons.width = [int(x) for x in

# Read in the construction.  We surround the entire thing with
# empty space, because that makes later water calculations easier.
cons.map = []

for i in range(cons.height + 2):
new_row = []
if i == 0 or i == cons.height + 1:

# These are the empty rows at top and bottom.
for i in range(cons.width + 2):
new_row.append(getEmpty())
else:

# Add a blank to the left side of the row ...
new_row.append(getEmpty())

# Handle all of the actual locations.
for elem in representation:
if elem == ".":
new_row.append(getEmpty())
else:
new_row.append(getBlock())

# Add a blank to the right side too.
new_row.append(getEmpty())

# Add the row to the map.
cons.map.append(new_row)

if DEBUG:
printConstruction(cons)

# All right.  Time to simulate.
water_held = simulate(cons)

# Sort the list of amount of water held.
water_held.sort()
water_held.reverse()

# Print!
print(" ".join([repr(x) for x in water_held]))

if "__main__" == __name__:
main()
```