#include <iostream>

using namespace std;

class Skup
{
public:
	virtual bool Dodaj( int n ) = 0;
	virtual bool Sadrzi( int n ) const = 0;
	virtual bool Prazan() const = 0;
	virtual void Isprazni() = 0;

	void Citaj( istream& istr )
		{
		char c;
		istr >> c;
		// preskacemo sav prazan prostor
		istr >> ws;	
		// peek sada vraca prvi neprazan znak u toku
		// ne izdvajajuci ga iz toka
		if( istr.peek() != '}' ) 
			while( istr && c != '}' ){
				int n;
				istr >> n;
				Dodaj(n);
				istr >> c;
				}
		else
			istr >> c;
		}	
		
	void operator += ( const Skup& s )
		{ s.dodajSveElementeSkupu( *this ); }
		
protected:
	virtual void dodajSveElementeSkupu( Skup& s ) const = 0;
};

class Lista
{
public:
	class Element
	{
	public:
		int	Vrednost() const
			{ return _Vrednost;}
			
		const Element* Sledeci() const
			{ return _Sledeci; }
	
	private:
		Element( int v  )
			: _Vrednost(v),
			  _Sledeci(0)
			{}

		Element( int v, Element* s )
			: _Vrednost(v),
			  _Sledeci(s)
			{}
	
		int			_Vrednost;
		Element*	_Sledeci;
			
		friend class Lista;		
	};
	
	Lista()
		: _Pocetak(0),
		  _Kraj(0),
		  _Velicina(0)
		{}
		
	~Lista()
		{ deinit(); }
		
	Lista( const Lista& l )
		{ init( l ); }
		
	Lista& operator = ( const Lista& l )
		{
		if( &l != this ){
			deinit(); 
			init( l ); 
			}
		return *this;
		}
		
	void DodajNaPocetak( int n )
		{ 
		_Pocetak = new Element( n, _Pocetak );
		if( !_Kraj )
			_Kraj = _Pocetak;
		_Velicina++;
		}
		
	void DodajNaKraj( int n )
		{
		Element* novi = new Element( n );
		if( !_Pocetak )
			_Kraj = _Pocetak = novi;
		else{
			_Kraj->_Sledeci = novi;
			_Kraj = novi;
			}
		_Velicina++;
		}
		
	int operator [] ( unsigned n ) const
		{
		const Element* p = _Pocetak;
		for( unsigned i=0; i<n && p; i++ )
			p = p->Sledeci();
		return p ? p->Vrednost() : 0;
		}
		
	const Element* Pocetak() const
		{ return _Pocetak; }
		
	bool Prazna() const
		{ return !_Pocetak; }
		
	unsigned Velicina() const
		{ return _Velicina; }
		
	void ObrisiPrviElement()
		{
		if( _Pocetak ){
			Element* p = _Pocetak->_Sledeci;
			delete _Pocetak;
			_Pocetak = p;
			if( !_Pocetak )
				_Kraj = 0;
			_Velicina--;
			}
		}

	void ObrisiPoslednjiElement()
		{
		if( _Velicina >=2 ){
			Element* p = _Pocetak;
			while( p->Sledeci() != _Kraj )
				p = p->_Sledeci;
			delete p->Sledeci();
			p->_Sledeci = 0;
			_Kraj = p;
			}
		else if( _Velicina == 1 ){
			delete _Pocetak;
			_Pocetak = _Kraj = 0;
			}
		_Velicina--;
		}
		
private:
/*
ovako se moze izbeci pisanje 
konstruktora kopije i operatora dodeljivanja
	Lista( const Lista& l );
	Lista& operator = ( const Lista& l );
*/

	void init( const Lista& l )
		{
		const Element* stari = l._Pocetak;
		Element** novi = &_Pocetak;
		_Kraj = 0;
		while( stari ){
			_Kraj = (*novi) = new Element( stari->Vrednost() );
			stari = stari->Sledeci();
			novi = &_Kraj->_Sledeci;
			}
		*novi = 0;
		_Velicina = l._Velicina;
		}
		
	void deinit()
		{
		for( Element* p = _Pocetak; p; ){
			Element* pl = p->_Sledeci;
			delete p;
			p = pl;
			}
		}

	Element*	_Pocetak;
	Element* 	_Kraj;
	unsigned	_Velicina;
};

class SkupL : public Skup
{
public:
	bool Dodaj( int n )
		{
		if( !Sadrzi(n) ){
			_Elementi.DodajNaKraj(n);
			return true;
			}
		else
			return false;
		}
		
	bool Prazan() const
		{ return _Elementi.Prazna(); }

	bool Sadrzi( int n ) const
		{
		for( const Lista::Element* p=_Elementi.Pocetak(); p; p = p->Sledeci() )
			if( p->Vrednost() == n )
				return true;
		return false;
		}

	void Isprazni() 
		{ 
		_Elementi = Lista(); 
		// prethodni izraz radi isto sto i sledeca sekvenca:
		//	Lista prazna;
		//	_Elementi = prazna;
		}
		
	void dodajSveElementeSkupu( Skup& s ) const
		{
		for( const Lista::Element* p=_Elementi.Pocetak(); p; p = p->Sledeci() )
			s.Dodaj( p->Vrednost() );
		}

private:
	Lista _Elementi;
};

class Drvo
{
public:
	class Element
	{
	public:
		int	Vrednost() const
			{ return _Vrednost;}
			
		const Element* Levi() const
			{ return _Levi; }

		const Element* Desni() const
			{ return _Desni; }
	
	private:
		Element( int v  )
			: _Vrednost(v),
			  _Levi(0),
			  _Desni(0)
			{}

		Element( int v, Element* l, Element* d )
			: _Vrednost(v),
			  _Levi(l),
			  _Desni(d)
			{}
			
		~Element()
			{
			delete _Levi;
			delete _Desni;
			}
		
		Element( const Element& e )
			: _Vrednost( e._Vrednost ),
			  _Levi( e._Levi ? new Element( *e._Levi ) : 0 ),
			  _Desni( e._Desni ? new Element( *e._Desni ) : 0 )
			{}
			
		Element& operator = ( const Element& e )
			{
			if( &e != this ){
				delete _Levi;
				delete _Desni;
				_Vrednost = e._Vrednost;
			  	_Levi = e._Levi ? new Element( *e._Levi ) : 0;
			  	_Desni = e._Desni ? new Element( *e._Desni ) : 0;
				}
			return *this;
			}

		void Dodaj( int n )
			{
			if( n < _Vrednost )
				if( _Levi )
					_Levi->Dodaj(n);
				else
					_Levi = new Element(n);
			else if( n > _Vrednost )
				if( _Desni )
					_Desni->Dodaj(n);
				else
					_Desni = new Element(n);
			}
	
		const Element* Pronadji( int n ) const
			{ 
			if( n == _Vrednost )
				return this;
			else if( n < _Vrednost )
				return _Levi ? _Levi->Pronadji(n) : 0;
			else 
				return _Desni ? _Desni->Pronadji(n) : 0;
			}

		int			_Vrednost;
		Element*	_Levi;
		Element*	_Desni;
			
		friend class Drvo;		
	};
	
	Drvo()
		: _Koren(0)
		{}
		
	void Dodaj( int n )
		{ 
		if( _Koren )
			_Koren->Dodaj(n);
		else
			_Koren = new Element(n);
		}
		
	const Element* Pronadji( int n ) const
		{ return _Koren ? _Koren->Pronadji(n) : 0; }
		
	bool Prazno() const
		{ return !_Koren; }
	
	const Element* Koren() const
		{ return _Koren; }
		
private:
	Element* _Koren;	
};

class SkupD : public Skup
{
public:
	bool Dodaj( int n )
		{
		if( !Sadrzi(n) ){
			_Elementi.Dodaj(n);
			return true;
			}
		else
			return false;
		}
		
	bool Prazan() const
		{ return _Elementi.Prazno(); }

	bool Sadrzi( int n ) const
		{ return _Elementi.Pronadji(n); }

	void Isprazni() 
		{ 
		_Elementi = Drvo(); 
		// prethodni izraz radi isto sto i sledeca sekvenca:
		//	Drvo prazno;
		//	_Elementi = prazno;
		}

	void dodajSveElementeSkupu( Skup& s ) const
		{
		
		const Drvo::Element* p=_Elementi.Koren();
		dodajPoddrvo( p, s );
		}

	// ovaj metod bi mogao da ideu klasu Drvo::Element
	// ali tako bismo svaki element drveta opteretili 
	// ponasanjem koje ne pripada elementu drveta nego skupu
	static void dodajPoddrvo( const Drvo::Element* e, Skup& s )
		{
			if( e ){
				s.Dodaj( e->Vrednost() );
				dodajPoddrvo( e->Levi(), s );
				dodajPoddrvo( e->Desni(), s );
				}
		}

	
private:
	Drvo _Elementi;
};

main()
{
	Skup* s = new SkupL();
	for( int i=0; i<20; i+=2 )
		s->Dodaj(i);
	for( int i=0; i<20; i++ )
		cout 
			<< i 
			<< (s->Sadrzi(i) ? " je" : " nije" ) 
			<< " element skupa." 
			<< endl;

	Skup* s2 = new SkupD();
	s2->Citaj( cin );
	for( int i=0; i<20; i++ )
		cout 
			<< i 
			<< (s2->Sadrzi(i) ? " je" : " nije" ) 
			<< " element skupa." 
			<< endl;
			
	(*s2) += *s;
	for( int i=0; i<20; i++ )
		cout 
			<< i 
			<< (s->Sadrzi(i) ? " je" : " nije" ) 
			<< " element skupa." 
			<< endl;

	delete s;		
	delete s2;
	return 0;	
}

