// a full binary tree of depth D. checksum is the node count, 8191.
// each node is two pointers. new() rounds that plus the 5-word header up
// to 8 words (a 4-word block cannot hold the header). free of the owned
// root recycles the tree onto the size-class lists.
//   a  plain new / own / free
//   b  the same, marked o3 (calls and new still leave the region)
//   c  one array, used as an arena of pairs. no allocator in the loop.
// the same shapes are tests/bench/trees.c.
const int D = 12;
const int WORDS = 16382; // two words for each of the 8191 nodes

struct node { node* left, right; };
int* heap;
int used;

node*.u make(int depth) {
	node* n = new(node);
	if (depth > 0) {
		n.left = make(depth - 1);
		n.right = make(depth - 1);
	} else {
		n.left = 0;
		n.right = 0;
	}
	return u*n;
}
o3 node*.u make3(int depth) {
	node* n = new(node);
	if (depth > 0) {
		n.left = make3(depth - 1);
		n.right = make3(depth - 1);
	} else {
		n.left = 0;
		n.right = 0;
	}
	return u*n;
}
int check(node* n) {
	if (!n.left) return 1;
	return 1 + check(n.left) + check(n.right);
}
o3 int check3(node* n) {
	if (!n.left) return 1;
	return 1 + check3(n.left) + check3(n.right);
}

// a node id is its word index plus one, so 0 can mean "no child"
o3 int build(int depth) {
	int i = used;
	used = used + 2;
	if (depth > 0) {
		heap[i] = build(depth - 1);
		heap[i + 1] = build(depth - 1);
	} else {
		heap[i] = 0;
		heap[i + 1] = 0;
	}
	return i + 1;
}
o3 int ck(int id) {
	int i, l;
	if (id == 0) return 0;
	i = id - 1;
	l = heap[i];
	if (l == 0) return 1;
	return 1 + ck(l) + ck(heap[i + 1]);
}

int main() {
	int which = get_c(), reps = 0, ch = get_c(), r = 0;
	while (ch >= '0' && ch <= '9') { reps = reps * 10 + ch - '0'; ch = get_c(); }
	if (which == 'c') {
		heap = new(int, WORDS);
		while (reps > 0) { used = 0; r = ck(build(D)); reps--; }
		put_n(r); put_c(10);
		return 0;
	}
	while (reps > 0) {
		if (which == 'b') {
			node* root = make3(D);
			r = check3(root);
			free(d*root);
		} else {
			node* root = make(D);
			r = check(root);
			free(d*root);
		}
		reps--;
	}
	put_n(r); put_c(10);
	return 0;
}