#include <fstream.h>

int tree234[100][3];

int index = 0;

int parent = (index - 1) / 4;

bool findItem(int searchValue, int index) {
	for ( int i=0; i<3; i++ ) {
		if ( tree234[index][i] == searchValue ) return true;
	}
	return false;
}

bool isLeaf(int index) {
	int child0 = index * 4 + 1;
	for ( int i=child0; i<child0+4; i++ ) {
		if ( tree234[i][0] != 0 ) return false;
	}
	return true;
}

int nextChild(int searchValue, int index) {
	for ( int i=0; i<3; i++ ) {
		if ( searchValue < tree234[index][i] ) return index * 4 + i + 1;
	}
	return index * 4 + 4;
}

void setLink(int n1, int n2) {
	for ( int i=0; i<4; i++ ) {
		if ( tree234[n1*4+1+i][0] == 0 ) {
			tree234[n1*4+1+i][0] = n2;
		}
	}
}

void placeValue(int v, int n) {
	int temp = 0;
	for ( int i=0; i<3; i++ ) {
		if ( tree234[n][i] == 0 ) {
			tree234[n][i] = v;
			return;
		} else if ( v < tree234[n][i] ) {
			temp = v;
			v = tree234[n][i];
			tree234[n][i] = temp;
		}
	}
}

void splitNode(int n) {
	if ( n == 0) {
		for ( int i=98; i>=0; i-- ) {
			for ( int j=0; j<3; j++ ) {
				tree234[i][j] = tree234[i+1][j];
			}
		}
	} else {
		setLink((n-1)/4, n);
	}

	int newNode = n + 1;
	tree234[newNode][0] = tree234[n][2];
	tree234[n][2] = 0;
	placeValue(tree234[n][1], (n-1)/4);
	tree234[n][1] = 0;
}

bool isFull(int index) {
	for ( int i=0; i<3; i++ ) {
		if ( tree234[index][i] == 0 ) return false;
	}
	return true;
}

void insertValue(int value) {
	int n = 0;
	while ( !isLeaf(n) ) {
		if ( isFull(n) ) splitNode(n);
		n = nextChild(value, n);
	}
	placeValue(value, n);
}

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

void inOrder(int curNode, ofstream OutFile) {
	if ( isLeaf(curNode) ) {
		for ( int i=0; i<3; i++ ) {
			visit(tree234[curNode][i], OutFile);
		}
	} else if (tree234[curNode][0] != 0) {
		int child0 = index * 4 + 1;
		int child1 = child0 + 1;
		int child2 = child1 + 1;
		int child3 = child2 + 1;
		inOrder(child0, OutFile);
		for ( int i=0; i<3; i++ ) {
			if (tree234[curNode][i+1] != 0 ) {
				visit(tree234[curNode][0], OutFile);
				inOrder(child0+1+i, OutFile);
			}
		}
	}
}

bool search(int searchValue, int index) {
	bool bRetVal = false;

	if ( index < 0 ) bRetVal = false;
	else if ( findItem(searchValue, index) ) bRetVal = true;
	else if ( !isLeaf(index) )
		bRetVal = search(searchValue, nextChild(searchValue, index));
	return bRetVal;

}

void main() {
	int input = 0;

	ifstream InFile("numbers.txt");

	while (InFile.peek() != EOF ) {
		InFile >> input;
		InFile.get();
		insertValue(input);
	}

	ofstream OutFile("output.txt");
	inOrder(0, OutFile);
	OutFile.close();
	InFile.close();
}