from math import sqrt, ceil, log2
from sys import exit
data = []
ddata = dict()
def fill(r1, r2, r3, rest):
	if len(r1) > 3:
		return
	if not rest:
		k = (list(sorted(r1)),list(sorted(r2)),list(sorted(r3)))
		ddata[str(k)] = k
		return
	t = [rest[0]]
	fill(t+r1, r2, r3, rest[1:])
	fill(r1, t+r2, r3, rest[1:])
	fill(r1, r2, t+r3, rest[1:])

fill([],[],[],[0,1,2,3,4])

def to_bin(r):
	c = 0
	for i in r:
		c |= 1<<i
	return c

for _, v in ddata.items():
	r1, r2, r3 = v
	data.append((to_bin(r1)<<10) | (to_bin(r2)<<5) | to_bin(r3))


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)

ZnJvbSBtYXRoIGltcG9ydCBzcXJ0LCBjZWlsLCBsb2cyCmZyb20gc3lzIGltcG9ydCBleGl0CmRhdGEgPSBbXQpkZGF0YSA9IGRpY3QoKQpkZWYgZmlsbChyMSwgcjIsIHIzLCByZXN0KToKCWlmIGxlbihyMSkgPiAzOgoJCXJldHVybgoJaWYgbm90IHJlc3Q6CgkJayA9IChsaXN0KHNvcnRlZChyMSkpLGxpc3Qoc29ydGVkKHIyKSksbGlzdChzb3J0ZWQocjMpKSkKCQlkZGF0YVtzdHIoayldID0gawoJCXJldHVybgoJdCA9IFtyZXN0WzBdXQoJZmlsbCh0K3IxLCByMiwgcjMsIHJlc3RbMTpdKQoJZmlsbChyMSwgdCtyMiwgcjMsIHJlc3RbMTpdKQoJZmlsbChyMSwgcjIsIHQrcjMsIHJlc3RbMTpdKQoKZmlsbChbXSxbXSxbXSxbMCwxLDIsMyw0XSkKCmRlZiB0b19iaW4ocik6CgljID0gMAoJZm9yIGkgaW4gcjoKCQljIHw9IDE8PGkKCXJldHVybiBjCgpmb3IgXywgdiBpbiBkZGF0YS5pdGVtcygpOgoJcjEsIHIyLCByMyA9IHYKCWRhdGEuYXBwZW5kKCh0b19iaW4ocjEpPDwxMCkgfCAodG9fYmluKHIyKTw8NSkgfCB0b19iaW4ocjMpKQoKCmRlZiBoYXNoX2Z1bmMoZGF0YSwgcG93Mj1UcnVlKToKCWNsYXNzIERvZXNOb3RGaXQoRXhjZXB0aW9uKToKCQlwYXNzCiAgICAKICAgICNjb250cm9sbGEgY2hlIGVsZW1lbnRpIG5lbGxhIHN0ZXNzYSBwb3NpemlvbmUgbm9uIHNpYW5vIHNldHRhdGkKCWRlZiBjaGVjayhsLCByKToKCQlmb3IgYSwgYiBpbiB6aXAobCwgcik6CgkJCWlmIChhJmIpPT0xOgoJCQkJcmV0dXJuIEZhbHNlCgkJcmV0dXJuIFRydWUKICAgIAogICAgI2NhbGNvbG8gZGltZW5zaW9uZSBtaW5pbWEKCXNpemUgPSBtYXgoY2VpbChzcXJ0KG1heChkYXRhKSkpLCBsZW4oZGF0YSkpCglpZiBwb3cyOgoJCXNpemUgPSAxPDxjZWlsKGxvZzIoc2l6ZSkpCiAgICAKICAgICNwcm9jZWRvIHBlciB0ZW50YXRpdmkKCXdoaWxlIFRydWU6CgkJdHJ5OgoKCQkJc3F1YXJlID0gW1swXSpzaXplIGZvciBpIGluIHJhbmdlKHNpemUpXQoJCQlyb3djb3VudHMgPSBbMF0gKiBzaXplCgkJCQogICAgICAgICAgICAjdGFiZWxsYSBkYSBjb21wcmltZXJlCgkJCWZvciBjIGluIGRhdGE6CgkJCQlzcXVhcmVbYy8vc2l6ZV1bYyVzaXplXSA9IDEKCQkJCXJvd2NvdW50c1tjLy9zaXplXSs9MQoJCQkKCQkJbW9zdF9mcmVxdWVudF9yb3dfb3JkZXIgPSByZXZlcnNlZChzb3J0ZWQoemlwKHJvd2NvdW50cywgcmFuZ2Uoc2l6ZSkpKSkKCQkJCiAgICAgICAgICAgICNzaGlmdCByZWxhdGl2byBhZCBvZ25pIHJpZ2EKCQkJc2hpZnRzID0gWzBdKnNpemUKCiAgICAgICAgICAgICN0YWJlbGxhIGNvbXByZXNzYSBpbiB1bmEgcmlnYQoJCQlDID0gWzBdKnNpemUKCQkJCiAgICAgICAgICAgICNjZXJjbyBkaSBydW90YXJlIG9nbmkgcmlnYSBpbiBtb2RvIGNoZSBub24gY2kgc2lhbm8gZHVwbGljYXRpIHN1bGxlIGNvbG9ubmUKCQkJZm9yIF8sIHIgaW4gbW9zdF9mcmVxdWVudF9yb3dfb3JkZXI6CgkJCQl0bXAgPSBzcXVhcmVbcl0KICAgICAgICAgICAgICAgICNydW90byBmaW5jaMOpIG5vbiB0cm92byB1bmEgcm90YXppb25lIGNoZSB2YWRhIGJlbmUgbyBhYmJpYSBmYXR0byB1biBnaXJvIGNvbXBsZXRvCgkJCQl3aGlsZSBub3QgY2hlY2soQywgdG1wKSBhbmQgc2hpZnRzW3JdIDwgc2l6ZToKCQkJCQlzaGlmdHNbcl0gKz0gMQoJCQkJCXRtcCA9IHRtcFstMTpdK3RtcFs6LTFdCiAgICAgICAgICAgICAgICAjU2UgaG8gY29tcGl1dG8gdW4gZ2lybyBjb21wbGV0byBub24gcG9zc28gc2lzdGVtYXJlIGxlIHJpZ2hlCgkJCQlpZiBzaGlmdHNbcl0gPT0gc2l6ZToKCQkJCQlyYWlzZSBEb2VzTm90Rml0CiAgICAgICAgICAgICAgICAjbWFya28gbGUgcG9zaXppb25pIG9jY3VwYXRlIGRhbGxhIHJpZ2EgY29ycmVudGUgcnVvdGF0YQoJCQkJQyA9IGxpc3QobWFwKHN1bSwgemlwKEMsIHRtcCkpKQoJCQlyZXR1cm4gc2l6ZSwgc2hpZnRzCgkJZXhjZXB0IERvZXNOb3RGaXQ6CgkJCXBhc3MKICAgICAgICAKICAgICAgICAjcml0ZW50byBjb24gdW5hIGRpbWVuc2lvbmUgcGnDuSBncmFuZGUKCQlpZiBwb3cyOgoJCQlzaXplID0gc2l6ZSA8PCAxCgkJZWxzZToKCQkJc2l6ZSArPSAxCgpkZWYgb3V0cHV0X2NfaGFzaF9mdW5jKGRhdGEsIHByZWZpeD0iIiwgcG93Mj1UcnVlKToKICAgIHNpemUsIHNoaWZ0cyA9IGhhc2hfZnVuYyhkYXRhLCBwb3cyKQogICAgdHNpemUgPSBwcmVmaXgrIlNJWkUiCiAgICBkZWYgdHNoaWZ0cyhuKToKICAgICAgICByZXR1cm4gcHJlZml4KyJTSElGVFNbIitzdHIobikrIl0iCiAgICBkZWYgdHRhYmxlKG4pOgogICAgICAgIHJldHVybiBwcmVmaXgrIlRBQkxFWyIrc3RyKG4pKyJdIgogICAgcHJpbnQoIiNkZWZpbmUiLCB0c2l6ZSwgc2l6ZSkKICAgIHByaW50KCJpbnQiLCB0c2hpZnRzKHNpemUpLCAiPSB7IiwgZW5kPSIiKQogICAgaXQgPSBpdGVyKHNoaWZ0cykKICAgIHByaW50KG5leHQoaXQpLCBlbmQ9IiIpCiAgICBmb3IgYyBpbiBpdDoKICAgICAgICBwcmludCgiLCIsIGMsIGVuZD0iIikKICAgIHByaW50KCJ9OyIpCiAgICBwcmludCgiaW50IiwgdHRhYmxlKHNpemUpLCAiOyIpCiAgICBwcmludCgiI2RlZmluZSIsIHByZWZpeCsibG9va3VwKGkpIiwgdHRhYmxlKCIoKGkpKyIrdHNoaWZ0cygiKGkpLyIrdHNpemUpKyIpJSIrdHNpemUpKQoKb3V0cHV0X2NfaGFzaF9mdW5jKGRhdGEsICJIVF8iLCBGYWxzZSk=