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


struct Vagonik  {
	char Znak;
	struct Vagonik *Sipka;
};


struct Vagonik * VytvorNovyVagonik(char Znak) {
	
	struct Vagonik *Pomocny=(struct Vagonik*)malloc(sizeof(struct Vagonik));
	
	if(Pomocny==NULL) {
		printf("Problemy pri alokovani pamate");
		exit(-1);
	}
	Pomocny->Znak=Znak; Pomocny->Sipka=NULL;
	return Pomocny;
}


void Zrus(struct Vagonik * Zaciatok) {

	while(Zaciatok!=NULL) {
		struct Vagonik *NasledujuciVagonik;
		NasledujuciVagonik=Zaciatok->Sipka;
		free(Zaciatok);
		Zaciatok=NasledujuciVagonik;
	}
}



void VypisZoznam(struct Vagonik * Zaciatok) {

	struct Vagonik *Ukazovatel=Zaciatok;
	
	while(Ukazovatel!=NULL) {
		printf("%c",Ukazovatel->Znak);
		Ukazovatel=Ukazovatel->Sipka;
	}
	printf("\n");
}



struct Vagonik * Pridaj(struct Vagonik *Zaciatok,char Znak) {

	struct Vagonik *Pomocny;
	struct Vagonik *Kde=Zaciatok;
	struct Vagonik *PredKde=NULL;

	while((Kde!=NULL)&&(Kde->Znak<Znak)) {
		//Existuje uz?
		PredKde=Kde; 
		Kde=Kde->Sipka;
	}

	if ((Kde!=NULL)&&(Kde->Znak==Znak))
		return Zaciatok; //Znak uz existuje.

	if(Kde==Zaciatok) {
		//Pridavame na zaciatok.
		Pomocny=VytvorNovyVagonik(Znak);
		Pomocny->Sipka=Zaciatok; Zaciatok=Pomocny;
	} else {
		//vlozenie za prvok PredKde->Sipka
		Pomocny=VytvorNovyVagonik(Znak);
		Pomocny->Sipka=Kde; PredKde->Sipka=Pomocny;
	}

	return Zaciatok;
}



void main(void) {

	int Znak;
	struct Vagonik *Zaciatok=NULL;

	while((Znak=getchar()) != EOF)

		Zaciatok=Pridaj(Zaciatok,Znak);

	VypisZoznam(Zaciatok);

	Zrus(Zaciatok);
}