#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct drvo
{
    int broj;
    char boja[10];
    int balans;
    struct drvo *levi,*desni;
}DRVO;

enum
{
    PLAVI,
    CRVENI
};

#define novi(x) x=(DRVO *) malloc(sizeof(DRVO))

void padding ( char ch, int n )
{
  int i;
  for ( i = 0; i < n; i++ )
    putchar ( ch );
}
void ispis ( DRVO *root, int level )
{
  int i;
  if ( root == NULL ) {
    padding ( '\t', level );
    puts ( "~" );
  }
  else {
    ispis ( root->desni, level + 1 );
    padding ( '\t', level );
    printf ( "%d %s\n", root->broj, root->boja);
    ispis ( root->levi, level + 1 );
  }
}

int dubina(DRVO *p)
{
    int dl=0,dd=0;
    if(p)
    {
        if (p->levi) 
            dl=dubina(p->levi);
        if (p->desni) 
            dd=dubina(p->desni);
        if (dl>dd) 
            return ++dl;
        else 
            return ++dd;
    }
    else 
        return 0;
}


void lrotacija(DRVO **t)
{
    DRVO *poml,*pomd;
    int stari_balans;
    poml = *t;
    pomd = poml->desni;
    poml->desni = pomd->levi;
    pomd->levi = poml;
    *t=pomd;
    poml->balans=dubina(poml->desni)-dubina(poml->levi);
    pomd->balans=dubina(pomd->desni)-dubina(pomd->levi);
}

void drotacija(DRVO **t)
{
    DRVO *poml,*pomd;
    int stari_balans;
    pomd = *t;
    poml = pomd->levi;
    pomd->levi = poml->desni;
    poml->desni = pomd;
    *t=poml;
    poml->balans=dubina(poml->desni)-dubina(poml->levi);
    pomd->balans=dubina(pomd->desni)-dubina(pomd->levi);
}

int dodaj(DRVO **p, int vrednost, char *boja)
{
    int inkrement, rezultat;
    DRVO *t = *p;
    rezultat = 0;
    if(t==NULL)
    {
        novi(t);
        if(t==NULL)
        {
            printf("Greska pri alociranju memorije\n");
            exit(1);
        }
        t->broj = vrednost;
        strcpy(t->boja, boja);
        t->levi = t->desni = NULL;
        t->balans = 0;
        rezultat = 1;
    }
    else
    {
        if(vrednost > t->broj || (vrednost == t->broj && !strcmp(boja, "CRVENI")))
            inkrement=dodaj(&(t->desni),vrednost, boja);
        else 
            inkrement=-dodaj(&(t->levi),vrednost, boja);
        t->balans += inkrement;
        if(inkrement!=0 && t->balans!=0)
        {
            if(t->balans<-1 )
            {
                if(t->levi->balans<0) 
                    drotacija(&t);
                else
                { 
                    lrotacija(&(t->levi)); 
                    drotacija(&t); 
                }
            }
            else if(t->balans>1)
            {
                if(t->desni->balans>0 ) 
                    lrotacija(&t);
                else
                { 
                    drotacija(&(t->desni)); 
                    lrotacija(&t); 
                }
            }
            else rezultat = 1;
        }
    }
    *p = t;
    return rezultat;
}

DRVO* form(int *n)
{
    DRVO *koren;
    int k, i;
    char boja[20];
    koren=NULL;
    scanf("%d",n);
    for (int i = 0; i < *n; i++)
    {
        scanf("%d%s",&k, boja);
        dodaj(&koren,k, boja);
    }
    return koren;
}

void sredi(DRVO **p)
{
    DRVO *t;
    if(*p)
    {
        t=*p;
        if( t->balans<-1 )
        {
            if( t->levi->balans<0 ) 
                drotacija(&t);
            else
            {
                lrotacija(&(t->levi)); 
                drotacija(&t);
            }
        }
        else if( t->balans>1 )
        {
            if( t->desni->balans>0 ) 
                lrotacija(&t);
            else
            {
                drotacija(&(t->desni)); 
                lrotacija(&t);
            }
        }
        *p=t;
    }
}


DRVO* nadji(DRVO **p)
{
    DRVO *pom,*pom1;
    DRVO* rez;
    pom=*p;
    if (!pom->levi) 
    {
        rez=pom;
        pom=pom->desni;
    }
    else 
        rez=nadji(&(pom->levi));
    if (pom) 
    {
        pom->balans=dubina(pom->desni)-dubina(pom->levi);
        sredi(&pom);
    }
    *p=pom;
    return rez;
}

DRVO* obrisi_b(DRVO *p,int k, char *boja)
{
    DRVO *pom;
    if(!p) 
        return NULL;
    if (p->broj==k && !strcmp(p->boja,boja)) 
    {
        if((!p->levi) && (!p->desni)) 
        {
            free(p);
            return NULL;
        }
        if((!p->levi) && (p->desni)) 
        {
            pom=p->desni;
            free(p);
            return pom;
        }
        if((p->levi) && (!p->desni))
        {
            pom=p->levi;
            free(p);
            return pom;
        }
        if((p->levi) && (p->desni))
        {
            DRVO *temp = nadji(&(p->desni));
            p->broj=temp->broj;
            strcpy(p->boja,temp->boja);
            p->balans=dubina(p->desni)-dubina(p->levi);
            sredi(&p);
            return p;
        }
    }
    if(k<p->broj || (k==p->broj && !strcmp(boja, "PLAVI")))
    {
        p->levi=obrisi_b(p->levi,k, boja);
        p->balans=dubina(p->desni)-dubina(p->levi);
        sredi(&p);
        return p;
    }
    else
    {
        p->desni=obrisi_b(p->desni,k, boja);
        p->balans=dubina(p->desni)-dubina(p->levi);
        sredi(&p);
        return p;
    }
}

int izracunaj_boju(DRVO *p, char *boja)
{
    if(p)
    {
        int broj = 0;
        if(!strcmp(p->boja, boja))
            broj++;
        broj += izracunaj_boju(p->levi, boja);
        broj += izracunaj_boju(p->desni, boja);
        return broj;
    }
    return 0;
}

DRVO * nadji_deljiv_sa_tri(DRVO *p)
{
    if(p)
    {
        DRVO *temp = p;
        if(temp->broj %3 == 0)
            return temp;
        temp = nadji_deljiv_sa_tri(p->levi);
        if(temp!= NULL && temp->broj %3 == 0)
            return temp;
        temp = nadji_deljiv_sa_tri(p->desni);
        if(temp!= NULL &&temp->broj %3 == 0)
            return temp;
    }
    return NULL;
}


DRVO* deljivi_sa_tri(DRVO *root)
{
    DRVO *p;
    while((p=nadji_deljiv_sa_tri(root)) != NULL)
        root = obrisi_b(root, p->broj, p->boja);
    return root;
}

DRVO * nadji_nedeljiv_sa_tri(DRVO *p)
{
    if(p)
    {
        DRVO *temp = p;
        if(temp->broj %3 != 0)
            return temp;
        temp = nadji_nedeljiv_sa_tri(p->levi);
        if(temp!= NULL && temp->broj %3 != 0)
            return temp;
        temp = nadji_nedeljiv_sa_tri(p->desni);
        if(temp!= NULL && temp->broj %3 != 0)
            return temp;
    }
    return NULL;
}

DRVO * nedeljivi_sa_tri(DRVO *root)
{
    DRVO *p;
    while ((p=nadji_nedeljiv_sa_tri(root)) != NULL)
        root = obrisi_b(root, p->broj, p->boja);
    return root;
}

DRVO* najlbizi(DRVO *p, int k)
{
    DRVO *minDrvo = p;
    if(p)
    {
        DRVO *temp;
        int min = abs(p->broj - k);
        temp = najlbizi(p->levi, k);
        if(temp!= NULL && (abs(temp->broj - k)<min))
        {
            minDrvo = temp;
            min = abs(temp->broj - k);
        }
        temp = najlbizi(p->desni, k);
        if(temp!= NULL && (abs(temp->broj - k)<min))
        {
            minDrvo = temp;
            min = abs(temp->broj - k);
        }

    }
    return minDrvo;
}

int main()
{
    DRVO *p;
    int n, pobeda, k;
    p=form(&n);
    ispis(p, 0);
    printf("-------------------------\n");
    scanf("%d", &k);
    if(k%3==0)
        p = nedeljivi_sa_tri(p);
    else
        p =  deljivi_sa_tri(p);
    ispis(p, 0);
    if(izracunaj_boju(p, "PLAVI") > izracunaj_boju(p, "CRVENI"))
        printf("Plavi tim ima više učesnika\n");
    else
        printf("Crveni tim ima više učesnika\n");
    DRVO * temp = najlbizi(p, k);
    printf("Najlbizi ucesnik je %d %s\n", temp->broj, temp->boja);
}