template <class T>
struct elem_link1
{	T inf;
	elem_link1 *link;
};

template <class T>
class LList
{	public:
		LList();									//konstruktor
		~LList();									//destruktor
		LList(LList const&);						//copy-konstruktor
		LList& operator=(LList const &);			//predifiniran operator =
		bool operator<(LList &);					//predefiniran operator <
		bool operator>(LList &);					//predefiniran operator >
		void print();								//izvejdane na spisuk na ekrana
		void IterStart(elem_link1<T>* = NULL);		//ukazva Current kum nachaloto
		elem_link1<T>* Iter();						//premestva iteratora vuv sledvashta poziciq
		void ToEnd(T const &);						//vkliuchva element v kraq na spisuka
		void ToStart(T const &);
		void InsertAfter(elem_link1<T>*,T const &);	//vkliuchvane na element sled ukazan element
		void InsertBefore(elem_link1<T>*,T const &);//vkliuchvane na element predi ukazan element
		int DeleteAfter(elem_link1<T>*,T &);		//iztrivane na element sled ukazan element
		int DeleteBefore(elem_link1<T>*,T &);		//iztrivane na element predi ukazan element
		void DeleteElem(elem_link1<T>*,T &);		//iztrivane na element
		int len();									//duljina na spisuk
		void concat(LList const &);					//konkatenaciq na neqvniq spisuk s ukazaniq kato parametur
		void reverse();								//obrushta spisuka naopaki
		LList<T> mergelists(LList<T>, LList<T>);	//slivane na sortirani spisuci
		void OddToEven();							//puvo nechetnite, posle chetnite v obraten red
		T GetEndInf();								//vrushta inf chastta na End
		T GetStartInf();							//vrushta inf chastta na Start
		bool empty();								//proverka dali e prazen spisuka
		bool member(T);								//proverka dali daden element e chast ot spisuka
		void DeleteLast();							//iztriva posledniq element v spisuk
		LList<T> Is_Longer_Than(LList<T> &);		//vrushta po-dulgiq ot *this i daden spisuk
		LList<T> Is_Shorter_Than(LList<T> &);		//vrushta po-kusiq ot *this i daden spisuk
		LList<T> Intersection(LList<T> &);			//vrushta sechenieto na tekushtiq spisuk s daden
		LList<T> Union(LList<T> &);					//vrushta obedinenieto na tekushtiq spisuk s daden
	private:
		elem_link1<T> *Start;						//ukazatel kum nachaloto
		elem_link1<T> *End;							//ukazatel kum kraq
		elem_link1<T> *Current;						//ukazatel kum tekusht element
		void DeleteList();
		void CopyList(LList<T> const &);
};

template <class T>			//iztrivane na spisuk
void LList<T>::DeleteList()
{	
	elem_link1<T> *p;
	
	while (Start)
	{	
		p=Start; 
		Start=Start->link;
		delete p;
	}
	End=NULL;
}

template <class T>			//kopirane na spisuk
void LList<T>::CopyList(LList<T> const & r)
{	
	Start=End=NULL;
	if (r.Start)
	{	
		elem_link1<T> *p = r.Start;
		while (p)
		{	
			ToEnd(p->inf);
			p=p->link;
		}
	}
}

template <class T>			//G4
LList<T>::LList()
{	
	Start=NULL;
	End=NULL;
}

template <class T>			//G4
LList<T>::~LList()
{	
	DeleteList();
}

template <class T>			//G4
LList<T>::LList(LList<T> const& r)
{	
	CopyList(r);
}

template <class T>			//G4
LList<T>& LList<T>::operator=(LList<T> const & r)
{	
	if (this!=&r)
	{	
		DeleteList();
		CopyList(r);
	}
	return *this;
}

template <class T>			//predefiniran operator <
bool LList<T>::operator<(LList<T> &r)
{
	return this->len()<r.len()?true:false;
}

template <class T>			//predefiniran operator >
bool LList<T>::operator>(LList<T> &r)
{
	return this->len()>r.len()?true:false;
}

template <class T>			//izvejdane na spisuk na ekrana
void LList<T>::print()
{	
	elem_link1<T> *p = Start;
	while (p)
	{	
		cout<<p->inf<<" ";
		p=p->link;
	}
	cout<<endl;
}

template <class T>			//ukazva Current kum nachaloto
void LList<T>::IterStart(elem_link1<T> *p)
{	
	if (p)
		Current=p;
	else
		Current=Start;
}

template <class T>			//premestva iteratora vuv sledvashta poziciq
elem_link1<T>* LList<T>::Iter()
{	
	elem_link1<T> *p=Current;
	if (Current)
		Current=Current->link;
	return p;
}

template <class T>			//vkliuchva element v kraq na spisuka
void LList<T>::ToEnd(T const & x)
{	
	Current=End;
	End = new elem_link1<T>;
	End->inf=x;
	End->link=NULL;
	if (Current)
		Current->link=End;
	else Start=End;
}

template <class T>			//vkliuchvane na element sled ukazan element
void LList<T>::InsertAfter(elem_link1<T> *p,T const & x)
{	
	elem_link1<T> *q = new elem_link1<T>;
	q->inf=x;
	q->link=p->link;
	if (p==End)
		End=q;
	p->link=q;
}

template <class T>			//vkliuchvane na element predi ukazan element
void LList<T>::InsertBefore(elem_link1<T> *p,T const& x)
{	
	elem_link1<T> *q = new elem_link1<T>;
	*q=*p;
	if (p==End)
		End=q;
	p->inf=x;
	p->link=q;
}

template <class T>			//iztrivane na element sled ukazan element
int LList<T>::DeleteAfter(elem_link1<T> *p,T & x)
{	
	if(p->link)
	{	
		elem_link1<T> *q=p->link;
		x=q->inf;
		p->link=q->link;
		if (q==End)
			End=p;
		delete q;
		return 1;
	}
	else return 0;
}

template <class T>			//iztrivane na element
void LList<T>::DeleteElem(elem_link1<T> *p, T & x)
{	
	if (p==Start)
	{	
		x=p->inf;
		if(Start==End)
		{	Start=End=NULL;
		}
		else Start=Start->link;
		
		delete p;
	}
	else
	{	
		elem_link1<T> *q=Start;
		while (q->link!=p)
			q=q->link;
		DeleteAfter(q, x);
	}
}

template <class T>			//iztrivane na element predi ukazan element
int LList<T>::DeleteBefore(elem_link1<T> *p, T & x)
{	
	if (p!=Start)
	{	
		elem_link1<T> *q=Start;
		while (q->link!=p)
			q=q->link;
		DeleteElem(q, x);
		return 1;
	}
	else return 0;
}

template <class T>			//duljina na spisuk
int LList<T>::len()
{	
	int n=0;
	IterStart();
	elem_link1<T> *p=Iter();
	
	while (p)
	{	
		n++;
		p=Iter();
	}
	return n;
}

template <class T>			//konkatenaciq na neqvniq spisuk s ukazaniq kato parametur	
void LList<T>::concat(LList<T> const & L)
{	
	elem_link1<T> *p=L.Start;
	
	while (p)
	{	
		ToEnd(p->inf);
		p=p->link;
	}
}

template <class T>			//obrushta spisuka naopaki
void LList<T>::reverse()
{	
	elem_link1<T> *p; 
	elem_link1<T> *q; 
	elem_link1<T> *temp;
	p=Start; 
	
	if (p)
	{	
		q=NULL;
		temp=Start;
		Start=End;
		End=temp;
		
		while (p!=Start)
		{	
			temp=p->link;
			p->link=q;
			q=p;
			p=temp;
		}
		
		p->link=q;
	}
}

template <class T>			//sortirane na spisuk
void sortlist(LList<T> & l)
{	
	element<T> *mp;
	element<T> *p;
	l.IterStart();
	p=l.Iter();
	
	while (p->link)
	{	
		T min=p->inf;
		mp=p;
		elem_link1<T> *q=p->link;
		while (q)
		{	
			if (q->inf<=min)
			{	
				mp=q;
				min=q->inf;
			}
			
			q=q->link;
		}
		
		min=mp->inf; 
		mp->inf=p->inf;
		p->inf=min;
		p=p->link;
	}
}

template <class T>			//slivane na sortirani spisuci
LList<T> mergelists(LList<T> l1, LList<T> l2)
{	
	LList<T> l;
	l1.IterStart();
	l2.IterStart();
	elem_link1<T> *p=l1.Iter();
	elem_link1<T> *q=l2.Iter();
	
	while (p && q)
		if (p->inf<=q->inf)
		{	
			l.ToEnd(p->inf);
			p=l1.Iter();
		}
		else
		{	
			l.ToEnd(q->inf);
			q=l2.Iter();
		}
	if (q)
		while(q)
		{	
			l.ToEnd(q->inf);
			q=l2.Iter();
		}
		else while(p)
		{	
			l.ToEnd(p->inf);
			p=l1.Iter();
		}
	return l;
}

template <class T>			//vrushta inf chastta na End
T LList<T>::GetEndInf()
{	
	return this->End->inf;
}

template <class T>			//vrushta inf chastta na Start
T LList<T>::GetStartInf()
{	
	return this->Start->inf;
}

template <class T>			//proverka dali e prazen spisuka
bool LList<T>::empty()
{	
	if (Start==NULL)
		return true;
	else
		return false;
}

template <class T>			//proverqva dali daden element e ot spisuka
bool LList<T>::member(T x)
{
	IterStart();
	elem_link1<T> *p = Iter();

	while (p)
	{
		if (p->inf == x)
			return true;
		p = p->link;
	}
	return false;
}

template <class T>			//iztriva posledniq element v spisuk
void LList<T>::DeleteLast()
{
	if (empty())
		return;

	int x;
	IterStart();
	elem_link1<T> *p = Iter();

	while (p->link)
		p = p->link;
	DeleteElem(p,x);
}

template <class T>			//vrushta po-kusiq ot *this i daden spisuk
LList<T> LList<T>::Is_Shorter_Than(LList<T> &L1)
{
	return *this<L1?*this:L1;
}

template <class T>			//vrushta po-dulgiq ot *this i daden spisuk
LList<T> LList<T>::Is_Longer_Than(LList<T> &L1)
{
	return *this>L1?*this:L1;
}

template <class T>			//vrushta sechenieto na tekushtiq spisuk s daden
LList<T> LList<T>::Intersection(LList<T> &L)
{
	LList<T> Result;
	IterStart();
	elem_link1<T> *p = Iter();
	L.IterStart();
	elem_link1<T> *q = L.Iter();

	while (p)
	{
		while (q)
		{
			if (p->inf == q->inf)
				Result.ToEnd(p->inf);
			q = q->inf;
		}
		p = p->inf;
	}
	return Result;
}

template <class T>			//vrushta obedinenieto na tekushtiq spisuk s daden
LList<T> LList<T>::Union(LList<T> &L)
{
	LList<T> Result;
	IterStart();
	elem_link1<T> *p = Iter();
	L.IterStart();
	elem_link1<T> *q = L.Iter();

	while (p)
	{
		while (q)
		{
			if (p->inf != q->inf)
				Result.ToEnd(p->inf);
			q = q->inf;
		}
		p = p->inf;
	}
	return Result;
}

template <class T>
void LList<T>::ToStart(T const & x)
{
	if (empty())
		ToEnd(x);
	else
	{
		Current = Start;
		Start = new elem_link1<T>;
		Start->inf = x;
		Start->link = Current;
	}
}