metadata

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<k;i++)
using namespace std;
struct Node
{
    int *val;
    Node **cp;
    int end;
    int n;
    Node()
    {
        val=new int[5];
        cp=new Node *[6];
        end=1;
        n=0;
        rep(i,0,6) cp[i]= NULL;
    }
};
Node *root= new Node(), *np = NULL, *x = NULL;
int divide(Node *x, int i)
{
    int half;
    Node *np1, *np3;
    np3 = new Node();
    np3->end = 1;
    if (i!=-1)
    {
        Node *temp;
        temp = x->cp[i];
        half = temp->val[2];
        temp->val[2] = 0;
        temp->n--;
        rep(j,3,5)
        {
            np3->val[j - 3] = temp->val[j];
            np3->n++;
            temp->val[j] = 0;
            temp->n--;
        }
        x->cp[i + 1] = temp;
        x->cp[i + 1] = np3;
    }
    else
    {
        half = x->val[2];
        x->val[2] = 0;
        x->n--;
        np1 = new Node();
        np1->end = 0;
        x->end = 1;
        rep(j,3,5)
        {
            np3->val[j - 3] = x->val[j];
            np3->cp[j - 3] = x->cp[j];
            np3->n++;
            x->val[j] = 0;
            x->n--;
        }
        rep(j,0,6)
        {
            x->cp[j] = NULL;
        }
        np1->val[0] = half;
        np1->cp[np1->n] = x;
        np1->cp[np1->n + 1] = np3;
        np1->n++;
        root = np1;
    }
    return half;
}
void insert(int num)
{

    x = root;
    int  temp,i;
    if (x->end == 1 and x->n == 5)
    {
            temp = divide(x, -1);
            x = root;
            for(i=0;i<x->n;i++)
            {
                if (num < x->val[0]) break;
                else if ((num > x->val[i]) && (num < x->val[i + 1]))
                {
                    i++;
                    break;
                }
            }
            x = x->cp[i];
    }
    else
        {
            while (x->end != 1)
            {
            for(i=0;i<x->n;i++)
            {
                if (num < x->val[0])    break;
                else if ((num > x->val[i]) && (num < x->val[i + 1]))
                {
                    i++;
                    break;
                }
            }
            if((x->cp[i])->n != 5)  x = x->cp[i];
            else
                {
                    temp = divide(x, i);
                    x->val[x->n] = temp;
                    x->n++;
                    continue;
                }

            }
        }
    x->val[x->n] = num;
    sort(x->val,x->val+(x->n+1));
    x->n++;
}
void trav(Node *p)
{
    cout<<endl;
    rep(i,0,p->n)
    {
        if (p->end != 1) trav(p->cp[i]);
        cout << " " << p->val[i];
    }
    if (p->end != 1) trav(p->cp[p->n]);
    cout<<endl;
}
int main()
{
    int n;
    cout<<"enter number element\n";
    cin>>n;
    rep(i,0,n)
    {
        int t;
        cout<<"element:\n";
        cin>>t;
        insert(t);
    }
    cout<<"Tree is\n";
    trav(root);
}