#include <iostream>
// #include <cassert>
#include <time.h>
using namespace std;
 
const int Max = 4; // max. pocet klicu v jednom uzlu
const int Min = Max / 2;
 
struct Item
{
    int cnt; // 1 <= cnt <= Max, cnt == Max+1 pri preplneni
    int key [Max+1]; // o jeden klic navic pri preplneni
    Item * ref [Max+2];
    // vyuzivame key [0] , ... , key [cnt-1]
    // vyuzivame ref [0] , ... , ref [cnt-1], ref [cnt]
    Item ();
};
 
Item::Item ()
{
    cnt = 0;
    for (int k = 0; k < Max+1; k++) key [k] = -1;
    for (int k = 0; k < Max+2; k++) ref [k] = nullptr;
}
 
void split (Item * p, int & center, Item * & r)
{
    int n = p->cnt;
 
    int a = Min; // pocet klicu v levem bloku, key[0] ...key[a-1]
    center = p->key [a];
    int b = n - a - 1; // pocet klicu v pravem bloku
 
    r = new Item;
 
    // ponechame v levem bloku, key[0] ...key[a-1]
    // nahoru key [a]
    // do praveho bloku, key[a+1] ... key[n-1]
    for (int k = a+1; k <= n-1; k++) r->key [k-a-1] = p->key [k];
 
    // ponechame v levem bloku, ref[0] ... ref[a]
    // do praveho bloku, ref[a+1] ... ref[n]
    for (int k = a+1; k <= n; k++) r->ref [k-a-1] = p->ref [k];
 
    // pro poradek
    for (int k = a; k <= n-1; k++) p->key [k] = -1;
    for (int k = a+1; k <= n; k++) p->ref [k] = nullptr;
 
    p->cnt = a;
    r->cnt = b;
}
 
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];
    for (int k = p->cnt; k >= i+1; k--) p->ref [k+1] = p->ref [k];
    p->key [i] = new_key;
    p->ref [i+1] = new_ref;
    p->cnt++;
}
 
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) { /* duplicita */ }
    else
    {
        if (p->ref [0] == nullptr)
        {
            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;
        t->cnt = 1;
        t->ref [0] = p;
        t->key [0] = center;
        t->ref [1] = r;
        p = t; // novy koren
    }
}
 
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; 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, 20);
    enter (root, 10);
    enter (root, 40);
    enter (root, 50);
 
    for (int i = 21; 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);
    */
 
    /*
    srand (time (nullptr));
    for (int i = 1; i <= 1000000; i++)
        enter (root, (rand () % 1000) + 1000 * (rand () % 1000));
    */
 
    print (root);
    printValue (root);
 
    cout << "O.K." << endl;
}