TheMatt2/golf_island.py

## golf_island.py
L,S,O,R,F=len,set,None,range,frozenset
U,N,J,D,I=S.update,F.union,F.isdisjoint,F.difference,F.intersection
def r(n,a,c):
 U(c,P)
 if L(I(N(Q[n],C[n]),a))<2:return 1
 w=D(P,N(a,[n]));e=S();u=S([next(iter(w))])
 while u:n=I(Q[u.pop()],w);U(u,D(n,e));U(e,n)
 return L(e)==L(w)
def T(a,o,i,c,k):
 s,p,m=a
 for _ in o:
  t=s,p,N(m,[_]);e=D(o,[_])
  if t[2] in c:o=e;continue
  c.add(t[2]);n=D(Q[_],m);U(k,n)
  if not J(i,n)or not r(_,N(m,i),k):o=e
  elif s==L(t[2]):yield t
  else:yield from T(t,N(e,n),i,c,k)
s,*p=input().split()
X,Y=eval(s)
A=[]
l=1,-1,0,0
P=F((x,y)for y in R(Y)for x in R(X))
exec("Q%sl,l[::-1]%s;C%s(1,1,-1,-1),l[:2]*2%s"%(('={(x,y):F((x+i,y+j)for i,j in zip(',')if X>x+i>-1<y+j<Y)for x,y in P}')*2))
for a in p:a,x,y=eval(a);k=x,y;A+=[(a,k,F([k]))]
A.sort(reverse=1)
k=F(a[1]for a in A)
p=[O]*L([a for a in A if a[0]!=1])
g,h=p[:],p[:]
i=0
while 1:
 if g[i]is O:h[i]=S();f=O;g[i]=T(A[i],Q[A[i][1]],D(N(k,*p[:i]),[A[i][1]]),S(),h[i])
 try:p[i]=g[i].send(f)[2]
 except:
  f=I(N(k,*p[:i]),h[i]);g[i]=p[i]=O;i-=1
  while J(p[i],f):g[i]=p[i]=O;i-=1
 else:
  i+=1
  if i==L(p):
   z=N(k,*p)
   if not any(J(z,F(zip([x,x+1]*2,[y,y,y+1,y+1])))for x in R(X-1)for y in R(Y-1)):break
   for c in h:U(c,z)
b=[X*['.']for i in R(Y)]
for x,y in z:b[y][x]='#'
for l in b[::-1]:print(''.join(l))

## island.py
#!/usr/bin/python3
#https://codegolf.stackexchange.com/questions/51006/map-of-islands-and-a-river
# Take an input of island data and generate a possible map.
# Edited for python 3 in version 4.
"""
Introduction

For many centuries, there has been a certain river that has never been mapped. The Guild of Cartographers want to produce a map of the river, however, they have never managed to succeed -- for some reason, all the cartographers they have sent to map the river have been eaten by wild animals in the area. A different approach is required.

Input Description

The area is a rectangular grid of cells of length m and width n. The cell in the bottom left would be 0,0, and the cell in the top right would be m-1,n-1. m and n are provided in the input as a tuple m,n.

By using long distance geographical sounding techniques the location of islands around the river have been identified. The size of the islands (i.e. how many cells the island occupies) have also been identified but the shape has not. We supply this information in a tuple s,x,y where s is the size of the island, and x and y are the x and y positions of one particular cell of that island. Each tuple in the input is space separated, so here is an example input:

7,7 2,0,0 2,3,1 2,6,1 2,4,3 2,2,4 8,0,6 1,2,6 3,4,6
To illustrate more clearly, here are is the input on a graph:

 y 6|8 1 3
   5|
   4|  2
   3|    2
   2|
   1|   2  2
   0|2
     =======
     0123456
     x
Output Description

Output a map using ASCII characters to represent parts of the area. Each cell will either be # (land) or . (water). The map should follow these rules:

Definition. An island is a orthogonally contiguous group of land cells that is bounded entirely by river cells and/or the border of the area.
Definition. A river is an orthogonally contiguous group of water cells that is bounded entirely by land cells and/or the border of the area, and does not contain "lakes" (2x2 areas of water cells).
Rule. The map shall contain exactly one river.
Rule. Each numbered cell in the input shall be part of an island containing exactly s cells.
Rule. Every island in the map shall contain exactly one of the numbered cells in the input.
Rule. There exists a single unique map for every input.
Here is the output of the example input:

#.#.##.
#....#.
#.##...
##..##.
###....
...##.#
##....#
Here is another input and output.

Input:

5,5 3,0,1 1,4,1 2,0,4 2,2,4 2,4,4
Output:

#.#.#
#.#.#
.....
###.#
.....
"""
# Island 2 Improvements.
# Global varibles, max dimensions.
# Set handling, new management system of generating shapes.

# Use named tuples for something like a class structure.
fs=frozenset
import time
from collections import namedtuple
# Board is an area
Area=namedtuple('Area','size peek members')
#_Area=Area
##class Area(_Area):
##    'Area(size, peek, members)'
##    def __new__(_cls,size,peek,members):
##        'Create new instance of Area(size, peek, members)'
##        # Just enforcing the typing.
##        assert isinstance(size,int)
##        assert len(peek)==2
##        assert isinstance(peek[0],int)and isinstance(peek[1],int)
##        assert isinstance(members,fs)
##        assert peek in members
##        assert all(len(member)==2for member in members)
##        assert size>=len(members)
##        return super(Area,_cls).__new__(_cls,size,peek,members)
def load_text(text):
    global X,Y,ALL_POINTS,get_plus,get_cross
    size,*plots=text.split()
    X,Y=eval(size)
    l=[]
    for a in plots:a,x,y=eval(a);l.append(Area(a,(x,y),fs([(x,y)])))
    # Generate all points now to fit the size of the board.
    ALL_POINTS=fs((x,y)for y in range(Y) for x in range(X))
    get_plus={(x,y):fs((i,j)for(i,j)in((x,y+1),(x,y-1),(x+1,y),(x-1,y))if X>i>-1<j<Y)for x in range(X)for y in range(Y)}.get
    get_cross={(x,y):fs((i,j)for(i,j)in((x+1,y+1),(x+1,y-1),(x-1,y-1),(x-1,y+1))if X>i>-1<j<Y)for x in range(X)for y in range(Y)}.get

##    l=1,-1,0,0
##    get_plus={(x,y):fs((x+i,y+j)for i,j in zip(l,l[::-1])if X>x+i>-1<y+j<Y)for x in range(X)for y in range(Y)}.get
##    get_cross={(x,y):fs((x+i,y+j)for i,j in zip((1,1,-1,-1),l[:2]*2)if X>x+i>-1<y+j<Y)for x in range(X)for y in range(Y)}.get
##    l=0,0,1,-1
##    d=lambda i,j:X>x+i>-1<y+j<Y
##    get_plus={(x,y):F(filter(d,zip(l,l[::-1])))for x in range(X)for y in range(Y)}.get
##    get_cross={(x,y):F(filter(d,zip([1,1,-1,-1],l[2:]*2)))for x in range(X)for y in range(Y)}.get
##    get_plus={(x,y):F((x+i,y+j)for i,j in((0,1),(0,-1),(1,0),(-1,0))if X>x+i>-1<y+j<Y)for x in R(X)for y in R(Y)}.get
##    get_plus={(x,y):F((x+i,y+j)for i,j in zip(if X>x+i>-1<y+j<Y)for x in R(X)for y in R(Y)}.get
##    get_plus={(x,y):F((i,j)for(i,j)in((x,y+1),(x,y-1),(x+1,y),(x-1,y))if X>i>-1<j<Y)for x in R(X)for y in R(Y)}.get
##    get_cross={(x,y):F((x+i,y+j)for i,j in((1,1),(1,-1),(-1,-1),(-1,1))if X>x+i>-1<y+j<Y)for x in R(X)for y in R(Y)}.get
##    get_cross={(x,y):F((i,j)for(i,j)in((x+1,y+1),(x+1,y-1),(x-1,y-1),(x-1,y+1))if X>i>-1<j<Y)for x in R(X)for y in R(Y)}.get
    return l
def print_plots(*args,**keywords): # Nice, fashionable for debugging.
    """print_plots(points,FG='#',BG='.'):
       Turn the points into a grid. (0,0) is bottom left.
    """
    line_length=15
    FG=keywords.pop('FG','#')
    BG=keywords.pop('BG','.')
    # highlight is a value that is noted on all boards.
    peeks=keywords.pop('peeks',())
    combined=keywords.pop('combined',0)
    highlight=keywords.pop('highlight',None)
    if keywords:
        raise TypeError("print_plots() got an unexpected keyword argument %r"%
                        keywords.popitem()[0])
    if combined and len(args)>1:
        args+=(fs().union(*filter(None,args)),)
    elif not args and (highlight or peeks):
        args=[fs()] # Do one plot.
    for k in range(0,len(args),line_length):
        text=[]
        for plot in args[k:k+line_length]:
            if plot is None:plot=()
            board=[[BG]*X for i in range(Y)]
            for peek in peeks:
                a,(x,y)=peek.size,peek.peek
                board[y][x]=str(a)
            for x,y in plot:board[y][x]=FG
            if highlight:
                x,y=highlight
                board[y][x]='!'
            for i,line in enumerate(reversed(board)):
                if i==len(text):
                    text.append(''.join(line))
                else:
                    text[i]+=' '+''.join(line)
        print('\n'.join(text)+'\n')
def print_plot(plot):
    # Little for golf.
    """Turn points into a grid and print them."""
    if PRINTS:print("Solution:")
    board=[['.']*X for i in range(Y)]
    for x,y in plot:board[y][x]='#'
    for line in board[::-1]:print(''.join(line))
##get_cross=lambda(x,y):fs((i,j)for i,j in((x+1,y+1),(x+1,y-1),(x-1,y-1),(x-1,y+1))if X>i>-1<j<Y)
##get_plus={(x,y):fs((i,j)for i,j in((x,y+1),(x,y-1),(x+1,y),(x-1,y))if X>i>-1<j<Y)for x in range(X)for y in range(Y)}.get
##get_plus=lambda(x,y):fs((i,j)for i,j in((x,y+1),(x,y-1),(x+1,y),(x-1,y))if X>i>-1<j<Y)
##get_plus=lambda(x,y):fs((i,j)for i,j in zip((x,x,x+1,x-1),(y+1,y-1,y,y))if X>i>-1<j<Y)
##get_plus=lambda(x,y):fs(filter(lambda(i,j):X>x+i>-1<y+j<Y,zip((0,0,1,-1),(1,-1,0,0))))
##get_plus=lambda(x,y),l=(0,0,1,-1):fs(filter(lambda(i,j):X>x+i>-1<y+j<Y,zip(l,l[::-1])))
##get_plus=lambda(x,y):fs(filter(lambda(i,j):X>x+i>-1<y+j<Y,((0,1),(0,-1),(1,0),(-1,0))))
##get_plus=lambda(x,y):fs((x+i,y+j)for i,j in((0,1),(0,-1),(1,0),(-1,0))if X>x+i>-1<y+j<Y)
##get_plus=lambda(x,y),l=(0,0,1,-1):fs((x+i,y+j)for i,j in zip(l,l[::-1])if X>x+i>-1<y+j<Y)
##get_plus=lambda p:fs((p[0]+i,p[1]+j)for i,j in((0,1),(0,-1),(1,0),(-1,0))if X>p[0]+i>-1<p[1]+j<Y)
##def get_plus((x,y)):return fs(filter(lambda p:X>p[0]>-1<p[1]<Y,((x,y+1),(x,y-1),(x+1,y),(x-1,y))))
def still_1_river(new_island,all_islands,checked):
    """Check to see if a river is still all connected."""
    checked.update(ALL_POINTS)
    # Checks only a small region.
    # ...
    # .#. <-- This situation means the river is good.
    # ...
    # And if there is only one other island in this box, then we know the river
    # is still find.
    # #.. .#. ..# ... ... ... ... ...
    # .#. .#. .#. .## .#. .#. .#. ##. <-- Also river is still good.
    # ... ... ... ... ..# .#. #.. ...
    # Any more then two, there is no longer a guarantee the river is good.
    # HOWEVER, it tends to be a very good guess that the river is still good.
    # So, lets guess that any group of three, is also clean.
    if len(get_plus(new_island).union(get_cross(new_island)).intersection(all_islands))<2:
        # This is a good river.
        return True
    # If the tricks fail, do a full is_1_river check.
    return is_1_river(all_islands.union([new_island]),checked)
def is_1_river(all_points,checked):
    """Check if all of the water connects to create 1 river."""
##    assert isinstance(all_points,fs)
    # So all_points is a set of all islands on the map.
    # My question is, do all of the surronding water connect?
    # First off, make a list of all of the water on the map.
    all_water_points=ALL_POINTS.difference(all_points)
    # Now test if all of these water points are connected.
    for start_water in all_water_points:
        break # Trick to just grab some water element.
    connected_water=set()
    unexplored_water=set([start_water])# Water that may lead to other water.
    while unexplored_water:
        # This will cycle until all water is explored.
        water=unexplored_water.pop()
        neighbor_water=get_plus(water).intersection(all_water_points)
        unexplored_water.update(neighbor_water.difference(connected_water))
        connected_water.update(neighbor_water)
    # Now that we have used all unexplored_water, check if connected_water is everything.
##    assert (len(connected_water)==len(all_water_points))==(connected_water==all_water_points)
##    if len(connected_water)==len(all_water_points):
##        return True
##    else:
##        return checked.update(ALL_POINTS)
    return len(connected_water)==len(all_water_points)or checked.update(ALL_POINTS)
##    return len(connected_water)==len(all_water_points)
def is_lakes(plot):
    # Really, just perform a test here that there are no lakes.
    # Every 2x2 areas has at least 1 land and is not all water.
    for y in range(Y-1):
        for x in range(X-1):
            lake=fs([(x,y),(x+1,y),(x,y+1),(x+1,y+1)])
            if plot.isdisjoint(lake):
                # There is no islands in this 2x2
                return lake
##def is_lakes(plot):
##	return any(map(plot.isdisjoint,(fs([(x,y),(x+1,y),(x,y+1),(x+1,y+1)])for x in range(X-1)for y in range(Y-1))))
def generate_area(area,other_islands,checked):
    # Generate areas.
##    assert isinstance(area,Area)
##    assert len(area.members)==1
##    assert isinstance(other_islands,fs)
##    assert all(isinstance(x,int)and isinstance(y,int)for x,y in other_islands)
    # There already isn't one river just with other islands.
    # This isn't just bad, that isn't valid.
##    assert is_1_river(other_islands)
    # If the size is 1, we are done right here.
    # There is 1 way to arrange 1 thing.
    if area.size==1:
        yield area # We are done, thank you. Few... that was hard.
        return
    #else:
    # Make the first set of members
    possible_members=get_plus(area.peek)
    # The other islands share 1 or more blocks.
    # This is not a valid start location!
##    assert other_islands.isdisjoint(possible_members)
    # Save areas that are generated so we don't return the same area repeatedly.
    area_cache=set()#This will be passed to the _step_area
    yield from _step_area(area,possible_members,other_islands,area_cache,checked)
##    if 0:
##        print(len(area_cache))
    #This returns a set, everything previous is Areas.
def _step_area(area,possible_members,other_islands,area_cache,checked):
    # Take area, yield all possible member configurations, that are legal.
    # other_islands is the other members that this area can't touch.
    size,peek,members=area
##    assert isinstance(area,Area)
##    assert isinstance(possible_members,fs)
##    assert isinstance(other_islands,fs)# This are points in other islands.
##    assert all(isinstance(x,int)and isinstance(y,int)for x,y in other_islands)
##    assert all(isinstance(x,int)and isinstance(y,int)for x,y in possible_members)
##    assert isinstance(area_cache,set)
##    # Make sure there is no overlap in these 3 sets.
##    assert len(area.members)+len(possible_members)+len(other_islands)==\
##           len(area.members.union(possible_members,other_islands))
    failed_land_points=fs()
    for p_m in possible_members:
        # This is the next cell.
        step_area=Area(size,peek,members.union([p_m]))
        step_possible_members=possible_members.difference([p_m])
        # First, check if this is in area_cache, if so ignore, it has already
        # been returned as a result.
        if step_area.members in area_cache:
            # Don't need to do anything else with this.
            possible_members=step_possible_members
            continue
        # Cache this current area.
        # Note: This step_area has less elements than its size, therefore,
        # step_area will never be yielded. However, if step_area should
        # be created somewhere else by chance, no need to process it,
        # or its desendence a second time.
        area_cache.add(step_area.members)
        # Clarification, "step_neighbors" is the spaces next to "p_m"
        step_neighbors=get_plus(p_m).difference(members)
        # step_neighbors is the outer most cells checked,
        # so save these so we know what we looked at.
        checked.update(step_neighbors)
        # Alright, verify that these members are valid.
        # First, do other island check. Make sure that the neighbors of this
        # are not other islands.
        # All we really need to do, is a river check.
        # This is an impossible_member.
        # Remove it from possible_members
##        print_plots(step_area.members,other_islands,step_area.members.union(other_islands))
##        if 0==other_islands.isdisjoint(step_neighbors)*is_1_river(step_area.members.union(other_islands)):
        if not other_islands.isdisjoint(step_neighbors)or\
           not still_1_river(p_m,members.union(other_islands),checked):
            # One or more neighbors are other islands.
            # The other islands share 1 or more blocks.
            # So this is not a valid move.
            possible_members=step_possible_members
            #Break, this is a fail.
        elif size==len(step_area.members):
            # So the we now have step_members, with our correct number of
            # items. No need to make recursive call.
            # Yield this as an area.
            # Now, if this generator comes back for another round, then we know
            # there was a failer. Something was not right.
            # So, failed_land_points is a list of points of the generator that
            # failed. So, for any new solution coming from this to be correct.
            #
            # So, for any new area, failed_land_points must *NOT* be a subset
            # of the area.
            failed_land_points=yield step_area
            # Check if the failed_land_points contains any points from this
            # generator. If not, well then this generator was always going to fail.
            # so just stop.
##            if failed_land_points and step_area.members.isdisjoint(failed_land_points):
##                print("***Disjoint")
##                return StopIteration
        else:
            # This is valid, make a recursive call.
##            if(yield from _step_area(step_area,step_possible_members.union(step_neighbors),other_islands,area_cache,checked))is StopIteration:return StopIteration
            yield from _step_area(step_area,step_possible_members.union(step_neighbors),other_islands,area_cache,checked)

PRINTS=0
def solve(areas):
    """Take the areas and try to solve the puzzle."""
    if PRINTS:
        global start_time
        start_time=time.time()
##    assert isinstance(areas,list)
    # First, create a list of all peeks, this is a minimum of subjects that
    # other islands must avoid.
##    areas.sort()
    areas.sort(reverse=1)
##    areas.sort(key=lambda x:(x[1][0]**2+x[1][1]**2)**.5)#Fail
##    areas.sort(lambda a,b:sum(b[1])-sum(a[1]))
##    areas.sort(lambda a,b:min(b[1][0]-a[1][0],b[1][1]-a[1][1]))#This worked, but I don't know how???
##    import random;random.shuffle(areas)
    peek_points=fs(area.peek for area in areas)
    if PRINTS:
        print("Starting Configuation:")
        print_plots(fs(),peeks=areas)
    # Make a list of generators for thse areas.
    # Figure out how many plots are needed.
    # We don't need plots for size 1.
    plot_num=len([x for x in areas if x.size!=1])
    plots=[None]*plot_num;area_gens=plots[:];areas_checked=plots[:];i=0
    while True:
        if area_gens[i]is None:
            plot=peek_points.union(*plots[:i]).difference([areas[i].peek])
            areas_checked[i]=set();failed_lands=None
            area_gens[i]=generate_area(areas[i],plot,areas_checked[i])
        try:
            plots[i]=area_gens[i].send(failed_lands).members
        except StopIteration:
            # If failed, clear the plots.
            plots[i]=None
            assert all(plots[:i]) and not any(plots[i:]),"Plots %r are corrupt at i of %d"%(plots,i)
            failed_lands=peek_points.union(*plots[:i]).intersection(areas_checked[i])
            if PRINTS:
                print("Failed to find a solution for plot %d"%i)
                print("Checked Outer Spots")
                print_plots(areas_checked[i],peek_points.union(*plots[:i]),failed_lands,highlight=areas[i].peek)
            if i==0:
                # No solutions.
                print("Fail")
                return peek_points
            # We have failed to come up with a solution.
            # Next, clear the plot and generater, they are dead.
            # Then, step down a level.
            area_gens[i]=plots[i]=None;i-=1
            assert i>=0,"i is not valid %d"%i
            while plots[i].isdisjoint(failed_lands):
                area_gens[i]=None
                plots[i]=None
                i-=1
                assert i>=0,"i is not valid %d"%i
        else:
            assert all(plots[:i+1]) and not any(plots[i+1:]),"Plots %r are corrupt at i of %d"%(plots,i)
            failed_lands=None#Eliminating this may increase performance.
            if PRINTS:
                print("Plots, Depth %d, Time %.6fs"%(i,time.time()-start_time))
                print_plots(*plots,highlight=areas[i+1].peek if i+1!=len(plots)else None,peeks=areas,combined=1)
##                print("Checked Spots")
##                print_plots(areas_checked[i],peek_points.union(*plots[:i]),peek_points.union(*plots[:i]).intersection(areas_checked[i]))
##                print_plots(reduce(lambda a,b:a.union(b),filter(None,plots),fs()),highlight=areas[i+1].peek if i+1!=len(areas) else None,peeks=areas)
            if i==len(plots)-1:
                # Most top frame.
                # Test the solution.
                plot=peek_points.union(*plots)
                if not is_lakes(plot):return plot
                else:
                    # Clear out the areas_checked for the top layer, as if it
                    # fails, it will be because of lakes, not because of
                    # other checks things. So add the plot as a possible.
                    # lake.
                    for c in areas_checked:
                        c.update(plot)
                    if PRINTS:print("Board has lakes, Try again.")
            else:i+=1
##texts='''
##5,5 1,1,1 1,3,1 3,3,3 1,4,2
##7,7 1,1,5 4,3,2 3,5,3 7,5,5 1,6,6
##7,7 2,2,1 9,2,5 1,3,0 1,3,6 2,4,1 2,4,5
##7,7 2,0,0 2,3,1 2,6,1 2,4,3 2,2,4 8,0,6 1,2,6 3,4,6
##12,12 1,0,0 1,0,11 7,1,6 3,1,8 6,2,4 2,3,1 1,3,3 4,3,8 3,4,9 1,5,1 2,5,3 2,6,10 5,7,2 1,7,6 1,8,3 1,8,5 2,8,8 2,8,10 5,9,7 1,10,3 1,10,5
##15,15 1,5,1 3,9,1 5,4,2 1,6,2 2,11,2 2,2,3 3,9,3 2,4,4 1,10,4 5,12,4 3,1,5 1,3,5 3,8,5 1,13,5 5,5,6 1,12,6 1,2,8 2,9,8 1,1,9 2,6,9 6,11,9 3,13,9 5,2,10 2,4,10 4,10,10 1,5,11 2,12,11 2,3,12 2,8,12 5,10,12 1,5,13 1,9,13 1,6,14 1,8,14
##15,15 4,2,0 2,5,0 1,3,1 2,14,2 1,3,3 2,11,3 1,13,3 1,5,4 11,7,4 1,9,4 1,4,5 1,8,5 2,10,5 12,14,5 3,5,6 1,4,7 2,10,7 3,9,8 4,0,9 1,4,9 1,6,9 3,10,9 1,5,10 1,7,10 8,9,10 1,1,11 10,3,11 2,11,11 6,0,12 1,11,13 2,9,14 1,12,14
##15,15 2,2,0 8,10,0 2,3,1 2,14,2 2,3,3 3,5,3 3,9,3 2,11,3 5,13,3 6,0,4 3,7,4 3,3,5 2,11,5 2,6,6 1,8,6 1,4,7 2,10,7 1,6,8 2,8,8 5,3,9 2,11,9 2,7,10 7,14,10 2,1,11 4,3,11 2,5,11 1,9,11 2,11,11 2,0,12 4,6,13 1,11,13 3,4,14 1,12,14
##15,15 2,0,0 2,4,0 3,6,1 2,10,1 1,13,1 2,5,2 2,12,2 3,0,3 2,2,3 4,7,3 2,9,3 1,14,3 1,4,4 1,8,4 2,12,5 4,2,6 3,4,6 1,14,6 7,7,7 1,10,8 2,12,8 3,2,9 2,14,9 2,0,10 2,6,10 1,10,10 2,5,11 4,7,11 2,12,11 1,14,11 3,2,12 3,9,12 1,1,13 2,4,13 3,8,13 2,10,14 5,14,14
##15,15 1,3,0 1,14,0 3,7,1 3,10,1 2,13,1 3,1,2 4,5,2 2,12,3 3,3,4 1,8,4 1,1,5 3,5,5 1,9,5 5,13,5 3,3,6 1,8,6 2,2,7 2,12,7 1,6,8 1,8,8 2,11,8 2,1,9 4,5,9 2,9,9 2,13,9 2,6,10 4,11,10 1,2,11 3,9,12 2,13,12 3,1,13 2,4,13 3,7,13 1,0,14
##15,15 2,8,0 2,4,1 2,7,1 1,10,1 6,4,3 1,1,4 12,5,4 3,11,4 5,13,4 3,10,5 3,0,6 1,6,6 2,8,6 4,13,7 2,3,8 1,6,8 3,8,8 2,14,8 2,4,9 5,1,10 4,3,10 1,9,10 6,13,10 3,8,11 1,10,11 3,4,13 2,7,13 3,10,13 1,6,14 1,14,14
##'''.strip().split('\n')
text=input()
##print text
areas=load_text(text)
##start=time.time()
print_plot(solve(areas))
##stop=time.time()
##print("%f sec"%(stop-start))
	L,S,O,R,F=len,set,None,range,frozenset
	U,N,J,D,I=S.update,F.union,F.isdisjoint,F.difference,F.intersection
	def r(n,a,c):
	U(c,P)
	if L(I(N(Q[n],C[n]),a))<2:return 1
	w=D(P,N(a,[n]));e=S();u=S([next(iter(w))])
	while u:n=I(Q[u.pop()],w);U(u,D(n,e));U(e,n)
	return L(e)==L(w)
	def T(a,o,i,c,k):
	s,p,m=a
	for _ in o:
	t=s,p,N(m,[_]);e=D(o,[_])
	if t[2] in c:o=e;continue
	c.add(t[2]);n=D(Q[_],m);U(k,n)
	if not J(i,n)or not r(_,N(m,i),k):o=e
	elif s==L(t[2]):yield t
	else:yield from T(t,N(e,n),i,c,k)
	s,*p=input().split()
	X,Y=eval(s)
	A=[]
	l=1,-1,0,0
	P=F((x,y)for y in R(Y)for x in R(X))
	exec("Q%sl,l[::-1]%s;C%s(1,1,-1,-1),l[:2]2%s"%(('={(x,y):F((x+i,y+j)for i,j in zip(',')if X>x+i>-1<y+j<Y)for x,y in P}')2))
	for a in p:a,x,y=eval(a);k=x,y;A+=[(a,k,F([k]))]
	A.sort(reverse=1)
	k=F(a[1]for a in A)
	p=[O]*L([a for a in A if a[0]!=1])
	g,h=p[:],p[:]
	i=0
	while 1:
	if g[i]is O:h[i]=S();f=O;g[i]=T(A[i],Q[A[i][1]],D(N(k,*p[:i]),[A[i][1]]),S(),h[i])
	try:p[i]=g[i].send(f)[2]
	except:
	f=I(N(k,*p[:i]),h[i]);g[i]=p[i]=O;i-=1
	while J(p[i],f):g[i]=p[i]=O;i-=1
	else:
	i+=1
	if i==L(p):
	z=N(k,*p)
	if not any(J(z,F(zip([x,x+1]*2,[y,y,y+1,y+1])))for x in R(X-1)for y in R(Y-1)):break
	for c in h:U(c,z)
	b=[X*['.']for i in R(Y)]
	for x,y in z:b[y][x]='#'
	for l in b[::-1]:print(''.join(l))
	#!/usr/bin/python3
	#https://codegolf.stackexchange.com/questions/51006/map-of-islands-and-a-river
	# Take an input of island data and generate a possible map.
	# Edited for python 3 in version 4.
	"""
	Introduction

	For many centuries, there has been a certain river that has never been mapped. The Guild of Cartographers want to produce a map of the river, however, they have never managed to succeed -- for some reason, all the cartographers they have sent to map the river have been eaten by wild animals in the area. A different approach is required.

	Input Description

	The area is a rectangular grid of cells of length m and width n. The cell in the bottom left would be 0,0, and the cell in the top right would be m-1,n-1. m and n are provided in the input as a tuple m,n.

	By using long distance geographical sounding techniques the location of islands around the river have been identified. The size of the islands (i.e. how many cells the island occupies) have also been identified but the shape has not. We supply this information in a tuple s,x,y where s is the size of the island, and x and y are the x and y positions of one particular cell of that island. Each tuple in the input is space separated, so here is an example input:

	7,7 2,0,0 2,3,1 2,6,1 2,4,3 2,2,4 8,0,6 1,2,6 3,4,6
	To illustrate more clearly, here are is the input on a graph:

	y 6\|8 1 3
	5\|
	4\| 2
	3\| 2
	2\|
	1\| 2 2
	0\|2
	=======
	0123456
	x
	Output Description

	Output a map using ASCII characters to represent parts of the area. Each cell will either be # (land) or . (water). The map should follow these rules:

	Definition. An island is a orthogonally contiguous group of land cells that is bounded entirely by river cells and/or the border of the area.
	Definition. A river is an orthogonally contiguous group of water cells that is bounded entirely by land cells and/or the border of the area, and does not contain "lakes" (2x2 areas of water cells).
	Rule. The map shall contain exactly one river.
	Rule. Each numbered cell in the input shall be part of an island containing exactly s cells.
	Rule. Every island in the map shall contain exactly one of the numbered cells in the input.
	Rule. There exists a single unique map for every input.
	Here is the output of the example input:

	#.#.##.
	#....#.
	#.##...
	##..##.
	###....
	...##.#
	##....#
	Here is another input and output.

	Input:

	5,5 3,0,1 1,4,1 2,0,4 2,2,4 2,4,4
	Output:

	#.#.#
	#.#.#
	.....
	###.#
	.....
	"""
	# Island 2 Improvements.
	# Global varibles, max dimensions.
	# Set handling, new management system of generating shapes.

	# Use named tuples for something like a class structure.
	fs=frozenset
	import time
	from collections import namedtuple
	# Board is an area
	Area=namedtuple('Area','size peek members')
	#_Area=Area
	##class Area(_Area):
	## 'Area(size, peek, members)'
	## def __new__(_cls,size,peek,members):
	## 'Create new instance of Area(size, peek, members)'
	## # Just enforcing the typing.
	## assert isinstance(size,int)
	## assert len(peek)==2
	## assert isinstance(peek[0],int)and isinstance(peek[1],int)
	## assert isinstance(members,fs)
	## assert peek in members
	## assert all(len(member)==2for member in members)
	## assert size>=len(members)
	## return super(Area,_cls).__new__(_cls,size,peek,members)
	def load_text(text):
	global X,Y,ALL_POINTS,get_plus,get_cross
	size,*plots=text.split()
	X,Y=eval(size)
	l=[]
	for a in plots:a,x,y=eval(a);l.append(Area(a,(x,y),fs([(x,y)])))
	# Generate all points now to fit the size of the board.
	ALL_POINTS=fs((x,y)for y in range(Y) for x in range(X))
	get_plus={(x,y):fs((i,j)for(i,j)in((x,y+1),(x,y-1),(x+1,y),(x-1,y))if X>i>-1<j<Y)for x in range(X)for y in range(Y)}.get
	get_cross={(x,y):fs((i,j)for(i,j)in((x+1,y+1),(x+1,y-1),(x-1,y-1),(x-1,y+1))if X>i>-1<j<Y)for x in range(X)for y in range(Y)}.get

	## l=1,-1,0,0
	## get_plus={(x,y):fs((x+i,y+j)for i,j in zip(l,l[::-1])if X>x+i>-1<y+j<Y)for x in range(X)for y in range(Y)}.get
	## get_cross={(x,y):fs((x+i,y+j)for i,j in zip((1,1,-1,-1),l[:2]*2)if X>x+i>-1<y+j<Y)for x in range(X)for y in range(Y)}.get
	## l=0,0,1,-1
	## d=lambda i,j:X>x+i>-1<y+j<Y
	## get_plus={(x,y):F(filter(d,zip(l,l[::-1])))for x in range(X)for y in range(Y)}.get
	## get_cross={(x,y):F(filter(d,zip([1,1,-1,-1],l[2:]*2)))for x in range(X)for y in range(Y)}.get
	## get_plus={(x,y):F((x+i,y+j)for i,j in((0,1),(0,-1),(1,0),(-1,0))if X>x+i>-1<y+j<Y)for x in R(X)for y in R(Y)}.get
	## get_plus={(x,y):F((x+i,y+j)for i,j in zip(if X>x+i>-1<y+j<Y)for x in R(X)for y in R(Y)}.get
	## get_plus={(x,y):F((i,j)for(i,j)in((x,y+1),(x,y-1),(x+1,y),(x-1,y))if X>i>-1<j<Y)for x in R(X)for y in R(Y)}.get
	## get_cross={(x,y):F((x+i,y+j)for i,j in((1,1),(1,-1),(-1,-1),(-1,1))if X>x+i>-1<y+j<Y)for x in R(X)for y in R(Y)}.get
	## get_cross={(x,y):F((i,j)for(i,j)in((x+1,y+1),(x+1,y-1),(x-1,y-1),(x-1,y+1))if X>i>-1<j<Y)for x in R(X)for y in R(Y)}.get
	return l
	def print_plots(args,*keywords): # Nice, fashionable for debugging.
	"""print_plots(points,FG='#',BG='.'):
	Turn the points into a grid. (0,0) is bottom left.
	"""
	line_length=15
	FG=keywords.pop('FG','#')
	BG=keywords.pop('BG','.')
	# highlight is a value that is noted on all boards.
	peeks=keywords.pop('peeks',())
	combined=keywords.pop('combined',0)
	highlight=keywords.pop('highlight',None)
	if keywords:
	raise TypeError("print_plots() got an unexpected keyword argument %r"%
	keywords.popitem()[0])
	if combined and len(args)>1:
	args+=(fs().union(*filter(None,args)),)
	elif not args and (highlight or peeks):
	args=[fs()] # Do one plot.
	for k in range(0,len(args),line_length):
	text=[]
	for plot in args[k:k+line_length]:
	if plot is None:plot=()
	board=[[BG]*X for i in range(Y)]
	for peek in peeks:
	a,(x,y)=peek.size,peek.peek
	board[y][x]=str(a)
	for x,y in plot:board[y][x]=FG
	if highlight:
	x,y=highlight
	board[y][x]='!'
	for i,line in enumerate(reversed(board)):
	if i==len(text):
	text.append(''.join(line))
	else:
	text[i]+=' '+''.join(line)
	print('\n'.join(text)+'\n')
	def print_plot(plot):
	# Little for golf.
	"""Turn points into a grid and print them."""
	if PRINTS:print("Solution:")
	board=[['.']*X for i in range(Y)]
	for x,y in plot:board[y][x]='#'
	for line in board[::-1]:print(''.join(line))
	##get_cross=lambda(x,y):fs((i,j)for i,j in((x+1,y+1),(x+1,y-1),(x-1,y-1),(x-1,y+1))if X>i>-1<j<Y)
	##get_plus={(x,y):fs((i,j)for i,j in((x,y+1),(x,y-1),(x+1,y),(x-1,y))if X>i>-1<j<Y)for x in range(X)for y in range(Y)}.get
	##get_plus=lambda(x,y):fs((i,j)for i,j in((x,y+1),(x,y-1),(x+1,y),(x-1,y))if X>i>-1<j<Y)
	##get_plus=lambda(x,y):fs((i,j)for i,j in zip((x,x,x+1,x-1),(y+1,y-1,y,y))if X>i>-1<j<Y)
	##get_plus=lambda(x,y):fs(filter(lambda(i,j):X>x+i>-1<y+j<Y,zip((0,0,1,-1),(1,-1,0,0))))
	##get_plus=lambda(x,y),l=(0,0,1,-1):fs(filter(lambda(i,j):X>x+i>-1<y+j<Y,zip(l,l[::-1])))
	##get_plus=lambda(x,y):fs(filter(lambda(i,j):X>x+i>-1<y+j<Y,((0,1),(0,-1),(1,0),(-1,0))))
	##get_plus=lambda(x,y):fs((x+i,y+j)for i,j in((0,1),(0,-1),(1,0),(-1,0))if X>x+i>-1<y+j<Y)
	##get_plus=lambda(x,y),l=(0,0,1,-1):fs((x+i,y+j)for i,j in zip(l,l[::-1])if X>x+i>-1<y+j<Y)
	##get_plus=lambda p:fs((p[0]+i,p[1]+j)for i,j in((0,1),(0,-1),(1,0),(-1,0))if X>p[0]+i>-1<p[1]+j<Y)
	##def get_plus((x,y)):return fs(filter(lambda p:X>p[0]>-1<p[1]<Y,((x,y+1),(x,y-1),(x+1,y),(x-1,y))))
	def still_1_river(new_island,all_islands,checked):
	"""Check to see if a river is still all connected."""
	checked.update(ALL_POINTS)
	# Checks only a small region.
	# ...
	# .#. <-- This situation means the river is good.
	# ...
	# And if there is only one other island in this box, then we know the river
	# is still find.
	# #.. .#. ..# ... ... ... ... ...
	# .#. .#. .#. .## .#. .#. .#. ##. <-- Also river is still good.
	# ... ... ... ... ..# .#. #.. ...
	# Any more then two, there is no longer a guarantee the river is good.
	# HOWEVER, it tends to be a very good guess that the river is still good.
	# So, lets guess that any group of three, is also clean.
	if len(get_plus(new_island).union(get_cross(new_island)).intersection(all_islands))<2:
	# This is a good river.
	return True
	# If the tricks fail, do a full is_1_river check.
	return is_1_river(all_islands.union([new_island]),checked)
	def is_1_river(all_points,checked):
	"""Check if all of the water connects to create 1 river."""
	## assert isinstance(all_points,fs)
	# So all_points is a set of all islands on the map.
	# My question is, do all of the surronding water connect?
	# First off, make a list of all of the water on the map.
	all_water_points=ALL_POINTS.difference(all_points)
	# Now test if all of these water points are connected.
	for start_water in all_water_points:
	break # Trick to just grab some water element.
	connected_water=set()
	unexplored_water=set([start_water])# Water that may lead to other water.
	while unexplored_water:
	# This will cycle until all water is explored.
	water=unexplored_water.pop()
	neighbor_water=get_plus(water).intersection(all_water_points)
	unexplored_water.update(neighbor_water.difference(connected_water))
	connected_water.update(neighbor_water)
	# Now that we have used all unexplored_water, check if connected_water is everything.
	## assert (len(connected_water)==len(all_water_points))==(connected_water==all_water_points)
	## if len(connected_water)==len(all_water_points):
	## return True
	## else:
	## return checked.update(ALL_POINTS)
	return len(connected_water)==len(all_water_points)or checked.update(ALL_POINTS)
	## return len(connected_water)==len(all_water_points)
	def is_lakes(plot):
	# Really, just perform a test here that there are no lakes.
	# Every 2x2 areas has at least 1 land and is not all water.
	for y in range(Y-1):
	for x in range(X-1):
	lake=fs([(x,y),(x+1,y),(x,y+1),(x+1,y+1)])
	if plot.isdisjoint(lake):
	# There is no islands in this 2x2
	return lake
	##def is_lakes(plot):
	## return any(map(plot.isdisjoint,(fs([(x,y),(x+1,y),(x,y+1),(x+1,y+1)])for x in range(X-1)for y in range(Y-1))))
	def generate_area(area,other_islands,checked):
	# Generate areas.
	## assert isinstance(area,Area)
	## assert len(area.members)==1
	## assert isinstance(other_islands,fs)
	## assert all(isinstance(x,int)and isinstance(y,int)for x,y in other_islands)
	# There already isn't one river just with other islands.
	# This isn't just bad, that isn't valid.
	## assert is_1_river(other_islands)
	# If the size is 1, we are done right here.
	# There is 1 way to arrange 1 thing.
	if area.size==1:
	yield area # We are done, thank you. Few... that was hard.
	return
	#else:
	# Make the first set of members
	possible_members=get_plus(area.peek)
	# The other islands share 1 or more blocks.
	# This is not a valid start location!
	## assert other_islands.isdisjoint(possible_members)
	# Save areas that are generated so we don't return the same area repeatedly.
	area_cache=set()#This will be passed to the _step_area
	yield from _step_area(area,possible_members,other_islands,area_cache,checked)
	## if 0:
	## print(len(area_cache))
	#This returns a set, everything previous is Areas.
	def _step_area(area,possible_members,other_islands,area_cache,checked):
	# Take area, yield all possible member configurations, that are legal.
	# other_islands is the other members that this area can't touch.
	size,peek,members=area
	## assert isinstance(area,Area)
	## assert isinstance(possible_members,fs)
	## assert isinstance(other_islands,fs)# This are points in other islands.
	## assert all(isinstance(x,int)and isinstance(y,int)for x,y in other_islands)
	## assert all(isinstance(x,int)and isinstance(y,int)for x,y in possible_members)
	## assert isinstance(area_cache,set)
	## # Make sure there is no overlap in these 3 sets.
	## assert len(area.members)+len(possible_members)+len(other_islands)==\
	## len(area.members.union(possible_members,other_islands))
	failed_land_points=fs()
	for p_m in possible_members:
	# This is the next cell.
	step_area=Area(size,peek,members.union([p_m]))
	step_possible_members=possible_members.difference([p_m])
	# First, check if this is in area_cache, if so ignore, it has already
	# been returned as a result.
	if step_area.members in area_cache:
	# Don't need to do anything else with this.
	possible_members=step_possible_members
	continue
	# Cache this current area.
	# Note: This step_area has less elements than its size, therefore,
	# step_area will never be yielded. However, if step_area should
	# be created somewhere else by chance, no need to process it,
	# or its desendence a second time.
	area_cache.add(step_area.members)
	# Clarification, "step_neighbors" is the spaces next to "p_m"
	step_neighbors=get_plus(p_m).difference(members)
	# step_neighbors is the outer most cells checked,
	# so save these so we know what we looked at.
	checked.update(step_neighbors)
	# Alright, verify that these members are valid.
	# First, do other island check. Make sure that the neighbors of this
	# are not other islands.
	# All we really need to do, is a river check.
	# This is an impossible_member.
	# Remove it from possible_members
	## print_plots(step_area.members,other_islands,step_area.members.union(other_islands))
	## if 0==other_islands.isdisjoint(step_neighbors)*is_1_river(step_area.members.union(other_islands)):
	if not other_islands.isdisjoint(step_neighbors)or\
	not still_1_river(p_m,members.union(other_islands),checked):
	# One or more neighbors are other islands.
	# The other islands share 1 or more blocks.
	# So this is not a valid move.
	possible_members=step_possible_members
	#Break, this is a fail.
	elif size==len(step_area.members):
	# So the we now have step_members, with our correct number of
	# items. No need to make recursive call.
	# Yield this as an area.
	# Now, if this generator comes back for another round, then we know
	# there was a failer. Something was not right.
	# So, failed_land_points is a list of points of the generator that
	# failed. So, for any new solution coming from this to be correct.
	#
	# So, for any new area, failed_land_points must NOT be a subset
	# of the area.
	failed_land_points=yield step_area
	# Check if the failed_land_points contains any points from this
	# generator. If not, well then this generator was always going to fail.
	# so just stop.
	## if failed_land_points and step_area.members.isdisjoint(failed_land_points):
	## print("***Disjoint")
	## return StopIteration
	else:
	# This is valid, make a recursive call.
	## if(yield from _step_area(step_area,step_possible_members.union(step_neighbors),other_islands,area_cache,checked))is StopIteration:return StopIteration
	yield from _step_area(step_area,step_possible_members.union(step_neighbors),other_islands,area_cache,checked)

	PRINTS=0
	def solve(areas):
	"""Take the areas and try to solve the puzzle."""
	if PRINTS:
	global start_time
	start_time=time.time()
	## assert isinstance(areas,list)
	# First, create a list of all peeks, this is a minimum of subjects that
	# other islands must avoid.
	## areas.sort()
	areas.sort(reverse=1)
	## areas.sort(key=lambda x:(x[1][0]2+x[1][1]2)**.5)#Fail
	## areas.sort(lambda a,b:sum(b[1])-sum(a[1]))
	## areas.sort(lambda a,b:min(b[1][0]-a[1][0],b[1][1]-a[1][1]))#This worked, but I don't know how???
	## import random;random.shuffle(areas)
	peek_points=fs(area.peek for area in areas)
	if PRINTS:
	print("Starting Configuation:")
	print_plots(fs(),peeks=areas)
	# Make a list of generators for thse areas.
	# Figure out how many plots are needed.
	# We don't need plots for size 1.
	plot_num=len([x for x in areas if x.size!=1])
	plots=[None]*plot_num;area_gens=plots[:];areas_checked=plots[:];i=0
	while True:
	if area_gens[i]is None:
	plot=peek_points.union(*plots[:i]).difference([areas[i].peek])
	areas_checked[i]=set();failed_lands=None
	area_gens[i]=generate_area(areas[i],plot,areas_checked[i])
	try:
	plots[i]=area_gens[i].send(failed_lands).members
	except StopIteration:
	# If failed, clear the plots.
	plots[i]=None
	assert all(plots[:i]) and not any(plots[i:]),"Plots %r are corrupt at i of %d"%(plots,i)
	failed_lands=peek_points.union(*plots[:i]).intersection(areas_checked[i])
	if PRINTS:
	print("Failed to find a solution for plot %d"%i)
	print("Checked Outer Spots")
	print_plots(areas_checked[i],peek_points.union(*plots[:i]),failed_lands,highlight=areas[i].peek)
	if i==0:
	# No solutions.
	print("Fail")
	return peek_points
	# We have failed to come up with a solution.
	# Next, clear the plot and generater, they are dead.
	# Then, step down a level.
	area_gens[i]=plots[i]=None;i-=1
	assert i>=0,"i is not valid %d"%i
	while plots[i].isdisjoint(failed_lands):
	area_gens[i]=None
	plots[i]=None
	i-=1
	assert i>=0,"i is not valid %d"%i
	else:
	assert all(plots[:i+1]) and not any(plots[i+1:]),"Plots %r are corrupt at i of %d"%(plots,i)
	failed_lands=None#Eliminating this may increase performance.
	if PRINTS:
	print("Plots, Depth %d, Time %.6fs"%(i,time.time()-start_time))
	print_plots(*plots,highlight=areas[i+1].peek if i+1!=len(plots)else None,peeks=areas,combined=1)
	## print("Checked Spots")
	## print_plots(areas_checked[i],peek_points.union(plots[:i]),peek_points.union(plots[:i]).intersection(areas_checked[i]))
	## print_plots(reduce(lambda a,b:a.union(b),filter(None,plots),fs()),highlight=areas[i+1].peek if i+1!=len(areas) else None,peeks=areas)
	if i==len(plots)-1:
	# Most top frame.
	# Test the solution.
	plot=peek_points.union(*plots)
	if not is_lakes(plot):return plot
	else:
	# Clear out the areas_checked for the top layer, as if it
	# fails, it will be because of lakes, not because of
	# other checks things. So add the plot as a possible.
	# lake.
	for c in areas_checked:
	c.update(plot)
	if PRINTS:print("Board has lakes, Try again.")
	else:i+=1
	##texts='''
	##5,5 1,1,1 1,3,1 3,3,3 1,4,2
	##7,7 1,1,5 4,3,2 3,5,3 7,5,5 1,6,6
	##7,7 2,2,1 9,2,5 1,3,0 1,3,6 2,4,1 2,4,5
	##7,7 2,0,0 2,3,1 2,6,1 2,4,3 2,2,4 8,0,6 1,2,6 3,4,6
	##12,12 1,0,0 1,0,11 7,1,6 3,1,8 6,2,4 2,3,1 1,3,3 4,3,8 3,4,9 1,5,1 2,5,3 2,6,10 5,7,2 1,7,6 1,8,3 1,8,5 2,8,8 2,8,10 5,9,7 1,10,3 1,10,5
	##15,15 1,5,1 3,9,1 5,4,2 1,6,2 2,11,2 2,2,3 3,9,3 2,4,4 1,10,4 5,12,4 3,1,5 1,3,5 3,8,5 1,13,5 5,5,6 1,12,6 1,2,8 2,9,8 1,1,9 2,6,9 6,11,9 3,13,9 5,2,10 2,4,10 4,10,10 1,5,11 2,12,11 2,3,12 2,8,12 5,10,12 1,5,13 1,9,13 1,6,14 1,8,14
	##15,15 4,2,0 2,5,0 1,3,1 2,14,2 1,3,3 2,11,3 1,13,3 1,5,4 11,7,4 1,9,4 1,4,5 1,8,5 2,10,5 12,14,5 3,5,6 1,4,7 2,10,7 3,9,8 4,0,9 1,4,9 1,6,9 3,10,9 1,5,10 1,7,10 8,9,10 1,1,11 10,3,11 2,11,11 6,0,12 1,11,13 2,9,14 1,12,14
	##15,15 2,2,0 8,10,0 2,3,1 2,14,2 2,3,3 3,5,3 3,9,3 2,11,3 5,13,3 6,0,4 3,7,4 3,3,5 2,11,5 2,6,6 1,8,6 1,4,7 2,10,7 1,6,8 2,8,8 5,3,9 2,11,9 2,7,10 7,14,10 2,1,11 4,3,11 2,5,11 1,9,11 2,11,11 2,0,12 4,6,13 1,11,13 3,4,14 1,12,14
	##15,15 2,0,0 2,4,0 3,6,1 2,10,1 1,13,1 2,5,2 2,12,2 3,0,3 2,2,3 4,7,3 2,9,3 1,14,3 1,4,4 1,8,4 2,12,5 4,2,6 3,4,6 1,14,6 7,7,7 1,10,8 2,12,8 3,2,9 2,14,9 2,0,10 2,6,10 1,10,10 2,5,11 4,7,11 2,12,11 1,14,11 3,2,12 3,9,12 1,1,13 2,4,13 3,8,13 2,10,14 5,14,14
	##15,15 1,3,0 1,14,0 3,7,1 3,10,1 2,13,1 3,1,2 4,5,2 2,12,3 3,3,4 1,8,4 1,1,5 3,5,5 1,9,5 5,13,5 3,3,6 1,8,6 2,2,7 2,12,7 1,6,8 1,8,8 2,11,8 2,1,9 4,5,9 2,9,9 2,13,9 2,6,10 4,11,10 1,2,11 3,9,12 2,13,12 3,1,13 2,4,13 3,7,13 1,0,14
	##15,15 2,8,0 2,4,1 2,7,1 1,10,1 6,4,3 1,1,4 12,5,4 3,11,4 5,13,4 3,10,5 3,0,6 1,6,6 2,8,6 4,13,7 2,3,8 1,6,8 3,8,8 2,14,8 2,4,9 5,1,10 4,3,10 1,9,10 6,13,10 3,8,11 1,10,11 3,4,13 2,7,13 3,10,13 1,6,14 1,14,14
	##'''.strip().split('\n')
	text=input()
	##print text
	areas=load_text(text)
	##start=time.time()
	print_plot(solve(areas))
	##stop=time.time()
	##print("%f sec"%(stop-start))