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


//構造体の定義。
struct c_list {
	char ch; //格納文字。
	struct c_list *pnext; //次のデータのポインタ。
};


//プロトタイプ宣言。
void addhead(struct c_list newlist);
void addtail(struct c_list newlist);
void removeall();
struct c_list removetail();
struct c_list removehead();
struct c_list getat(int n);
void setat(int n, struct c_list newdata);
void removeat(int n);
int getcount();
int empty();
void insertafter(int n, struct c_list newdata);
void insertbefore(int n, struct c_list newdata);
int finddata(struct c_list data);
struct c_list getnext();
void getheadposition();


//リストの最初と最後のデータのポインタ。
struct c_list *pstart, *pend;
struct c_list *ptr;


//メイン関数。
int main(void) {
	struct c_list data;
	char ch;

	//リスト作成。
	ch = getche();
	while( isalpha(ch) ) {
		data.ch = ch;
		addtail(data);
		ch = getche();
	}

	//改行。
	printf("\n");

	//リスト表示。
	getheadposition();
	do {
		data = getnext();
		if( data.ch ) {
			putch(data.ch);
		}
	} while( data.ch );

	printf("\n");

	//確保した領域を開放する。
	removeall();

	return 0;
}


//リストの最後に追加。
void addtail(struct c_list newlist) {
	struct c_list *ptr;

	//メモリー確保。
	ptr = (struct c_list*)malloc(sizeof(struct c_list));

	//現在の最後のデータにアドレス格納。
	if( pend ) {
		pend->pnext = ptr;
	} else {
		pstart = ptr;
	}
	pend = ptr;

	//データをコピー。
	*pend = newlist;

	//追加したデータの次のポインタをNULLにする。
	pend->pnext = NULL;
}


//リストの最初に追加。
void addhead(struct c_list newlist) {
	struct c_list *ptr;

	//メモリー確保。
	ptr = (struct c_list*)malloc(sizeof(struct c_list));

	//データをコピー。
	*ptr = newlist;

	//追加するデータの次のポインタを、現在の最初のデータにする。
	ptr->pnext = pstart;

	//最初のデータを、今追加したデータに置き換える。
	pstart = ptr;
}


//全てのデータを解放する。
void removeall(void) {
	struct c_list *p, *pnext;

	//1つずつ削除していく。
	for( p = pstart; p; p = pnext ) {
		pnext = p->pnext;
		free(p);
	}

	//リストの開始、終了位置をNULLにする。
	pend = pstart = NULL;
}


//最初のデータを削除する。
//返り値として、最初のデータを返す。
struct c_list removehead(void) {
	struct c_list ret;

	//構造体の中身をNULLで初期化する。
	ret.ch = '\0';

	//リストの要素が空でなければ。
	if( pstart ) {

		//最初のデータ取得。
		ret = *pstart;

		//最初のデータを解放する。
		free(pstart);

		//最初のデータを次のデータに置き換える。
		pstart = ret.pnext;

		//空になったらpendも修正。
		if( !pstart ) {
			pend = NULL;
		}
	}

	ret.pnext = NULL;

	return ret;
}


//最後のデータを削除する。
//返り値として、最後のデータを返す。
struct c_list removetail(void) {
	struct c_list ret;

	//返り値用構造体をNULLで初期化する。
	ret.ch = '\0';

	//リストの要素が空でなければ。
	if( pend ) {
		struct c_list *ptr;

		//最後のデータ取得。
		ret = *pend;

		//最後から2番目のpnextを変更する。
		for( ptr = pstart; ptr; ptr = ptr->pnext ) {
			
			//最後から2番目のデータなら。
			if( ptr->pnext == pend ) {
				//pnextをNULLに変更。
				ptr->pnext = NULL;
			}
		}

			//最後のデータを解放する。
			free(pend);

			//最後のデータを、その前のデータに置き換える。
			pend = ptr;

			//空になったらpstartも書き換える。
			if( !pend ) {
				pstart = NULL;
			}
	}

		ret.pnext = NULL;

		return ret;
}


//n番目のデータを返す。
struct c_list getat(int n) {
	struct c_list *ptr;
	struct c_list ret;

	//返り値用データをNULLで初期化する。
	ret.ch = '\0';
	ret.pnext = NULL;

	//nがマイナスはありえない。
	if( n < 0 ) {
		return ret;
	}

	//n番目の要素を返す。
	for( ptr = pstart; ptr; ptr = ptr->pnext ) {
		if( n-- == 0 ) {
			return *ptr;
		}
	}

	//n番目の要素がない場合。
	return ret;
}


//n番目の要素を置き換える。
void setat(int n, struct c_list newdata) {
	struct c_list *ptr;
	struct c_list *pnext;

	//nがマイナスはありえない。
	if( n < 0 ) {
		return;
	}

	for( ptr = pstart; ptr; ptr = ptr->pnext ) {
		if( n-- == 0 ) {
			pnext = ptr->pnext;
			*ptr = newdata;
			ptr->pnext = pnext;
			return;
		}
	}
}


//n番目の要素を削除する。
void removeat(int n) {
	struct c_list *ptr, *ppre;

	//nがマイナスはありえない。
	if( n < 0 ) {
		return;
	}

	//0番目だったら、removeheadを呼び出して帰る。
	if( n == 0 ) {
		removehead();
		return;
	}

	//リストが空だったら。
	if( !pstart ) {
		return;
	}

	//準備。
	ppre = pstart;
	ptr = pstart->pnext;
	n--;

	while( ptr ) {
		//削除。
		if( n-- == 0 ) {
			//リストのつなぎ換え。
			ppre->pnext = ptr->pnext;

			//n番目のリストを解放する。
			free(ptr);

			return;
		}

		ppre = ptr;
		ptr = ptr->pnext;
	}

	//n番目をない場合はここに来る。
}


//リストの要素数を返す。
int getcount(void) {
	struct c_list *ptr;
	int n = 0;

	//空でない場合。
	if( pstart ) {
		for( ptr = pstart; ptr; ptr = ptr->pnext ) {
			n++;
		}
	}

	return n;
}


//リストが空かどうかを調べる。
//返り値：0　---> 空ではない。
//　　　：0以外-> 空である。
int empty(void) {
	return pstart ? 0 : 1;
}


//n番目の次に要素を追加する。
void insertafter(int n, struct c_list newdata) {
	struct c_list *ptr, *pnew;

	//nがマイナスはありえない。
	if( n < 0 ) {
		return;
	}

	for( ptr = pstart; ptr; ptr = ptr->pnext ) {
		//指定要素なら。
		if( n-- == 0 ) {
			//メモリ確保。
			pnew = (struct c_list*)malloc(sizeof(struct c_list));

			//新しく確保したメモリにデータをコピーする。
			*pnew = newdata;

			//リストのつなぎ換え。
			pnew->pnext = ptr->pnext;
			ptr->pnext = pnew;

			return;
		}
	}
	//n番目のデータがなければここに来る。
}


//n番目の前に要素を追加する。
void insertbefore(int n, struct c_list newdata) {
	struct c_list *ptr, *pnew;

	//nがマイナスはありえない。
	if( n < 0 ) {
		return;
	}

	//最初に追加するなら、addheadを読んで帰る。
	if( n == 0 ) {
		addhead(newdata);
		return;
	}

	for( ptr = pstart; ptr; ptr = ptr->pnext ) {
		//指定要素なら。
		if( --n == 0 ) {
			//メモリ確保。
			pnew = (struct c_list*)malloc(sizeof(struct c_list));

			//新しく確保したメモリにデータをコピーする。
			*pnew = newdata;

			//リストのつなぎ換え。
			*pnew = newdata;

			//リストのつなぎ換え。
			pnew->pnext = ptr->pnext;
			ptr->pnext = pnew;

			return;
		}
	}

	//n番目のデータがなければここに来る。
}


//要素を探し出す。
//見つからなければ-1を返す。
int finddata(struct c_list data) {
	struct c_list *ptr;
	int i = 0;

	for( ptr = pstart; ptr; ptr->pnext ) {
		//見つかったら。
		if( data.ch == ptr->ch ) {
			return i;
		}
		i++;
	}

	//見つからなかったら。
	return -1;
}


//順次アクセス。
//現在のデータをptrで保存しておき、この関数が呼ばれるたびに次のデータを返すようにする。
struct c_list getnext(void) {
	struct c_list ret;

	//初期化。
	ret.ch = '\0';

	if( ptr ) {
		ret = *ptr;
		ptr = ptr->pnext;
	}
	ret.pnext = NULL;

	return ret;
}


//順次アクセス。
//現在のデータをpstartにし、次回のgetnextで最初のデータを返すように初期化する。
void getheadposition(void) {
	ptr = pstart;
}