value

import re
import math

cache = {0:"<()>"}

def find(x,i,j):
    return i*((x**2+x)/2)+(j+1)*((x**2-x)/2)

def solve(x, i, j):
    a = (i + j + 1)/2.
    b = (i - j - 1)/2.
    c = -x
    return (-b + math.sqrt(b**2 - 4*a*c))/(2*a)

def size(i,j=0):
    return 4*(i+j)+14

def polynomials(n):
    upperBound = int(4*math.log(n,2))
    i = 0
    answers = []
    while size(i) < upperBound:
        for j in range(i):
            sol = int(solve(n, i-j, j)+.5)
            if find(sol, i-j, j) == n:
                answers.append((sol, i-j, j))
        i += 1
    return answers

def complement(character):
        dict = {"(":")","{":"}","<":">","[":"]",")":"(","}":"{",">":"<","]":"["}
        return dict[character]

def findMatch(snippet, index):
        increment = 1 if snippet[index] in "({<[" else -1
        stack = []
        if snippet[index] in "(){}<>[]":
                stack.append(snippet[index])
        while len(stack) > 0 and index + increment < len(snippet):
                index += increment
                if snippet[index] in "(){}<>[]":
                        if complement(snippet[index]) == stack[-1]:
                                stack = stack[:-1]
                        else:
                                stack.append(snippet[index])
        return index

def isPrime(n):
    return not [0 for x in range(2,int(n**.5)+1) if n%x==0] and n>1

def getPrimeFactors(n):
    return [x for x in range(2,n/2) if n%x==0 and isPrime(x)]

def divHardcode(n,m):
    assert n%m == 0
    assert m != 1
    assert n != 1
    binary = bin(m)[3:]
    return (binary.count("1")+len(binary))*"("+getBF(n/m)+")"*binary.count("1")+binary.replace("1","){}{}").replace("0","){}")

def isTriangular(n):
    #Triangles must be between sqrt(2n) and cbrt(2n)
    if n < 0: return isTriangular(-n)
    for x in range(int((2*n)**(1/3.)),int((2*n)**.5)+1):
        if (x**2+x) == 2*n:
            return True
    return False

def getTriangle(n):
    if n < 0: return -getTriangle(-n)
    #Triangles must be between sqrt(2n) and cbrt(2n)
    for x in range(int((2*n)**(1/3.)),int((2*n)**.5)+1):
        if (x**2+x) == 2*n:
            return x
    #If we don't find one we made a mistake
    assert False

def getSimpleBF(n):
    if n in cache:return cache[n]
    if n < 0:
        # There is room for better solutions here
        return "["+getSimpleBF(-n)+"]"
    elif n == 0:
        return ""
    elif n < 6:
        return "()"*n
    else:
        #Non-edge cases
        solutions = []
    factors = getPrimeFactors(n)
        if n >= 78 and isTriangular(n):
            solutions.append(
                min([push(getTriangle(n))+"{({}[()])}{}","<"+push(getTriangle(n)+1)+">{({}[()])}{}"],key=len)
            )
    polynomialSolutions = polynomials(n)
    for polynomial in polynomialSolutions:
        solutions.append("<%s>{%s({}[()])%s}{}"%(push(polynomial[0]),"({})"*polynomial[1],"({})"*polynomial[2]))
        #Mod 3 tricks
        if n % 3 == 2:
           solutions.append(("((%s)()){}{}")%getBF(n/3))
        elif n % 3 == 1:
           solutions.append(("((%s)()()){}{}")%getBF(n/3-1))
        #Basic solutions
        if isPrime(n):
            solutions.append(getSimpleBF(n-1) + "()")
        else:
            #TODO multithread
            solutions += map(lambda m:divHardcode(n,m),factors)
        return min(solutions,key=lambda x:len(unpack(x)))

def getBF(n):
    if n in cache: return cache[n]
    result = getSimpleBF(n)
    index = n - 1
    while index > n-(len(result)/2):
        score = getSimpleBF(index)+getSimpleBF(n-index)
        if len(score) < len(result):result = score
        index -= 1
    index = n + 1
    while index < n+(len(result)/2):
        score = getSimpleBF(index)+getSimpleBF(n-index)
        if len(score) < len(result):result = score
        index += 1
    cache[n] = result
    return result

def unpack(string):
    reMatch = re.match("\(*<",string)
    if reMatch:
        location =reMatch.span()
        return string[location[1]:findMatch(string,location[1]-1)] +string[:location[1]-1] + string[findMatch(string,location[1]-1)+1:]
    return string

def push(n):
    return unpack("("+getBF(n)+")")

def kolmo(string):
    code = push(ord(string[-1]))
    stringVector = map(ord,string)
    for x,y in zip(stringVector[-1:0:-1],stringVector[-2::-1]):
        code = "("+code+getBF(y-x)+")"
    code = code.replace("<()>)",")")
    return code

if __name__ == "__main__":
    print getBF(40)