#! /usr/bin/python
# WordCracker1.31 (MiniEntry) by Mike Sweeney (mjs) 11-feb-05
# 96 lines - 13 comment/space/dbug = 83 working lines

BC = '_'

import sys, time, operator
from string import *
from random import randrange
def sum(s): return reduce( operator.__add__, s, 0 )

if sys.argv[1] == '-w': words = [ upper(w) for w in sys.argv[2:] ]
else: words = [strip(a) for a in file( sys.argv[1] ).readlines() if strip(a)]

tlimit = time.clock() + 56.0

cm = {}
for w in words:
	for i in range(len(w)):
		cm.setdefault(w[i],[]).append((len(w),w,i))
		for j in range(2,8):
			if j<=i:
				pat = w[i-j]+(BC*(j-1))+w[i]
				cm.setdefault(pat,[]).append((len(w),w,i-j))

wpop = dict([(w,sum([len(cm[ch]) for ch in w])) for w in words])
for k in cm: cm[k] = [(wpop[w],wl,w,i) for wl,w,i in cm[k]]
[ (a.sort(),a.reverse()) for a in cm.values() ]
popchs = [ (len(wset),ch) for ch,wset in cm.items() ]
popchs.sort()

rc, rw, rh = range(1,16), range(32), range(16)

def findw( q, px, py, pdx, pdy, slots ):
	pat = q((px,py))
	dx,dy = -pdx,-pdy
	for spre in rc:
		x,y = px+dx*spre,py+dy*spre
		if q((x,y))!=BC or 'A'<=q((x+dx,y+dy))<='Z': break
		if 'A'<=q((x+dy,y+dx))<='Z' or 'A'<=q((x-dy,y-dx))<='Z': break
	dx,dy = pdx,pdy
	for spost in rc:
		x,y = px+dx*spost,py+dy*spost
		if q((x,y))!=BC: break
		if 'A'<=q((x+dy,y+dx))<='Z' or 'A'<=q((x-dy,y-dx))<='Z': break
		if 'A'<=q((x+dx,y+dy))<='Z': 
			slots.append( [px,py,pdx, spre-1, pat, spost-1] )
			if 'A'<=q((x+dx*2,y+dy*2))<='Z' : pat=''
			else: pat = q((px,py))+(BC*spost)+q((x+dx,y+dy))
			break
	if len(pat)>1:
		for spost in rc:
			x,y = px+dx*(spost+len(pat)-1), py+dy*(spost+len(pat)-1)
			if q((x,y))!=BC or 'A'<=q((x+dx,y+dy))<='Z': break
			if 'A'<=q((x+dy,y+dx))<='Z' or 'A'<=q((x-dy,y-dx))<='Z': break
	if pat: slots = [[px,py,pdx, spre-1, pat, spost-1]] + slots
	return slots

def run(sc=0):
	pz = dict( [((x,y),BC) for x in rw for y in rh] )
	pz[(15,8)] = popchs[-1][1]
	piv = { (15,8,1) : 1 }
	while piv:
		targ = None
		pl = piv.keys()
		z = randrange( max( len(pl)-16, 1 ) )
		slots = [findw(pz.get,x,y,dx,1-dx,[]) for x,y,dx in pl[z:z+16]]
		ps = [ s[0] for s in slots if len(s)==2 ]
		ps += [ s[-1] for s in slots if len(s)>=1 ]
		if not ps: break
		for x,y,dx,spre,pat,spost in ps :
			dy = 1-dx
			if len(pat)>1 or spre+spost > 0 :
				for wpop,wlen,word,wpre in cm.get(pat,[]):
					if wpre <= spre and wlen-wpre-len(pat) <= spost: 
						targ = word
						break
			if targ: break
			if len(pat)==1 and piv.get((x,y,dx)) : del piv[(x,y,dx)]
		if targ:
			for i in range(len(targ)):
				cx,cy = x+dx*(i-wpre),y+dy*(i-wpre)
				if pz[(cx,cy)] != targ[i] :
					pz[(cx,cy)] = targ[i]
					piv[(cx,cy,dy)] = 1
				else:
					if piv.get((cx,cy,dx)) : del piv[(cx,cy,dx)]
			sc += len(targ)
	return pz, sc

top = -1
while 1:
	pz, sc = run()
	if sc > top: ans, top = pz, sc
	if time.clock() > tlimit: break
print join( [join([ans[(x,y)] for x in rw],'') for y in rh], '\n' )