/************************************************************
 * INFO 2 SS 2001 
 * Musterloesung Aufgabe 3 Blatt2
 * by Janis Fehr
 ************************************************************
*/


import java.io.InputStreamReader; //import der Funktionen 
import java.io.BufferedReader;


public class listsort  {    
    private doppelliste liste = new doppelliste();  //lege neue Liste vom Datentyp Doppelliste an

    public class listenellement {                  //Deffinition des Datentyps listenellement
	listenellement pred=null;                  //Zeiger auf Vorgaenger
	listenellement succ=null;                  //Zeiger auf Nachfolger
	String data;                               //hier werden die Daten abgelegt
	listenellement(String data){
	    this.data = data;
	}
    }

    private class doppelliste {                    //lege meine Liste an 
	private listenellement cur ;               //cur zeigt auf da aktuelle Element
	
	Object pred() {                            //gibt Wert des Vorgaengers aus und
	    if (cur == null)                       //setzt den Zeiger darauf  
		return null;
	    if (cur.pred != null)
		cur = cur.pred;
	    return cur.data;
	}
	
	Object succ() {                            //gibt Wert des Nachfolgers aus und
	    if (cur == null)                       //setzt den Zeiger darauf
		return null;
	    if (cur.succ != null)
		cur = cur.succ;
	    return cur.data;
	}
	
	Object first() {                           //springt zum Anfang der Liste
	    if (cur == null)
		return null;
	    while (cur.pred != null){
		cur = cur.pred;
	    }
	    return cur.data;
	}

	Object last() {                            //springt zum Ende der Liste
	    if (cur == null)
		return null;
	    while (cur.succ != null){
		cur = cur.succ;
	    }
	    return cur.data;
	}

	

	boolean begin() {                          //ist das Element das Erste ?
	    if (cur == null)
		return true;
	    return (cur.pred == null);
	}

	boolean end() {                            //ist das Element das Letzte ?
	    if (cur == null)
		return true;
	    return (cur.succ == null);
	}


    

	void insert(String element){                       //Einfuegen eines neuen Elements
	listenellement e = new listenellement(element);    //erzeuge neues Element
	if (cur == null) {                                 //ist die Liste leer -> fuege ein 
	    cur = e;
	    return;
	}
	
	boolean fertig = false;                            //ist das neue Element eingefuegt ? 
	while (!fertig) {

	    if (e.data.compareTo(cur.data)>0) {            //ist das neue Element groesser als das 
		if (cur.succ != null){                     //aktuelle und gibt es ein weiteres ?
		    cur=cur.succ;                          //JA : gehe eins weiter
		}else {                                   
		    cur.succ = e;                          //NEIN : fuege Element hinten an
		    e.pred = cur;
		    fertig = true;
		}
	    }else if (cur.pred == null){                   //Element ist kleiner und es gibt
		cur.pred=e;                                //kein Element davor -> fuege vorn an
		 e.succ = cur;
		 fertig = true;
	    }else if (e.data.compareTo(cur.pred.data)<0){  //Element ist kleiner
		cur=cur.pred;                              //geh eins vor
	    }else {                                        //oder feuge zwischen die Elemente ein
	         cur.pred.succ = e;
	         e.pred = cur.pred;
	         e.succ = cur;
	         cur.pred = e;
		 fertig = true;
	   }
	}
	}

    }

    public  void useit() {                                 //Eingabe-Ausgabe
	try {
	    BufferedReader eingabe = new BufferedReader(new InputStreamReader(System.in));
	    String in = eingabe.readLine();
	    while (!in.equals("")) {                       //lese Strings von der Eingabe
		liste.insert(in);                          //bis Leerzeile und schreibe in
		in = eingabe.readLine();                   //die Liste
	     }
	    eingabe.close();
	} catch (Exception ex) {                           //Fehlerbehandlung der Eingabe
	     System.exit(1);
	}
	
	
	System.out.println("aufsteigende Liste :");
	System.out.println(liste.first());                 //gebe erstes Element aus
	do {
	     System.out.println(liste.succ());
	}while (!liste.end());
	       
	System.out.println("absteigende Liste :");
	System.out.println(liste.last());                  //gebe letztes Element aus
	do {
	     System.out.println(liste.pred());
	}while (!liste.begin());
	

    }



    public static void main(String[] args){         
	listsort test = new listsort();             
	test.useit();
    }


}