#include <iostream>
using namespace std;
 
const int Max = 4;
const int Min = Max / 2;
 
struct Item
{
    int cnt; // pocet klicu, nejvise Max, docasne Max+1
    int key [Max+1]; // cnt klicu
    Item * ref [Max+2]; // cnt+1 ukazatelu
    Item ();
};
 
Item::Item ()
{
    cnt = 0;
    for (int i = 0; i < Max+1; i++) key [i] = 0;
    for (int i = 0; i < Max+2; i++) ref [i] = nullptr;
}
 
void shift (Item* p, int i, int new_key, Item* new_ref)
{
    for (int k = p->cnt-1; k >= i; k--) p->key [k+1] = p->key [k];
    p->key [i] = new_key;
 
    for (int k = p->cnt; k >= i+1; k--) p->ref [k+1] = p->ref [k];
    p->ref [i+1] = new_ref;
 
    p->cnt ++;
}
 
void split (Item * p, int & center, Item * & r)
// rozdelit p .... p, center, r
{
    int n = p->cnt;
    int a = Max/2; // a prvku zustane v p, tj. key[0] ...key[a-1]
    center = p->key [a]; // nahoru
    int b = n-a-1; // b prvku umistit do r, 
 
    r = new Item; // novy pravy prvek
    // z p presuneme key[a+1], ... key[n-1] 
    // do r key[0] ... key[b-1]
    for (int i = a+1; i < n; i++) r->key [i-a-1] = p->key [i];
    // ref[0] ... ref [a] ponechame v p, a klicu, a+1 ukazatelu
    // ref[a+1] ... ref [n] presuneme do r
    for (int i = a+1; i < n+1 ; i++) r->ref [i-a-1] = p->ref [i];
 
    // pro poradek odstranit stare hodnoty
    for (int i = a; i < n; i++) p->key [i] = 0;
    for (int i = a+1; i < n+1; i++) p->ref [i] = nullptr;
 
    // nove pocty prvku
    p->cnt = a;
    r->cnt = b;
}
 
void insertValue (Item * p, int value)
{
    int i = 0;
    while (i < p->cnt && p->key [i] < value) i++;
    if (i < p->cnt && p->key [i] == value)
    {
        // klic je jiz pritomen
    }
    else
    {
        if (p->ref [0] == nullptr)
        {
            // list
            shift (p, i, value, nullptr);
        }
        else
        {
            Item* t = p->ref [i];
            insertValue (t, value);
            if (t->cnt > Max)
            {
                int center;
                Item* r;
                split (t, center, r);
                shift (p, i, center, r);
            }
        }
    }
}
 
void enter (Item * & p, int value)
{
    if (p == nullptr)
    {
        p = new Item;
        p->cnt = 0;
    }
    insertValue (p, value);
 
    if (p->cnt > Max)
    {
        int center;
        Item * r;
        split (p, center, r);
 
        Item * t = new Item; // novy koren stromu
        t->cnt = 1;
        t->ref [0] = p;
        t->key [0] = center;
        t->ref [1] = r;
        p = t;
    }
}
 
void print (Item* p, int level = 1)
{
    if (p != nullptr)
    {
        for (int i = 2; i <= level; i++)
            cout << "         ";
 
        for (int i = 0; i < p->cnt; i++)
        {
            cout << p->key [i];
            if (i < p->cnt-1) cout << ",";
        }
        cout << endl;
 
        for (int i = 0; i < p->cnt+1; i++)
            print (p->ref [i], level+1);
    }
}
 
void printValue (Item* p)
{
    if (p != nullptr)
    {
        for (int i = 0; i < p->cnt; i++)
        {
            printValue (p->ref [i]);
            cout << p->key [i] << " ";
        }
        printValue (p->ref [p->cnt]);
    }
}
 
int main()
{
    Item * root = nullptr;
    enter (root, 30);
    enter (root, 10);
    enter (root, 20);
    enter (root, 40);
    enter (root, 50);
 
    for (int i = 20; i <= 30; i++)
        enter (root, i);
 
    enter (root, 51);
    enter (root, 52);
    // enter (root, 53);
 
    /*
    for (int i = 1; i <= 1024; i++)
        enter (root, i);
    */
 
    print (root);
 
    cout << endl;
    printValue (root);
    cout << endl;
 
    cout << "O.K." << endl;
}