#include <fstream.h>

struct node {
	int DataItem0;
	int DataItem1;
	int DataItem2;
	node* Parent;
	node* Child0;
	node* Child1;
	node* Child2;
	node* Child3;
};

typedef node* ptrType;

ptrType createNode() {
	ptrType newNode = new node;
	
	newNode->DataItem0 = 0;
	newNode->DataItem1 = 0;
	newNode->DataItem2 = 0;
	newNode->Child0 = NULL;
	newNode->Child1 = NULL;
	newNode->Child2 = NULL;
	newNode->Child3 = NULL;
	newNode->Parent = NULL;
	
	return newNode;
}

ptrType root = createNode();

bool isLeaf(ptrType curNode) {
	if ( curNode->Child0 != NULL ) return false;
	if ( curNode->Child1 != NULL ) return false;
	if ( curNode->Child2 != NULL ) return false;
	if ( curNode->Child3 != NULL ) return false;
	return true;
}

bool isFull(ptrType curNode) {
	if ( curNode->DataItem0 == 0 ) return false;
	if ( curNode->DataItem1 == 0 ) return false;
	if ( curNode->DataItem2 == 0 ) return false;
	return true;
}

void setLink(ptrType parentNode, ptrType childNode) {
	childNode->Parent = parentNode;

	if (parentNode->Child0 == NULL) {
		parentNode->Child0 = childNode;
		return;
	}
	if (parentNode->Child1 == NULL) {
		parentNode->Child1 = childNode;
		return;
	}
	if (parentNode->Child2 == NULL) {
		parentNode->Child2 = childNode;
		return;
	}
	if (parentNode->Child3 == NULL) {
		parentNode->Child3 = childNode;
		return;
	}
}

void placeValue(int Value, ptrType curNode) {
	int temp = 0;

	if ( curNode->DataItem0 == 0 ) {
		curNode->DataItem0 = Value;
		return;
	} else if ( Value < curNode->DataItem0 ) {
		temp = Value;
		Value = curNode->DataItem0;
		curNode->DataItem0 = temp;
	}

	if ( curNode->DataItem1 == 0 ) {
		curNode->DataItem1 = Value;
		return;
	} else if ( Value < curNode->DataItem1 ) {
		curNode->DataItem2 = curNode->DataItem1;
		curNode->DataItem1 = Value;
	}
	else {
		curNode->DataItem2 = Value;
	}
}

void splitNode(ptrType curNode) {
	ptrType newNode = createNode();
	
	if ( curNode == root ) {
		ptrType newRoot = createNode();
		setLink(newRoot, curNode);
		setLink(newRoot, newNode);
		root = newRoot;
	} else {
		setLink(curNode->Parent, newNode);
	}
	
	placeValue(curNode->DataItem1, curNode->Parent);
	curNode->DataItem1 = 0;
	
	newNode->DataItem0 = curNode->DataItem2;
	newNode->Child0 = curNode->Child2;
	newNode->Child1 = curNode->Child3;
	
	curNode->DataItem2 = 0;
	curNode->Child2 = NULL;
	curNode->Child3 = NULL;
}

ptrType nextChild(int searchValue, ptrType curNode) {
	if ( searchValue < curNode->DataItem0 ) return curNode->Child0;
	else if ((curNode->DataItem1 == 0) || (searchValue < curNode->DataItem1)) return curNode->Child1;
	else if ((curNode->DataItem2 == 0) || (searchValue < curNode->DataItem2)) return curNode->Child2;
	else return curNode->Child3;
}

void insertValue(int value) {
	ptrType curNode = root;

	while ( !isLeaf(curNode) ) {
		if ( isFull(curNode) ) splitNode(curNode);
		curNode = nextChild(value, curNode);
	}
	
	if ( isFull(curNode) ) splitNode(curNode);
	if ( !isLeaf(curNode) ) curNode = nextChild(value, curNode);
	
	placeValue(value, curNode);
}

void visit(int dataItem,  ofstream OutFile) {
	if (dataItem != 0 ) OutFile << dataItem << " ";
}

void inOrder(ptrType curNode, ofstream OutFile) {
	if ( isLeaf(curNode) ) {
		visit(curNode->DataItem0, OutFile);
		visit(curNode->DataItem1, OutFile);
		visit(curNode->DataItem2, OutFile);
	} else if (curNode->DataItem0 != 0) {
		inOrder(curNode->Child0, OutFile);
		visit(curNode->DataItem0, OutFile);
		inOrder(curNode->Child1, OutFile);

		if (curNode->DataItem1 != 0 ) {
			visit(curNode->DataItem1, OutFile);
			inOrder(curNode->Child2, OutFile);

			if (curNode->DataItem2 != 0 ) {
				visit(curNode->DataItem2, OutFile);
				inOrder(curNode->Child3, OutFile);
			}
		}
	}
}

void main() {
	int input = 0;
	
	ifstream InFile("numbers.txt");

	while (InFile.peek() != EOF ) {
		InFile >> input;
		InFile.get();
		insertValue(input);
	}
	
	ofstream OutFile("output.txt");
	inOrder(root, OutFile);
	OutFile.close();
	InFile.close();
}