#include <numeric>
#include <set>

using std::set;

template<typename T>
class cart_prod { 

public:
  set<set<T> > operator()( const set<set<T> >& ss, const set<T>& s )
  {  
    set<set<T> > res;
    if( ss.empty() )
      for( typename set<T>::const_iterator it = s.begin();
	   it != s.end(); it++ )
	{
	  set<T> tmp;
	  tmp.insert( *it );
	  res.insert( tmp );
	}	
    else
      for( typename set<T>::const_iterator it = s.begin();
	   it != s.end(); it++ )
	for( typename set<set<T> >::const_iterator it2 = ss.begin();
	     it2 != ss.end(); it2++ )
	  {
	    set<T> tmp( *it2 );
	    tmp.insert( *it );
	    res.insert( tmp );
	  }	
    return res;
} };

template<typename T>
set<set<T > >
cartesian( const set<set<T> >& sets, const set<set<T> >& init )
{
  return std::accumulate( sets.begin(), sets.end(), init, cart_prod<T>());
}

template<typename T>
set<set<T > >
cartesian( const set<set<T> >& sets )
{
  set<set<T> > init;
  return std::accumulate( sets.begin(), sets.end(), init, cart_prod<T>());
}


// The same, but with a predicate

template<typename T, typename _Predicate>
class cart_prod_p { 
protected:
  _Predicate pred;
public:
  explicit  
  cart_prod_p(const _Predicate& __p) : pred(__p) 
  {}
  
  set<set<T> > operator()( const set<set<T> >& ss, const set<T>& s )
  {  
    set<set<T> > res;
    if( ss.empty() )
      for( typename set<T>::const_iterator it = s.begin();
	   it != s.end(); it++ )
	{
	  if( pred(*it) )
	    {
	      set<T> tmp;
	      tmp.insert( *it );
	      res.insert( tmp );
	    }	
	}
    else
      {
	bool one = false;
	for( typename set<T>::const_iterator it = s.begin();
	     it != s.end(); it++ )
	  if( pred(*it) )
	    {
	      for( typename set<set<T> >::const_iterator it2 = ss.begin();
		   it2 != ss.end(); it2++ )
	      {
		set<T> tmp( *it2 );
		tmp.insert( *it );
		res.insert( tmp );
		one = true;
	      }	
	    }
	if(!one)
	  res = ss;
      }
    return res;
} };


template<typename _Predicate, typename T>
set<set<T > >
cartesian_p( const set<set<T> >& sets, const set<set<T> >& init, _Predicate p )
{
  return std::accumulate( sets.begin(), sets.end(), init, cart_prod_p<T,_Predicate>(p));
}

template<typename _Predicate, typename T>
set<set<T > >
cartesian_p( const set<set<T> >& sets, _Predicate p )
{
  set<set<T> > init;
  return std::accumulate( sets.begin(), sets.end(), init, cart_prod_p<T,_Predicate>(p));
}

// The same, but with a predicate
// also allow to reject an element to be included in a set

template<typename T, typename _Predicate, typename _Reject_elem>
class cart_prod_p_r { 
protected:
  _Predicate pred;
  _Reject_elem reject;
public:
  explicit  
  cart_prod_p_r(const _Predicate& __p, const _Reject_elem& __r) : pred(__p), reject(__r)
  {}
  
  set<set<T> > operator()( const set<set<T> >& ss, const set<T>& s )
  {  
    set<set<T> > res;
    if( ss.empty() )
      for( typename set<T>::const_iterator it = s.begin();
	   it != s.end(); it++ )
	{
	  if( pred(*it) )
	    {
	      set<T> tmp;
	      tmp.insert( *it );
	      res.insert( tmp );
	    }	
	}
    else
      {
	bool one = false;
	for( typename set<T>::const_iterator it = s.begin();
	     it != s.end(); it++ )
	  if( pred(*it) )
	    {
	      for( typename set<set<T> >::const_iterator it2 = ss.begin();
		   it2 != ss.end(); it2++ )
	      {
		set<T> tmp( *it2 );
		if( reject(tmp, *it) ) continue;
		tmp.insert( *it );
		res.insert( tmp );
		one = true;
	      }	
	    }
	if(!one)
	  res = ss;
      }
    return res;
} };


template<typename _Predicate, typename _Reject_elem, typename T>
set<set<T > >
cartesian_p_r( const set<set<T> >& sets, const set<set<T> >& init, _Predicate p, _Reject_elem r )
{
  return std::accumulate( sets.begin(), sets.end(), init, 
			  cart_prod_p_r<T,_Predicate,_Reject_elem>(p,r));
}

template<typename _Predicate, typename _Reject_elem, typename T>
set<set<T > >
cartesian_p_r( const set<set<T> >& sets, _Predicate p, _Reject_elem r )
{
  set<set<T> > init;
  return std::accumulate( sets.begin(), sets.end(), init, 
			  cart_prod_p_r<T,_Predicate,_Reject_elem>(p,r));
}


// The same, but 
// only allow to reject an element to be included in a set

template<typename T, typename _Reject_elem>
class cart_prod_r { 
protected:
  _Reject_elem reject;
public:
  explicit  
  cart_prod_r(const _Reject_elem& __r) : reject(__r)
  {}
  
  set<set<T> > operator()( const set<set<T> >& ss, const set<T>& s )
  {  
    set<set<T> > res;
    if( ss.empty() )
      for( typename set<T>::const_iterator it = s.begin();
	   it != s.end(); it++ )
	{
	  set<T> tmp;
	  tmp.insert( *it );
	  res.insert( tmp );
	}
    else
      {
	bool one = false;
	for( typename set<T>::const_iterator it = s.begin();
	     it != s.end(); it++ )
	  for( typename set<set<T> >::const_iterator it2 = ss.begin();
	       it2 != ss.end(); it2++ )
	    {
	      set<T> tmp( *it2 );
	      if( reject(tmp, *it) ) continue;
	      tmp.insert( *it );
	      res.insert( tmp );
	      one = true;
	    }	
	if(!one)
	  res = ss;
      }
    return res;
} };


template<typename _Reject_elem, typename T>
set<set<T > >
cartesian_r( const set<set<T> >& sets, const set<set<T> >& init, _Reject_elem r )
{
  return std::accumulate( sets.begin(), sets.end(), init, 
			  cart_prod_r<T,_Reject_elem>(r));
}

template<typename _Reject_elem, typename T>
set<set<T > >
cartesian_r( const set<set<T> >& sets, _Reject_elem r )
{
  set<set<T> > init;
  return std::accumulate( sets.begin(), sets.end(), init, 
			  cart_prod_r<T,_Reject_elem>(r));
}
