import java.util.*;

interface Dico {
  public Object chercher(int clŽ);
  public Object insŽrer(int clŽ, Object info);
  public Object supprimer(int clŽ);
/*   public int taille(); */
  public boolean estVide();
  public void lister();
/*   public void vider(); */
}

public class monDico implements Dico {
  private arbre_ab a;
  
  public monDico() {
    a = new arbre_ab();
  }
  
  public boolean estVide() { // crŽation d'un dico vide
    return a.estVide();
  }
  
  public Object chercher(int clŽ) {
    // retourne l'info associŽe ˆ la clŽ ou null si la clŽ n'est pas dans
    // le dictionnaire.
    return a.chercher(clŽ);
  }
  
  public Object insŽrer(int clŽ, Object info) {
    // Si un couple (clŽ, oldInfo) existe dŽjˆ dans le dico, on remplace
    // oldInfo par info et on retourne oldInfo, sinon on insŽre le couple
    // (clŽ, info) dans le dico et on retourne null.
    Object old_info = a.insŽrer(clŽ, info);
    if (a.tropPlein()) a = new arbre_ab(a); // Žclatement de la racine
    return old_info;
  }
  
  public Object supprimer(int clŽ) {
    // Si un couple (clŽ,info) existe dans l'arbre, on le supprime et on
    // retourne info. Sinon, on retourne null.
    Object old_info = a.supprimer(clŽ);
    if (a.estVide()) a = a.fils0();
    return old_info;
  }
  
  public void lister() {
    // les couples (clŽ, info) dans l'ordre des clŽs
    // a.lister1();
    // liste les couples (clŽ, info) dans l'ordre des clŽs en faisant
    // appara”tre la structure de l'arbre
    a.lister("");
  }
}

class Test {
  public static void main (String[] args) {
    Dico d = new monDico();
    System.out.println("---------------------- c 12");
    System.out.println(d.chercher(12));
 
    System.out.println("---------------------- i 12, 4, 8");
    d.insŽrer(12,"Paul");
    d.insŽrer(4,"BŽatrice");
    d.insŽrer(8,"HŽl�ne");
    d.lister();

    System.out.println("---------------------- c 12, 15, 8");
    System.out.println(d.chercher(12));
    System.out.println(d.chercher(15));
    System.out.println(d.chercher(8));

    System.out.println("---------------------- i 15, 2");
    d.insŽrer(15,"Richard");
    d.insŽrer(2,"AndrŽ");
    d.lister();

    System.out.println("---------------------- i 6");
    d.insŽrer(6,"Denis");
    d.lister();

    System.out.println("---------------------- s 12");
    d.supprimer(12);
    d.lister();
    System.out.println("---------------------- s 8");
    d.supprimer(8);
    d.lister();
    System.out.println("---------------------- s 4");
    d.supprimer(4);
    d.lister();
    System.out.println("---------------------- s 15");
    d.supprimer(15);
    d.lister();
    
    System.out.println("---------------------- arbre alŽatoire");
    Dico d2 = new monDico();
    Random r = new Random();
    int j;
    for (int i=0; i<45; i++) {
      j = r.nextInt();
      d2.insŽrer(j,"");
    }
    d2.lister();
    
  }
}

class RŽsultat {
  int clŽ;
  Object info;
}

class arbre_ab {
  private static final int a = 2;
  private static final int b = 4;
  private int nb_clŽs;
  private int[] clŽs;
  private Object[] infos;
  private arbre_ab[] fils;
  
  public arbre_ab() {
    // crŽation d'un noeud vide
    nb_clŽs = 0;
    clŽs = new int[b];
    infos = new Object[b];
    fils = new arbre_ab[b + 1];
  }
  
  public arbre_ab(arbre_ab f) {
    // crŽation d'une nouvelle racine par Žclatement de la racine actuelle.
    nb_clŽs = 0;
    clŽs = new int[b];
    infos = new Object[b];
    fils = new arbre_ab[b + 1];
    fils[0] = f;
    Žclater(0);
  }
  
  public boolean estVide() {
    return (nb_clŽs == 0);
  }
  
  public boolean tropPlein() {
    return (nb_clŽs == b);
  }
  
  public boolean pasAssezPlein() {
    return (nb_clŽs < a-1);
  }
  
  public arbre_ab fils0() {
    // pour supprimer la racine lorsqu'elle devient vide
    if (fils[0] == null) {
      return this;
    } else {
      return fils[0];
    }
  }
  
  public void lister1() {
    // les couples (clŽ, info) dans l'ordre des clŽs
    if (estVide()) {
      System.out.println("arbre vide");
      return;
    }
    if (fils[0] != null) fils[nb_clŽs].lister1();
    for (int i=nb_clŽs-1; i >= 0; i--) {
      System.out.println("(" + clŽs[i] + "," + infos[i] + ")");
      if (fils[0] != null) fils[i].lister1();
    }
  }
  
  public void lister(String prŽfixe) {
    // liste les couples (clŽ, info) dans l'ordre des clŽs en faisant
    // appara”tre la structure de l'arbre
    if (estVide()) {
      System.out.println("arbre vide");
      return;
    }
    if (fils[0] != null) fils[nb_clŽs].lister(prŽfixe + "   |");
    for (int i=nb_clŽs-1; i >= 0; i--) {
      System.out.println(prŽfixe + "(" + clŽs[i] + "," + infos[i] + ")");
      if (fils[0] != null) fils[i].lister(prŽfixe + "   |");
    }

		/* 
		 * if (fils[0] == null) {
		 *   for (int i=0; i < nb_clŽs; i++) {
		 *     System.out.println(prŽfixe + "(" + clŽs[i] + "," + infos[i] + ")");
		 *   }
		 * } else {
		 *   for (int i=0; i < nb_clŽs; i++) {
		 *     fils[i].lister(prŽfixe + "   |");
		 *     System.out.println(prŽfixe + "(" + clŽs[i] + "," + infos[i] + ")");
		 *   }
		 *   fils[nb_clŽs].lister(prŽfixe + "   |");
		 * }
		 */
  }
  
  public Object chercher(int clŽ) {
    // retourne l'info associŽe ˆ la clŽ ou null si la clŽ n'est pas dans
    // l'arbre.
    clŽs[nb_clŽs] = clŽ;
    int i=0;
    while (clŽ > clŽs[i]) i++;
    if ((clŽ == clŽs[i]) && (i < nb_clŽs)) return infos[i];
    if (fils[i] == null) return null;
    return fils[i].chercher(clŽ);
  }
  
  public Object insŽrer(int clŽ, Object info) {
    // Si un couple (clŽ, oldInfo) existe dŽjˆ dans l'arbre, on remplace
    // oldInfo par info et on retourne oldInfo, sinon on insŽre le couple
    // (clŽ, info) dans l'arbre et on retourne null.
    // 
    // Attention: apr�s l'insertion, la racine de l'arbre peut avoir b clŽs
    // et nŽcessiter un Žquilibrage (Žclatement).
    clŽs[nb_clŽs] = clŽ;
    int i=0;
    while (clŽ > clŽs[i]) i++;
    if ((clŽ == clŽs[i]) && (i < nb_clŽs)) {
      // trouvŽ, on remplace
      Object old_info = infos[i];
      infos[i] = info;
      return old_info;
    }
    if (fils[i] == null) {
      // feuille, on ins�re
      int j=nb_clŽs;
      while (j>i) { // dŽcalage
        clŽs[j] = clŽs[j-1];
        infos[j] = infos[j-1];
        j--;
      }
      clŽs[i] = clŽ;
      infos[i] = info;
      nb_clŽs++;
      return null;
    }
    Object old_info = fils[i].insŽrer(clŽ, info);
    if (fils[i].tropPlein()) Žclater(i);
    return old_info;
  }
  
  private void Žclater(int pos) {
    // Žclatement de fils[pos]
    int j=nb_clŽs;
    while (j>pos) { // dŽcalage
      clŽs[j] = clŽs[j-1];
      infos[j] = infos[j-1];
      fils[j+1] = fils[j];
      j--;
    }
    arbre_ab g = fils[pos];
    clŽs[pos] = g.clŽs[b/2];
    infos[pos] = g.infos[b/2];
    nb_clŽs++;
    arbre_ab d = new arbre_ab();
    fils[pos+1] = d;
    d.nb_clŽs = b - b/2 - 1;
    for (int i=0; i < d.nb_clŽs; i++) {
      d.clŽs[i]  = g.clŽs[b/2 + i + 1];
      d.infos[i] = g.infos[b/2 + i + 1];
      d.fils[i]  = g.fils[b/2 + i + 1];
    }
    d.fils[d.nb_clŽs] = g.fils[b];
    g.nb_clŽs = b/2;
  }
  
  public Object supprimer(int clŽ) {
    // Si un couple (clŽ,info) existe dans l'arbre, on le supprime et on
    // retourne info. Sinon, on retourne null.
    // 
    // Attention: apr�s la suppression, la racine de l'arbre peut ne pas
    // avoir assez de clŽs et nŽcessiter un Žquilibrage (partage ou fusion).
    clŽs[nb_clŽs] = clŽ;
    int i=0;
    while (clŽ > clŽs[i]) i++;
    if ((clŽ == clŽs[i]) && (i < nb_clŽs)) {
      // trouvŽ, il faut supprimer
      if (fils[i] == null) {
        // on est sur une feuille
        Object old_info = infos[i];
        for (int j = i+1; j<nb_clŽs; j++) { // dŽcalage
          clŽs[j-1] = clŽs[j];
          infos[j-1] = infos[j];
        }
        nb_clŽs--;
        return old_info;
      }
      RŽsultat res = fils[i].supprimer_max();
      clŽs[i] = res.clŽ;
      Object old_info = infos[i];
      infos[i] = res.info;
      if (fils[i].pasAssezPlein()) Žquilibrer(i);
      return old_info;
    }
    if (fils[i] == null) {
      // la clŽ n'est pas dans l'arbre
      return null;
    } 
    // suppression dans le sous-arbre
    Object old_info = fils[i].supprimer(clŽ);
    if (fils[i].pasAssezPlein()) Žquilibrer(i);
    return old_info;
  }
  
  private RŽsultat supprimer_max() {
    // supprime le couple (clŽ_max,info_max) de clŽ maximale dans l'arbre.
    // retourne res.clŽ = clŽ_max et res.info = info_max
    // 
    // Attention: apr�s la suppression, la racine de l'arbre peut ne pas
    // avoir assez de clŽs et nŽcessiter un Žquilibrage (partage ou fusion).
    if (fils[0] == null) {
      RŽsultat res = new RŽsultat();
      nb_clŽs--;
      res.clŽ = clŽs[nb_clŽs];
      res.info = infos[nb_clŽs];
      return res;
    }
    RŽsultat res = fils[nb_clŽs].supprimer_max();
    if (fils[nb_clŽs].pasAssezPlein()) Žquilibrer(nb_clŽs);
    return res;
  }
  
  private void Žquilibrer(int i) {
    // fils[i] n'est pas assez plein, il faut le rŽŽquilibrer
    if ((i>0) && (fils[i-1].nb_clŽs >= a)) {
      // partager gauche -> droite
      partagerGD(i-1);
    } else if ((i<nb_clŽs) && (fils[i].nb_clŽs >= a)) {
      // partager droite -> gauche
      partagerDG(i);
    } else if (i>0) {
      fusionner(i-1);
    } else {
      fusionner(i);
    }
  }
  
  private void partagerGD(int pos) {
    // partager gauche -> droite ˆ pos
    arbre_ab g = fils[pos];
    arbre_ab d = fils[pos+1];
    for (int i=d.nb_clŽs; i>0; i--) {
      d.clŽs[i] = d.clŽs[i-1];
      d.infos[i] = d.infos[i-1];
      d.fils[i+1] = d.fils[i];
    }
    d.nb_clŽs++;
    d.clŽs[0] = clŽs[pos];
    d.infos[0] = infos[pos];
    d.fils[0] = g.fils[g.nb_clŽs];
    g.nb_clŽs--;
    clŽs[pos] = g.clŽs[g.nb_clŽs];
    infos[pos] = g.infos[g.nb_clŽs];
  }
  
  private void partagerDG(int pos) {
    // partager droite -> gauche ˆ pos
    arbre_ab g = fils[pos];
    arbre_ab d = fils[pos+1];
    g.clŽs[g.nb_clŽs] = clŽs[pos];
    g.infos[g.nb_clŽs] = infos[pos];
    g.fils[g.nb_clŽs+1] = d.fils[0];
    g.nb_clŽs++;
    clŽs[pos] = g.clŽs[0];
    infos[pos] = g.infos[0];
    for (int i=0; i<d.nb_clŽs; i++) {
      d.clŽs[i] = d.clŽs[i+1];
      d.infos[i] = d.infos[i+1];
      d.fils[i] = d.fils[i+1];
    }
    d.nb_clŽs--;
  }
  
  private void fusionner(int pos) {
    // fusion de fils[pos] et fils[pos+1]
    arbre_ab g = fils[pos];
    arbre_ab d = fils[pos+1];
    g.clŽs[g.nb_clŽs] = clŽs[pos];
    g.infos[g.nb_clŽs] = infos[pos];
    g.fils[g.nb_clŽs+1] = d.fils[0];
    for (int i=g.nb_clŽs+1, j=0; j<d.nb_clŽs; i++, j++) {
      g.clŽs[i] = d.clŽs[j];
      g.infos[i] = d.infos[j];
      g.fils[i+1] = d.fils[j+1];
    }
    g.nb_clŽs += d.nb_clŽs + 1;
    for (int i=pos; i<nb_clŽs; i++) {
      clŽs[i] = clŽs[i+1];
      infos[i] = infos[i+1];
      fils[i+1] = fils[i+2];
    }
    nb_clŽs--;
  }
}