from math import sqrt, ceil, log2
from sys import exit
data = []
def fill(num, count, bit):
	if (bit == 9 or bit == 8) and count > 3:
		return
	if count == 5:
		mask = (1<<6)-1
		if (((num & (num>>5)) | (num & (num>>10)) | ((num>>5) & (num>>10))) & mask) != 0:
			return
		data.append(num)
		return
	if bit == -1:
		return
	fill(num, count, bit-1)
	fill(num | (1<<bit), count+1, bit-1)
 
fill(0, 0, 14)
 
 
 
def hash_func(data, pow2=True):
	class DoesNotFit(Exception):
		pass
 
    #controlla che elementi nella stessa posizione non siano settati
	def check(l, r):
		for a, b in zip(l, r):
			if (a&b)==1:
				return False
		return True
 
    #calcolo dimensione minima
	size = max(ceil(sqrt(max(data))), len(data))
	if pow2:
		size = 1<<ceil(log2(size))
 
    #procedo per tentativi
	while True:
		try:
 
			square = [[0]*size for i in range(size)]
			rowcounts = [0] * size
 
            #tabella da comprimere
			for c in data:
				square[c//size][c%size] = 1
				rowcounts[c//size]+=1
 
			most_frequent_row_order = reversed(sorted(zip(rowcounts, range(size))))
 
            #shift relativo ad ogni riga
			shifts = [0]*size
 
            #tabella compressa in una riga
			C = [0]*size
 
            #cerco di ruotare ogni riga in modo che non ci siano duplicati sulle colonne
			for _, r in most_frequent_row_order:
				tmp = square[r]
                #ruoto finché non trovo una rotazione che vada bene o abbia fatto un giro completo
				while not check(C, tmp) and shifts[r] < size:
					shifts[r] += 1
					tmp = tmp[-1:]+tmp[:-1]
                #Se ho compiuto un giro completo non posso sistemare le righe
				if shifts[r] == size:
					raise DoesNotFit
                #marko le posizioni occupate dalla riga corrente ruotata
				C = list(map(sum, zip(C, tmp)))
			return size, shifts
		except DoesNotFit:
			pass
 
        #ritento con una dimensione più grande
		if pow2:
			size = size << 1
		else:
			size += 1
 
def output_c_hash_func(data, prefix="", pow2=True):
    size, shifts = hash_func(data, pow2)
    tsize = prefix+"SIZE"
    def tshifts(n):
        return prefix+"SHIFTS["+str(n)+"]"
    def ttable(n):
        return prefix+"TABLE["+str(n)+"]"
    print("#define", tsize, size)
    print("int", tshifts(size), "= {", end="")
    it = iter(shifts)
    print(next(it), end="")
    for c in it:
        print(",", c, end="")
    print("};")
    print("int", ttable(size), ";")
    print("#define", prefix+"lookup(i)", ttable("((i)+"+tshifts("(i)/"+tsize)+")%"+tsize))
 
output_c_hash_func(data, "HT_", False)

ZnJvbSBtYXRoIGltcG9ydCBzcXJ0LCBjZWlsLCBsb2cyCmZyb20gc3lzIGltcG9ydCBleGl0CmRhdGEgPSBbXQpkZWYgZmlsbChudW0sIGNvdW50LCBiaXQpOgoJaWYgKGJpdCA9PSA5IG9yIGJpdCA9PSA4KSBhbmQgY291bnQgPiAzOgoJCXJldHVybgoJaWYgY291bnQgPT0gNToKCQltYXNrID0gKDE8PDYpLTEKCQlpZiAoKChudW0gJiAobnVtPj41KSkgfCAobnVtICYgKG51bT4+MTApKSB8ICgobnVtPj41KSAmIChudW0+PjEwKSkpICYgbWFzaykgIT0gMDoKCQkJcmV0dXJuCgkJZGF0YS5hcHBlbmQobnVtKQoJCXJldHVybgoJaWYgYml0ID09IC0xOgoJCXJldHVybgoJZmlsbChudW0sIGNvdW50LCBiaXQtMSkKCWZpbGwobnVtIHwgKDE8PGJpdCksIGNvdW50KzEsIGJpdC0xKQoKZmlsbCgwLCAwLCAxNCkKCgoKZGVmIGhhc2hfZnVuYyhkYXRhLCBwb3cyPVRydWUpOgoJY2xhc3MgRG9lc05vdEZpdChFeGNlcHRpb24pOgoJCXBhc3MKICAgIAogICAgI2NvbnRyb2xsYSBjaGUgZWxlbWVudGkgbmVsbGEgc3Rlc3NhIHBvc2l6aW9uZSBub24gc2lhbm8gc2V0dGF0aQoJZGVmIGNoZWNrKGwsIHIpOgoJCWZvciBhLCBiIGluIHppcChsLCByKToKCQkJaWYgKGEmYik9PTE6CgkJCQlyZXR1cm4gRmFsc2UKCQlyZXR1cm4gVHJ1ZQogICAgCiAgICAjY2FsY29sbyBkaW1lbnNpb25lIG1pbmltYQoJc2l6ZSA9IG1heChjZWlsKHNxcnQobWF4KGRhdGEpKSksIGxlbihkYXRhKSkKCWlmIHBvdzI6CgkJc2l6ZSA9IDE8PGNlaWwobG9nMihzaXplKSkKICAgIAogICAgI3Byb2NlZG8gcGVyIHRlbnRhdGl2aQoJd2hpbGUgVHJ1ZToKCQl0cnk6CgoJCQlzcXVhcmUgPSBbWzBdKnNpemUgZm9yIGkgaW4gcmFuZ2Uoc2l6ZSldCgkJCXJvd2NvdW50cyA9IFswXSAqIHNpemUKCQkJCiAgICAgICAgICAgICN0YWJlbGxhIGRhIGNvbXByaW1lcmUKCQkJZm9yIGMgaW4gZGF0YToKCQkJCXNxdWFyZVtjLy9zaXplXVtjJXNpemVdID0gMQoJCQkJcm93Y291bnRzW2MvL3NpemVdKz0xCgkJCQoJCQltb3N0X2ZyZXF1ZW50X3Jvd19vcmRlciA9IHJldmVyc2VkKHNvcnRlZCh6aXAocm93Y291bnRzLCByYW5nZShzaXplKSkpKQoJCQkKICAgICAgICAgICAgI3NoaWZ0IHJlbGF0aXZvIGFkIG9nbmkgcmlnYQoJCQlzaGlmdHMgPSBbMF0qc2l6ZQoKICAgICAgICAgICAgI3RhYmVsbGEgY29tcHJlc3NhIGluIHVuYSByaWdhCgkJCUMgPSBbMF0qc2l6ZQoJCQkKICAgICAgICAgICAgI2NlcmNvIGRpIHJ1b3RhcmUgb2duaSByaWdhIGluIG1vZG8gY2hlIG5vbiBjaSBzaWFubyBkdXBsaWNhdGkgc3VsbGUgY29sb25uZQoJCQlmb3IgXywgciBpbiBtb3N0X2ZyZXF1ZW50X3Jvd19vcmRlcjoKCQkJCXRtcCA9IHNxdWFyZVtyXQogICAgICAgICAgICAgICAgI3J1b3RvIGZpbmNow6kgbm9uIHRyb3ZvIHVuYSByb3RhemlvbmUgY2hlIHZhZGEgYmVuZSBvIGFiYmlhIGZhdHRvIHVuIGdpcm8gY29tcGxldG8KCQkJCXdoaWxlIG5vdCBjaGVjayhDLCB0bXApIGFuZCBzaGlmdHNbcl0gPCBzaXplOgoJCQkJCXNoaWZ0c1tyXSArPSAxCgkJCQkJdG1wID0gdG1wWy0xOl0rdG1wWzotMV0KICAgICAgICAgICAgICAgICNTZSBobyBjb21waXV0byB1biBnaXJvIGNvbXBsZXRvIG5vbiBwb3NzbyBzaXN0ZW1hcmUgbGUgcmlnaGUKCQkJCWlmIHNoaWZ0c1tyXSA9PSBzaXplOgoJCQkJCXJhaXNlIERvZXNOb3RGaXQKICAgICAgICAgICAgICAgICNtYXJrbyBsZSBwb3Npemlvbmkgb2NjdXBhdGUgZGFsbGEgcmlnYSBjb3JyZW50ZSBydW90YXRhCgkJCQlDID0gbGlzdChtYXAoc3VtLCB6aXAoQywgdG1wKSkpCgkJCXJldHVybiBzaXplLCBzaGlmdHMKCQlleGNlcHQgRG9lc05vdEZpdDoKCQkJcGFzcwogICAgICAgIAogICAgICAgICNyaXRlbnRvIGNvbiB1bmEgZGltZW5zaW9uZSBwacO5IGdyYW5kZQoJCWlmIHBvdzI6CgkJCXNpemUgPSBzaXplIDw8IDEKCQllbHNlOgoJCQlzaXplICs9IDEKCmRlZiBvdXRwdXRfY19oYXNoX2Z1bmMoZGF0YSwgcHJlZml4PSIiLCBwb3cyPVRydWUpOgogICAgc2l6ZSwgc2hpZnRzID0gaGFzaF9mdW5jKGRhdGEsIHBvdzIpCiAgICB0c2l6ZSA9IHByZWZpeCsiU0laRSIKICAgIGRlZiB0c2hpZnRzKG4pOgogICAgICAgIHJldHVybiBwcmVmaXgrIlNISUZUU1siK3N0cihuKSsiXSIKICAgIGRlZiB0dGFibGUobik6CiAgICAgICAgcmV0dXJuIHByZWZpeCsiVEFCTEVbIitzdHIobikrIl0iCiAgICBwcmludCgiI2RlZmluZSIsIHRzaXplLCBzaXplKQogICAgcHJpbnQoImludCIsIHRzaGlmdHMoc2l6ZSksICI9IHsiLCBlbmQ9IiIpCiAgICBpdCA9IGl0ZXIoc2hpZnRzKQogICAgcHJpbnQobmV4dChpdCksIGVuZD0iIikKICAgIGZvciBjIGluIGl0OgogICAgICAgIHByaW50KCIsIiwgYywgZW5kPSIiKQogICAgcHJpbnQoIn07IikKICAgIHByaW50KCJpbnQiLCB0dGFibGUoc2l6ZSksICI7IikKICAgIHByaW50KCIjZGVmaW5lIiwgcHJlZml4KyJsb29rdXAoaSkiLCB0dGFibGUoIigoaSkrIit0c2hpZnRzKCIoaSkvIit0c2l6ZSkrIiklIit0c2l6ZSkpCgpvdXRwdXRfY19oYXNoX2Z1bmMoZGF0YSwgIkhUXyIsIEZhbHNlKQ==