import sys, os
import math

class Tree:
    def __init__(self, item, left, right):
        self.item = item
        self.left = left
        self.right = right

def make_tree(item, depth):
    if depth > 0:
        item2 = 2 * item
        depth -= 1
        return Tree(item, make_tree(item2 - 1, depth), make_tree(item2, depth))
    else:
        return Tree(item, None, None)

def check_tree(tree):
    if tree.left is not None:
        return tree.item + check_tree(tree.left) - check_tree(tree.right)
    else:
        return tree.item

def main(argv):
    min_depth = 4
    max_depth = max(min_depth + 2, int(argv[1]))
    stretch_depth = max_depth + 1

    print "stretch tree of depth %d\t check: %d" % (stretch_depth, check_tree(make_tree(0, stretch_depth)))

    long_lived_tree = make_tree(0, max_depth)

    for depth in xrange(min_depth, stretch_depth, 2):
        iterations = int(math.pow(2.0, (max_depth - depth + min_depth)))

        check = 0
        for i in xrange(1, iterations + 1):
            check += check_tree(make_tree(i, depth)) + check_tree(make_tree(-i, depth))

        print "%d\t trees of depth %d\t check: %d" % (iterations * 2, depth, check)

    print "long lived tree of depth %d\t check: %d" % (max_depth, check_tree(long_lived_tree))

def entry_point(argv):
    if len(argv) != 2:
        print "Argument missing"
        os._exit(2)
    main(argv)
    return 0

def target(*args):
    return entry_point, None

if __name__ == '__main__':
    main(sys.argv)