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

typedef struct clan_struct
{
   struct clan_struct* prosli;
   char* string;
   struct clan_struct* sledeci;		 		
} Clan;

void Odstampaj(Clan* lista)
{
 	Clan* trenutni = lista; 
    while(trenutni != NULL)
    {
	    printf("%s\t", trenutni->string);
	    trenutni = trenutni->sledeci; 	 
    }
    putchar('\n');
}

void OdstampajUnazad(Clan* lista)
{
 	Clan* trenutni = lista; 
    while(trenutni->sledeci != NULL)
	    trenutni = trenutni->sledeci;
	while(trenutni != NULL)
    {
	    printf("%s\t", trenutni->string);
	    trenutni = trenutni->prosli; 	 
    } 	 
    putchar('\n');
}

Clan* DodajUListu(Clan* lista, char* s)
{
     if(lista == NULL)
     {
	  	  lista = (Clan*) malloc (sizeof(Clan));	  
	      lista->string = (char*) malloc(sizeof(char) * strlen(s));
	      strcpy(lista->string, s);
	      
		  lista->sledeci = NULL;
		  lista->prosli = NULL; 		  
     }
     else
     {
     	Clan* trenutni = lista;  
	 	while(trenutni->sledeci != NULL)
	 		trenutni = trenutni->sledeci;
	 	
	 	Clan* novi = (Clan*) malloc(sizeof(Clan));
	 	novi->string = (char*) malloc(sizeof(char) * strlen(s));
	    
		strcpy(novi->string, s);  
	 	trenutni->sledeci = novi;
	 	novi->sledeci = NULL;
	 	novi->prosli = trenutni;
	}
	return lista;
}

Clan* DodajUSortListu(Clan* lista, char* s)
{
     if(lista == NULL)
     {
	  	  lista = (Clan*) malloc (sizeof(Clan));	  
	      lista->string = (char*) malloc(sizeof(char) * strlen(s));
	      strcpy(lista->string, s);
	      
		  lista->sledeci = NULL;
		  lista->prosli = NULL; 	
     }
     else
     {
     	Clan* trenutni = lista;  
	 	while(strcmp(trenutni->string, s) < 0 && trenutni->sledeci != NULL)
	 		trenutni = trenutni->sledeci;
		
	 	Clan* novi = (Clan*) malloc(sizeof(Clan));
	 	novi->string = (char*) malloc(sizeof(char) * strlen(s));   
		strcpy(novi->string, s);  
		if(trenutni == lista && strcmp(trenutni->string, s) > 0)
	 	{ //na prvo mjesto
			novi->prosli = NULL;
			novi->sledeci = trenutni;
			trenutni->prosli = novi;
			lista = novi;
		}
		else if(trenutni->sledeci == NULL && strcmp(trenutni->string, s) < 0)
		{ //na poslednje mjesto
			novi->prosli = trenutni;
			novi->sledeci = NULL;
			trenutni->sledeci = novi;
		}
		else
		{ // negdje u sredini...
	 		novi->sledeci = trenutni;
	 		novi->prosli = trenutni->prosli;
	 	 	trenutni->prosli = novi;
			novi->prosli->sledeci = novi;
		}
	}
	return lista;	
}

void DealocirajMemoriju(Clan* lista)
{	
	Clan* pom;
	while(lista != NULL)
	{
		pom = lista;
		while(pom->sledeci != NULL)
			pom = pom->sledeci;
		
		if(pom->prosli == NULL)
			lista = NULL;
		else
			pom->prosli->sledeci = NULL;
		free(pom->string);
		free(pom);
	}
}

int main()
{
 	Clan* lista = NULL;
	Clan* sortLista = NULL;
    
 	int i;
 	char string[10];
 	for(i=0; i<5; i++)
 	{
	    scanf("%s", &string);
		lista = DodajUListu(lista, string);
		sortLista = DodajUSortListu(sortLista, string);
    }    
    
    Odstampaj(lista);	
    OdstampajUnazad(lista);	
    
	Odstampaj(sortLista);
	OdstampajUnazad(sortLista);
    
	DealocirajMemoriju(lista); 		 
    	 		 
    system("PAUSE");	
    return 0;
}