import math
 
 
class HorseTicket:
 
	def prefixSum(self, races, curpre):
		ret = 0
		race = []
		invalid = False
		for i in curpre:
			for j in curpre:
				if i != j:
					for k in races:
						if i in k and j in k:
							invalid = True
		if invalid:
			return 0
		for u in races:
			valid = True
			for i in u:
				if i in curpre:
					valid = False
			if valid:
				race.append(u)
		races = race
		nn = len(races)
		c = [0 for i in range(nn + 1)]
		c[0] = 1
		for i in range(nn):
			for j in range(nn, 0, -1):
				c[j] += c[j - 1] * len(race[i])
		for i in range(nn + 1):
			ret += math.factorial(i) * c[i]
		return ret
 
	def getTicket(self, races, index):
		total = self.prefixSum(races, '')
		if index >= total:
			return '!'
 
		chars = []
		for u in races:
			chars.extend([i for i in u])
		chars = sorted(list(set(chars)))
 
		ans = ''
		while index > 0:
			index -= 1
			for i in chars:
				if i in ans:
					continue
				prefix = ans + i
				tot = self.prefixSum(races, prefix)
				if tot > index:
					ans = prefix
					break
				else:
					index -= tot
		return ans