from itertools import*;e=enumerate;f=lambda l:[[[' ']*(max(j for k,(j,c)in o[1:])-i)+l[k][:i]+[c.upper()]+l[k][i+1:]for k,(i,c)in o[1:]]for p in product(*[list(e(w))for w in l])for o in permutations(list(e(p)))if[c for k,(i,c)in o[1:]]==l[o[0][0]]][0]
tests=[
	[['t','o','g','e','t','h','e','r'],['t','e','a','m'],['e','v','e','r','y','o','n','e'],['a','c','h','i','e','v','e','s'],['m','o','r','e']],
	[['a','a','a'],['a','a','a'],['a','a','a'],['a','a','a']],
	[['a','a','a'],['a','a','a'],['a','a','b'],['b','a','a']],
	[['l','i','v','e'],['e','v','e','r','y'],['l','o','v','e'],['v','e','r','y'],['o','h','i','o']],
	[['c','o','w'],['o','f'],['f','o','x']],
	[['l','a','t','e'],['b','a','l','l','r','o','o','m'],['a','n','v','i','l'],['t','o'],['h','e','a','d']]
	]
for test in tests:
	print '\n'.join(''.join(r) for r in f(test))
	print

ZnJvbSBpdGVydG9vbHMgaW1wb3J0KjtlPWVudW1lcmF0ZTtmPWxhbWJkYSBsOltbWycgJ10qKG1heChqIGZvciBrLChqLGMpaW4gb1sxOl0pLWkpK2xba11bOmldK1tjLnVwcGVyKCldK2xba11baSsxOl1mb3IgaywoaSxjKWluIG9bMTpdXWZvciBwIGluIHByb2R1Y3QoKltsaXN0KGUodykpZm9yIHcgaW4gbF0pZm9yIG8gaW4gcGVybXV0YXRpb25zKGxpc3QoZShwKSkpaWZbYyBmb3IgaywoaSxjKWluIG9bMTpdXT09bFtvWzBdWzBdXV1bMF0KdGVzdHM9WwoJW1sndCcsJ28nLCdnJywnZScsJ3QnLCdoJywnZScsJ3InXSxbJ3QnLCdlJywnYScsJ20nXSxbJ2UnLCd2JywnZScsJ3InLCd5JywnbycsJ24nLCdlJ10sWydhJywnYycsJ2gnLCdpJywnZScsJ3YnLCdlJywncyddLFsnbScsJ28nLCdyJywnZSddXSwKCVtbJ2EnLCdhJywnYSddLFsnYScsJ2EnLCdhJ10sWydhJywnYScsJ2EnXSxbJ2EnLCdhJywnYSddXSwKCVtbJ2EnLCdhJywnYSddLFsnYScsJ2EnLCdhJ10sWydhJywnYScsJ2InXSxbJ2InLCdhJywnYSddXSwKCVtbJ2wnLCdpJywndicsJ2UnXSxbJ2UnLCd2JywnZScsJ3InLCd5J10sWydsJywnbycsJ3YnLCdlJ10sWyd2JywnZScsJ3InLCd5J10sWydvJywnaCcsJ2knLCdvJ11dLAoJW1snYycsJ28nLCd3J10sWydvJywnZiddLFsnZicsJ28nLCd4J11dLAoJW1snbCcsJ2EnLCd0JywnZSddLFsnYicsJ2EnLCdsJywnbCcsJ3InLCdvJywnbycsJ20nXSxbJ2EnLCduJywndicsJ2knLCdsJ10sWyd0JywnbyddLFsnaCcsJ2UnLCdhJywnZCddXQoJXQpmb3IgdGVzdCBpbiB0ZXN0czoKCXByaW50ICdcbicuam9pbignJy5qb2luKHIpIGZvciByIGluIGYodGVzdCkpCglwcmludA==