#include <concepts>
#include <type_traits>
#include <utility>

namespace stdlite {

  template <class Tp>
  Tp&& _declval() noexcept;

  struct _cp {
    template <class Tp>
    using _f = Tp;
  };

  struct _cpc {
    template <class Tp>
    using _f = const Tp;
  };

  struct _cplr {
    template <class Tp>
    using _f = Tp&;
  };

  struct _cprr {
    template <class Tp>
    using _f = Tp&&;
  };

  struct _cpclr {
    template <class Tp>
    using _f = const Tp&;
  };

  struct _cpcrr {
    template <class Tp>
    using _f = const Tp&&;
  };

  template <class>
  extern _cp _cpcvr;
  template <class Tp>
  extern _cpc _cpcvr<const Tp>;
  template <class Tp>
  extern _cplr _cpcvr<Tp&>;
  template <class Tp>
  extern _cprr _cpcvr<Tp&&>;
  template <class Tp>
  extern _cpclr _cpcvr<const Tp&>;
  template <class Tp>
  extern _cpcrr _cpcvr<const Tp&&>;
  template <class Tp>
  using _copy_cvref_fn = decltype(_cpcvr<Tp>);

  template <class From, class To>
  using _copy_cvref_t = typename _copy_cvref_fn<From>::template _f<To>;

  template <class Fun, class... As>
  concept _callable =
    requires(Fun&& _fun, As&&... _as) {
      ((Fun&&) _fun)((As&&) _as...);
    };
  template <class Fun, class... As>
  concept _nothrow_callable =
    _callable<Fun, As...> &&
    requires(Fun&& _fun, As&&... _as) {
      { ((Fun&&) _fun)((As&&) _as...) } noexcept;
    };

  template <class Ty, class Up>
  concept _decays_to = std::same_as<std::decay_t<Ty>, Up>;

  template <class...>
  struct _undefined;

  struct _ignore {
    _ignore() = default;

    constexpr _ignore(auto&&...) noexcept {
    }
  };

  template <class Ty>
  struct _mtype {
    using _t = Ty;
  };

  template <class...>
  struct _types;

  template <class Tp, class Up>
  using _mfirst = Tp;

  template <std::size_t Np>
  using _msize_t = char[Np + 1];

  template <class Tp>
  extern const _undefined<Tp> _v;

  template <std::size_t Ip>
  inline constexpr std::size_t _v<char[Ip]> = Ip - 1;

  template <bool>
  struct _i {
    template <template <class...> class Fn, class... Args>
    using _g = Fn<Args...>;
  };

  template <class...>
  concept Ok = true;

  template <template <class...> class Fn, class... Args>
  using _meval = typename _i<Ok<Args...>>::template _g<Fn, Args...>;

  template <class Fn, class... Args>
  using _minvoke = _meval<Fn::template _f, Args...>;

  template <template <class...> class Fn>
  struct _q {
    template <class... Args>
    using _f = _meval<Fn, Args...>;
  };

  template <template <class...> class Tp, class... Args>
  concept _valid = requires { typename _meval<Tp, Args...>; };

  template <template <class...> class Tp, class... Args>
  concept _invalid = !_valid<Tp, Args...>;

  template <class Fn, class... Args>
  concept _minvocable = _valid<Fn::template _f, Args...>;

  template <bool>
  struct _if_ {
    template <class True, class...>
    using _f = True;
  };

  template <>
  struct _if_<false> {
    template <class, class False>
    using _f = False;
  };

  template <bool Pred, class True = void, class... False>
    requires(sizeof...(False) <= 1)
  using _if_c = _minvoke<_if_<Pred>, True, False...>;

  template <class Tp>
  struct _mexpand;

  template <template <class...> class Ap, class... As>
  struct _mexpand<Ap<As...>> {
    template <class Fn, class... Bs>
    using _f = _minvoke<Fn, Bs..., As...>;
  };

  template <class Fn, class List>
  using _mapply = _minvoke<_mexpand<List>, Fn>;

  template <class Fn, class List>
  concept _mapplicable = _minvocable<_mexpand<List>, Fn>;

  template <class Fun, class... As>
  using _call_result_t = decltype(_declval<Fun>()(_declval<As>()...));

  template <class Ty>
  const Ty& _cref_fn(const Ty&);

  template <class Ty>
  using _cref_t = decltype(stdlite::_cref_fn(_declval<Ty>()));

  template <class... Lists>
    requires (_mapplicable<_q<_types>, Lists> &&...)
  struct _mzip_with_
    : _mzip_with_<_mapply<_q<_types>, Lists>...> { };

  template <class... Cs>
  struct _mzip_with_<_types<Cs...>> {
    template <class Fn, class Continuation>
    using _f = _minvoke<Continuation, _minvoke<Fn, Cs>...>;
  };

  template <class... Cs, class... Ds>
  struct _mzip_with_<_types<Cs...>, _types<Ds...>> {
    template <class Fn, class Continuation>
    using _f = _minvoke<Continuation, _minvoke<Fn, Cs, Ds>...>;
  };

  template <class Fn, class Continuation = _q<_types>>
  struct _mzip_with {
    template <class... Lists>
    using _f = _minvoke<_mzip_with_<Lists...>, Fn, Continuation>;
  };

  template <std::size_t>
  using _ignore_t = _ignore;

  template <class Indices>
  struct _nth_pack_element_;

  template <std::size_t... Is>
  struct _nth_pack_element_<std::index_sequence<Is...>> {
    template <class Ty, class... Us>
    constexpr Ty&& operator()(_ignore_t<Is>..., Ty&& _ty, Us&&...) const noexcept {
      return (Ty&&) _ty;
    }
  };

  template <std::size_t Nn>
  using _nth_pack_element = _nth_pack_element_<std::make_index_sequence<Nn>>;

#if __has_builtin(__type_pack_element)
  template <std::size_t _Np, class... _Ts>
  using _m_at = __type_pack_element<_Np, _Ts...>;
#else
  template <std::size_t>
  using _void_ptr = void*;

  template <class _Ty>
  using _mtype_ptr = _mtype<_Ty>*;

  template <class _Ty>
  struct _m_at_;

  template <std::size_t... _Is>
  struct _m_at_<std::index_sequence<_Is...>> {
    template <class _Up, class... _Us>
    static _Up _f_(_void_ptr<_Is>..., _Up*, _Us*...);
    template <class... _Ts>
    using _f = typename decltype(_m_at_::_f_(_mtype_ptr<_Ts>()...))::_t;
  };

  template <std::size_t _Np, class... _Ts>
  using _m_at = _minvoke<_m_at_<std::make_index_sequence<_Np>>, _Ts...>;
#endif

#if __has_builtin(__is_nothrow_constructible)
  template <class Ty, class... As>
  concept _nothrow_constructible_from =
    std::constructible_from<Ty, As...> && __is_nothrow_constructible(Ty, As...);
#else
  template <class Ty, class... As>
  concept _nothrow_constructible_from =
    std::constructible_from<Ty, As...> && std::is_nothrow_constructible_v<Ty, As...>;
#endif

  template <class Ty>
  concept _nothrow_decay_copyable = _nothrow_constructible_from<std::decay_t<Ty>, Ty>;

  //////////////////////////////////////////////////////////////////////////////////////////////////
  // tuple implementation begins here:
  template <std::size_t Ny, class Impl>
  struct _tuple;

  namespace _tup {
    template <std::size_t Ny, class Impl, class Ty>
      requires std::same_as<_tuple<Ny, Impl>, Ty>
    void _is_tuple_(const _tuple<Ny, Impl>&, const Ty&);

    template <class Ty>
    concept _is_tuple = requires(Ty&& t) { _tup::_is_tuple_(t, t); };
  }

  template <_tup::_is_tuple Tuple>
  extern const std::size_t tuple_size_v;

  template <std::size_t Ny, class Impl>
  struct _mexpand<_tuple<Ny, Impl>>;

  namespace _tup {
    struct _base { };

    template <class Ty>
    struct _wrapper;

    template <class Ty>
    struct _wrapper<Ty&> {
      using type = Ty;
      using reference_wrapper = _wrapper;
      Ty& _val_;

      /*implicit*/ constexpr _wrapper(Ty& t) noexcept
        : _val_(t) {
      }

      constexpr operator Ty&() const noexcept {
        return _val_;
      }
    };

    // Also works with std::reference_wrapper:
    template <class Ty>
    using _unwrapped_t = typename Ty::reference_wrapper::type;

    struct _wrap_fn {
      template <class Ty>
        requires _invalid<_unwrapped_t, Ty>
      constexpr auto operator()(const Ty&&) const = delete;

      template <class Ty>
        requires _invalid<_unwrapped_t, Ty>
      constexpr auto operator()(Ty& _ty) const noexcept -> _wrapper<Ty&> {
        return _ty;
      }

      template <class Ty>
        requires _valid<_unwrapped_t, Ty>
      constexpr auto operator()(Ty _ty) const noexcept -> _wrapper<_unwrapped_t<Ty>&> {
        return static_cast<_unwrapped_t<Ty>&>(_ty);
      }
    };

    template <class Ty>
    struct _any_convertible_to {
      virtual constexpr operator Ty() = 0;

      friend constexpr Ty _move_capture(_any_convertible_to& _self) {
        return static_cast<Ty>(_self);
      }
    };
    template <class Ty>
    struct _any_convertible_to<_any_convertible_to<Ty>>;

    template <class Ty, class Uy>
      requires std::convertible_to<Uy, Ty>
    struct _convertible_from : _any_convertible_to<Ty> {
      Uy&& _src_;

      constexpr _convertible_from(Uy&& _src) noexcept
        : _src_((Uy&&) _src) {
      }

      constexpr operator Ty() override {
        return static_cast<Ty>(static_cast<Uy&&>(_src_));
      }
    };

    struct _self_fn {
      template <class Ty, class Uy>
      using _value = _if_c<std::same_as<Ty&&, Uy&&>, Uy&&, Ty>;
      template <class Ty>
      using _param = Ty;
    };

    struct _tie_fn {
      template <class Ty, class>
      using _value = _wrapper<Ty>;
      template <class Ty>
      using _param = _wrapper<Ty>;
    };

    struct _convert_fn {
      template <class Ty, class Uy>
      using _value = _convertible_from<Ty, Uy>;
      template <class Ty>
      using _param = _any_convertible_to<Ty>&&;
    };

    template <class Ty>
    extern const _self_fn _wrap;
    template <class Ty>
    extern const _tie_fn _wrap<Ty&>;
    template <class Ty>
      requires(!std::move_constructible<Ty>)
    extern const _convert_fn _wrap<Ty>;

    template <class Ty, class Uy>
    using _value_t = typename decltype(_wrap<Ty>)::template _value<Ty, Uy>;
    template <class Ty>
    using _param_t = typename decltype(_wrap<Ty>)::template _param<Ty>;

    template <class Ty>
    auto _unwrap(Ty&&, long) -> Ty&&;
    template <class Ty>
    auto _unwrap(Ty, int) -> _unwrapped_t<Ty>&;
    template <class Ty>
    using _unwrap_t = decltype(_tup::_unwrap(_declval<Ty>(), 0));

    template <class Ty>
    auto _unconst(Ty&&) -> Ty;
    template <class Ty>
    auto _unconst(Ty&) -> Ty&;
    template <class Ty>
    auto _unconst(const Ty&&) -> Ty;
    template <class Ty>
    auto _unconst(const Ty&) -> Ty&;
    template <class Ty>
    using _unconst_t = decltype(_tup::_unconst(_declval<Ty>()));

    struct _access {
      template <_is_tuple Tuple>
      static constexpr decltype(auto) _get_impl(Tuple&& _tup) noexcept {
        return (((Tuple&&) _tup)._fn_);
      }
    };

    template <class Tuple>
    using _impl_of = decltype(_access::_get_impl(_declval<Tuple>()));

    struct _apply_impl {
      template <class Fun, class Impl>
      constexpr auto operator()(Fun&& _fn, Impl&& _impl) const
        noexcept(_nothrow_callable<_unconst_t<Impl>, Impl, Fun>)
          -> _call_result_t<_unconst_t<Impl>, Impl, Fun> {
        return const_cast<_unconst_t<Impl>&&>(_impl)((Impl&&) _impl, (Fun&&) _fn);
      }
    };

    template <class Fun, _is_tuple Tuple>
    constexpr auto apply(Fun&& _fn, Tuple&& _self) noexcept(
      _nothrow_callable<_apply_impl, Fun, _impl_of<Tuple>>)
      -> _call_result_t<_apply_impl, Fun, _impl_of<Tuple>> {
      return _apply_impl()((Fun&&) _fn, _access::_get_impl((Tuple&&) _self));
    }

    template <class Fun, _is_tuple Tuple>
    using _apply_result_t = //
      _call_result_t<_apply_impl, Fun, _impl_of<Tuple>>;

    template <class Fun, class Tuple>
    concept _applicable = //
      _callable<_apply_impl, Fun, _impl_of<Tuple>>;

    template <class Fun, class Tuple>
    concept _nothrow_applicable = //
      _nothrow_callable<_apply_impl, Fun, _impl_of<Tuple>>;

    struct _impl_types_ {
      template <class... Ts>
      auto operator()(Ts&&...) const -> _types<Ts...>;
    };

    template <class Impl>
    using _impl_types = //
      _call_result_t<_apply_impl, _impl_types_, Impl>;

    template <class Tuple>
    using _types_of = _impl_types<_impl_of<Tuple>>;

    template <class Ty>
    constexpr Ty&& _move_capture(Ty& _ty) noexcept {
      return (Ty&&) _ty;
    }

    template <class Ty>
    using _rvalue_t = decltype(_move_capture(_declval<Ty&>()));

    template <class Self, class Ty>
    using _element_t = _unwrap_t<_copy_cvref_t<Self, _rvalue_t<Ty>>>;

    template <class Ty>
    void _decay_copy(Ty) noexcept;

    template <class From, class To>
    concept _decay_convertible_to = //
      requires(From&& _from, _param_t<To>& _w) {
        static_cast<_param_t<To>>(static_cast<_value_t<To, From>>((From&&) _from));
        _tup::_decay_copy(_move_capture(_w));
      };

    template <class... Ts>
    constexpr auto
      _make_impl(Ts&&... _ts) noexcept((_nothrow_decay_copyable<_rvalue_t<Ts>> && ...)) {
      return [... _ts = _move_capture(_ts)]                                           //
            <class Self, class Fun>(Self&&, Fun && _fn) constexpr mutable           //
             noexcept(_nothrow_callable<_unconst_t<Fun>, _element_t<Self, Ts>...>) //
             -> _call_result_t<_unconst_t<Fun>, _element_t<Self, Ts>...> {
               return const_cast<_unconst_t<Fun>&&>(_fn)(
                 static_cast<_element_t<Self, Ts>&&>(_ts)...);
             };
    }

    template <class Ret, class... Args>
    Ret _impl_for_(Ret (*)(Args...));

    template <class... Ts>
    using _impl_for = decltype(_tup::_impl_for_(&_make_impl<_param_t<Ts>...>));

    template <class... Ts>
    using _tuple_for = _tuple<sizeof...(Ts), _impl_for<Ts...>>;

    struct _make_tuple_fn {
      template <std::move_constructible... Ts>
      constexpr _tuple_for<Ts...> operator()(Ts... _ts) const
        noexcept(_nothrow_constructible_from<_tuple_for<Ts...>, Ts...>) {
        return _tuple_for<Ts...>((Ts&&) _ts...);
      }
    };

    template <class Ty>
    struct _make_default {
      operator Ty() const noexcept(noexcept(Ty())) {
        return (Ty());
      }
    };

    template <class Ty>
    using _default_init_for = _if_c<std::move_constructible<Ty>, Ty, _make_default<Ty>>;

    template <class... Ts>
    struct _construct_impl {
      template <class... Us>
        requires(_decay_convertible_to<Us, Ts> && ...)
      constexpr auto operator()(Us&&... us) const noexcept(noexcept(
        _tup::_make_impl<_param_t<Ts>...>(static_cast<_value_t<Ts, Us>>((Us&&) us)...)))
        -> _impl_for<Ts...> {
        return _tup::_make_impl<_param_t<Ts>...>(
          static_cast<_value_t<Ts, Us>>((Us&&) us)...);
      };
    };

    template <class... Ts>
    struct _default_init_impl {
      constexpr auto operator()() noexcept(
        _nothrow_callable<_construct_impl<Ts...>, _default_init_for<Ts>...>)
        requires(std::default_initializable<Ts> && ...)
      {
        return _construct_impl<Ts...>()(_default_init_for<Ts>()...);
      }
    };

    template <class Ty, class U>
    concept _nothrow_assignable_from = //
      requires(Ty&& t, U&& u) {
        { ((Ty&&) t) = ((U&&) u) } noexcept;
      };

    struct _assign_tuple {
      template <class... Ts>
      constexpr auto operator()(Ts&&... _ts) const noexcept {
        return [&]<class... Us>(Us && ... us) noexcept(
          (_nothrow_assignable_from<Ts, Us> && ...))
          requires(std::assignable_from<Ts, Us> && ...)
        {
          ((void) (((Ts&&) _ts) = ((Us&&) us)), ...);
        };
      }
    };

    template <class To, class From>
    concept _tuple_assignable_from = //
      _applicable<_apply_result_t<_assign_tuple, To>, From>;

    template <class To, class From>
    concept _nothrow_tuple_assignable_from = //
      _nothrow_applicable<_apply_result_t<_assign_tuple, To>, From>;

    template <std::size_t Nn, _is_tuple Tuple>
    constexpr auto get(Tuple&& _tup) noexcept
      -> _apply_result_t<_nth_pack_element<Nn>, Tuple> {
      return _tup::apply(_nth_pack_element<Nn>(), (Tuple&&) _tup);
    }
  } // namespace _tup

  template <std::size_t Size, class Impl>
  struct _tuple : private _tup::_base {
   private:
    friend _tup::_access;
    using _types = _tup::_impl_types<Impl>;
    using _construct_impl = _mapply<_q<_tup::_construct_impl>, _types>;
    using _default_init_impl = _mapply<_q<_tup::_default_init_impl>, _types>;

    template <std::size_t, class>
    friend struct _tuple;

    Impl _fn_;

   public:
    constexpr _tuple() noexcept(_nothrow_callable<_default_init_impl>)
      requires _callable<_default_init_impl>
      : _fn_(_default_init_impl()()) {
    }

    _tuple(_tuple&&) = default;
    _tuple(_tuple const &) = default;
    _tuple& operator=(_tuple&&) = default;
    _tuple& operator=(_tuple const &) = default;

    template <class... Us>
      requires(sizeof...(Us) == Size) && _callable<_construct_impl, Us...>
    explicit(sizeof...(Us) == 1) constexpr _tuple(Us&&... _us) noexcept(
      _nothrow_callable<_construct_impl, Us...>)
      : _fn_(_construct_impl()((Us&&) _us...)) {
    }

    template <_tup::_is_tuple Other>
      requires(!_decays_to<Other, _tuple>) && _tup::_applicable<_construct_impl, Other>
    explicit constexpr _tuple(Other&& _other) noexcept(
      _tup::_nothrow_applicable<_construct_impl, Other>)
      : _fn_(_tup::apply(_construct_impl(), (Other&&) _other)) {
    }

    template <_tup::_is_tuple Other>
      requires _tup::_tuple_assignable_from<_tuple, Other>
    constexpr _tuple&& operator=(Other&& _other) && noexcept(
      _tup::_nothrow_tuple_assignable_from<_tuple, Other>) {
      _tup::apply(_tup::apply(_tup::_assign_tuple(), (_tuple&&) *this), (Other&&) _other);
      return (_tuple&&) *this;
    }

    template <_tup::_is_tuple Other>
      requires _tup::_tuple_assignable_from<_tuple&, Other>
    constexpr _tuple& operator=(Other&& _other) & noexcept(
      _tup::_nothrow_tuple_assignable_from<_tuple&, Other>) {
      _tup::apply(_tup::apply(_tup::_assign_tuple(), *this), (Other&&) _other);
      return *this;
    }

    template <_tup::_is_tuple Other>
      requires _tup::_tuple_assignable_from<const _tuple&, Other>
    constexpr const _tuple& operator=(Other&& _other) const & noexcept(
      _tup::_nothrow_tuple_assignable_from<const _tuple&, Other>) {
      _tup::apply(_tup::apply(_tup::_assign_tuple(), *this), (Other&&) _other);
      return *this;
    }
  };

  using _tup::get;
  using _tup::apply;
  using _tup::_apply_result_t;
  using _tup::_applicable;
  using _tup::_nothrow_applicable;

  // From _meta.hpp:
  template <std::size_t Size, class Impl>
  struct _mexpand<_tuple<Size, Impl>> {
    template <class MetaFn>
    using _f = _mapply<MetaFn, _tup::_impl_types<Impl>>;
  };

  template <std::size_t Size, class Impl>
  inline constexpr std::size_t tuple_size_v<_tuple<Size, Impl>> = Size;

  inline constexpr _tup::_wrap_fn ref{};
  inline constexpr _tup::_make_tuple_fn make_tuple{};

  template <class... Ts>
  using tuple = _tuple<sizeof...(Ts), _tup::_impl_for<Ts...>>;
}

namespace std {
  template <class>
  struct tuple_size;

  template <size_t Size, class Impl>
  struct tuple_size<stdlite::_tuple<Size, Impl>> : integral_constant<size_t, Size> { };

  template <size_t Size, class Impl>
  struct tuple_size<const stdlite::_tuple<Size, Impl>> : integral_constant<size_t, Size> { };

  template <size_t Nn>
  struct _tuple_element_ {
    template <class... Ts>
    using _f = stdlite::_m_at<Nn, Ts...>;
  };

  template <size_t Nn, size_t Size, class Impl>
    requires(Nn < Size)
  struct tuple_element<Nn, stdlite::_tuple<Size, Impl>> {
    using type = stdlite::_mapply<_tuple_element_<Nn>, stdlite::_tuple<Size, Impl>>;
  };
}