#ifndef STL_ITERATOR
#define STL_ITERATOR

#include "iostream"
#include "streambuf"
#include "utility"

namespace std
{
template <class CharT>
struct char_traits;

template <
  class Category,
  class T,
  class Distance = ptrdiff_t,
  class Pointer = T *,
  class Reference = T &>
class iterator
{
public:
  typedef T value_type;
  typedef Distance difference_type;
  typedef Pointer pointer;
  typedef Reference reference;
  typedef Category iterator_category;
};

///  Marking input iterators.
class input_iterator_tag
{
};

///  Marking output iterators.
class output_iterator_tag
{
};

// Marking random iterators
class random_access_iterator_tag
{
};

template <class Iterator>
class iterator_traits
{
  typedef typename Iterator::difference_type difference_type;
  typedef typename Iterator::value_type value_type;
  typedef typename Iterator::pointer pointer;
  typedef typename Iterator::reference reference;
  typedef typename Iterator::iterator_category iterator_category;
};

template <class T>
struct iterator_traits<T *>
{
  typedef ptrdiff_t difference_type;
  typedef T value_type;
  typedef T *pointer;
  typedef T &reference;
  typedef random_access_iterator_tag iterator_category;
};

template <class T>
struct iterator_traits<const T *>
{
  typedef ptrdiff_t difference_type;
  typedef T value_type;
  typedef const T *pointer;
  typedef const T &reference;
  typedef random_access_iterator_tag iterator_category;
};

template <class InputIterator, class Distance>
void advance(InputIterator &i, Distance n);

template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);

template <class Container>
class back_insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
{
protected:
  Container *container;

public:
  typedef Container container_type;
  explicit back_insert_iterator(Container &x) : container(&x)
  {
  }
  back_insert_iterator<Container> &
  operator=(typename Container::const_reference value)
  {
    container->push_back(value);
    return *this;
  }
  back_insert_iterator<Container> &operator*()
  {
    return *this;
  }
  back_insert_iterator<Container> &operator++()
  {
    return *this;
  }
  back_insert_iterator<Container> operator++(int)
  {
    return *this;
  }
};

template <class Container>
class front_insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
{
protected:
  Container *container;

public:
  typedef Container container_type;
  explicit front_insert_iterator(Container &x) : container(&x)
  {
  }
  front_insert_iterator<Container> &
  operator=(typename Container::const_reference value)
  {
    container->push_front(value);
    return *this;
  }
  front_insert_iterator<Container> &operator*()
  {
    return *this;
  }
  front_insert_iterator<Container> &operator++()
  {
    return *this;
  }
  front_insert_iterator<Container> operator++(int)
  {
    return *this;
  }
};

template <class Container>
class insert_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
{
protected:
  Container *container;
  typename Container::iterator iter;

public:
  typedef Container container_type;
  explicit insert_iterator(Container &x, typename Container::iterator i)
    : container(&x), iter(i)
  {
  }
  insert_iterator<Container> &
  operator=(typename Container::const_reference value)
  {
    iter = container->insert(iter, value);
    ++iter;
    return *this;
  }
  insert_iterator<Container> &operator*()
  {
    return *this;
  }
  insert_iterator<Container> &operator++()
  {
    return *this;
  }
  insert_iterator<Container> operator++(int)
  {
    return *this;
  }
};

template <class Container>
back_insert_iterator<Container> back_inserter(Container &x);

template <class Container>
front_insert_iterator<Container> front_inserter(Container &x);

template <class Container, class Inserter>
insert_iterator<Container> inserter(Container &x, Inserter i);

template <class Iterator>
class reverse_iterator
  : public std::iterator<
      typename std::iterator_traits<Iterator>::iterator_category,
      typename std::iterator_traits<Iterator>::value_type,
      typename std::iterator_traits<Iterator>::difference_type,
      typename std::iterator_traits<Iterator>::pointer,
      typename std::iterator_traits<Iterator>::reference>
{
public:
  typedef
    typename std::iterator_traits<Iterator>::difference_type difference_type;
  typedef typename std::iterator_traits<Iterator>::pointer pointer;
  typedef typename std::iterator_traits<Iterator>::reference reference;

  Iterator base() const;
  reference operator*() const;
  reverse_iterator operator+(difference_type n) const;
  reverse_iterator &operator++();
  reverse_iterator operator++(int);
  reverse_iterator &operator+=(difference_type n);
  reverse_iterator operator-(difference_type n) const;
  reverse_iterator &operator--();
  reverse_iterator operator--(int);
  reverse_iterator &operator-=(difference_type n);
  pointer operator->() const;
  reference operator[](difference_type n) const;
};

template <
  class T,
  class charT = char,
  class traits = char_traits<charT>,
  class Distance = ptrdiff_t>
class istream_iterator
  : public iterator<input_iterator_tag, T, Distance, const T *, const T &>
{
  istream *in_stream;
  T value;

public:
  typedef charT char_type;
  typedef traits traits_type;
  typedef istream istream_type;
  istream_iterator() : in_stream(0)
  {
  }
  istream_iterator(istream_type &s) : in_stream(&s)
  {
    //++*this;
  }
  //istream_iterator(const istream_iterator<T, charT, traits, Distance>& x) :
  //	in_stream(x.in_stream), value(x.value) {
  //}
  ~istream_iterator()
  {
  }
  const T &operator*() const
  {
    return value;
  }
  const T &operator++() const;
  /*
	const T* operator->() const {
		return &value;
	}
	istream_iterator<T, charT, traits, Distance>& operator++() {
		if (in_stream && !(*in_stream >> value))
			in_stream = 0;
		return *this;
	}
	istream_iterator<T, charT, traits, Distance> operator++(int) {
		istream_iterator<T, charT, traits, Distance> tmp = *this;
		++*this;
		return tmp;
	}*/
};

template <class T, class charT = char, class traits = char_traits<charT>>
class ostream_iterator
  : public iterator<output_iterator_tag, void, void, void, void>
{
  ostream *out_stream;
  const charT *delim;

public:
  typedef charT char_type;
  typedef traits traits_type;
  typedef ostream ostream_type;
  ostream_iterator(ostream_type &s) : out_stream(&s), delim(0)
  {
  }
  ostream_iterator(ostream_type &s, const charT *delimiter)
    : out_stream(&s), delim(delimiter)
  {
  }
  ostream_iterator(ostream_type &s, char *delimiter)
    : out_stream(&s), delim(delimiter)
  {
  }
  ostream_iterator(ostream_iterator<T, charT, traits> &x); /* :
			out_stream(x.out_stream), delim(x.delim) {
	}*/
  ~ostream_iterator()
  {
  }

  ostream_iterator<T, charT, traits> &operator=(const T &value)
  {
    *out_stream << value;
    if (delim != 0)
      *out_stream << delim;
    return *this;
  }
  ostream_iterator<T, charT, traits> &operator*()
  {
    return *this;
  }
  ostream_iterator<T, charT, traits> &operator++()
  {
    return *this;
  }
  ostream_iterator<T, charT, traits> &operator++(int)
  {
    return *this;
  }
};

#if 0
template <class charT = char, class traits = std::char_traits<charT> >
class istreambuf_iterator : public std::iterator<std::input_iterator_tag, charT, typename traits::off_type, charT*, charT&>
{
public:
    typedef charT char_type;
    typedef traits traits_type;
    typedef typename traits::int_type int_type;
    typedef std::basic_streambuf<charT, traits> streambuf_type;
    typedef std::basic_istream<charT, traits> istream_type;

    class proxy
    {
        charT keep_;
        streambuf_type* sbuf_;

    public:
        proxy(charT c, streambuf_type* sbuf) : keep_(c), sbuf_(sbuf) {}
        charT operator*() { return keep_; }
    };

    istreambuf_iterator() throw() : sbuf_(0) {}
    istreambuf_iterator(istream_type& s) throw() : sbuf_(s.rdbuf()) {}
    istreambuf_iterator(streambuf_type* s) throw() : sbuf_(s) {}
    istreambuf_iterator(const proxy& p) throw() : sbuf_(p.sbuf_) {}

    charT operator*() const { return sbuf_->sgetc(); }
    istreambuf_iterator<charT, traits>& operator++() { sbuf_->sbumpc(); return *this; }
    proxy operator++(int) { return proxy(sbuf_->sbumpc(), sbuf_); }

    bool equal(istreambuf_iterator& b) const
    {
        if (sbuf_ == 0 || *(*this) == traits::eof())
        {
            if (b.sbuf_ == 0 || *b == traits::eof())
                return true;
        }
        else if (b.sbuf_ != 0 && *b != traits::eof())
            return true;
        return false;
    }

private:
  streambuf_type* sbuf_;
};


template <class charT = char, class traits = char_traits<charT> >
class ostreambuf_iterator
  : public iterator<output_iterator_tag, charT, void, charT *, charT &>
{
public:
  typedef charT char_type;
  typedef traits traits_type;
  typedef int int_type;
  typedef streambuf streambuf_type;
  typedef ostream ostream_type;

  ostreambuf_iterator(ostream_type &s) throw();   /* :
			sbuf_(s.rdbuf()) {
	}*/
  ostreambuf_iterator(streambuf_type *s) throw(); /* :
			sbuf_(s) {
	}*/
  ostreambuf_iterator &operator=(charT c);        /* {
		if (!failed())
			last = sbuf_->sputc(c);
		return *this;
	}*/

  ostreambuf_iterator &operator*();    /* {
		return *this;
	}*/
  ostreambuf_iterator &operator++();   /* {
		return *this;
	}*/
  ostreambuf_iterator operator++(int); /* {
		return *this;
	}*/

  bool failed() const throw(); /* {
		return last == traits::eof();
	}*/
private:
  streambuf_type *sbuf_;
  charT last;
};

} // namespace std
#endif

#if __cplusplus >= 201103L
template <class C>
constexpr auto begin(C &c) -> decltype(c.begin())
{
  return c.begin();
}

template <class C>
constexpr auto begin(const C &c) -> decltype(c.begin())
{
  return c.begin();
}

template <class C>
constexpr auto end(C &c) -> decltype(c.end())
{
  return c.end();
}

template <class C>
constexpr auto end(const C &c) -> decltype(c.end())
{
  return c.end();
}

template <class T, std::size_t N>
constexpr T *begin(T (&arr)[N]) noexcept
{
  return arr;
}

template <class T, std::size_t N>
constexpr T *end(T (&arr)[N]) noexcept
{
  return arr + N;
}
#endif

#if __cplusplus >= 201402L
template <class C>
constexpr auto cbegin(const C &c) noexcept(noexcept(std::begin(c)))
  -> decltype(std::begin(c))
{
  return std::begin(c);
}

template <class C>
constexpr auto cend(const C &c) noexcept(noexcept(std::end(c)))
  -> decltype(std::end(c))
{
  return std::end(c);
}
#endif

} // namespace std
#endif
