// <functional> -*- C++ -*-

// Copyright (C) 2001-2022 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/*
 * Copyright (c) 1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */

/** @file include/functional
 *  This is a Standard C++ Library header.
 */

#ifndef _GLIBCXX_FUNCTIONAL
#define _GLIBCXX_FUNCTIONAL 1

#pragma GCC system_header

#include <bits/c++config.h>
#include <bits/stl_function.h>

#if __cplusplus >= 201103L

#include <new>
#include <tuple>
#include <type_traits>
#include <bits/functional_hash.h>
#include <bits/invoke.h>
#include <bits/refwrap.h>	// std::reference_wrapper and _Mem_fn_traits
#include <bits/std_function.h>	// std::function
#if __cplusplus > 201402L
# include <unordered_map>
# include <vector>
# include <array>
# include <bits/stl_algo.h>
#endif
#if __cplusplus > 201703L
# include <bits/ranges_cmp.h>
# include <compare>
#endif
#if __cplusplus > 202002L
# include <bits/move_only_function.h>
#endif

#endif // C++11

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /** @brief The type of placeholder objects defined by libstdc++.
   *  @ingroup binders
   *  @since C++11
   */
  template<int _Num> struct _Placeholder { };

#if __cplusplus >= 201103L

#if __cplusplus >= 201703L
# define __cpp_lib_invoke 201411L
# if __cplusplus > 201703L
#  define __cpp_lib_constexpr_functional 201907L
# endif

  /** Invoke a callable object.
   *
   * `std::invoke` takes a callable object as its first argument and calls it
   * with the remaining arguments. The callable object can be a pointer or
   * reference to a function, a lambda closure, a class with `operator()`,
   * or even a pointer-to-member.  For a pointer-to-member the first argument
   * must be a reference or pointer to the object that the pointer-to-member
   * will be applied to.
   *
   *  @since C++17
   */
  template<typename _Callable, typename... _Args>
    inline _GLIBCXX20_CONSTEXPR invoke_result_t<_Callable, _Args...>
    invoke(_Callable&& __fn, _Args&&... __args)
    noexcept(is_nothrow_invocable_v<_Callable, _Args...>)
    {
      return std::__invoke(std::forward<_Callable>(__fn),
			   std::forward<_Args>(__args)...);
    }

#if __cplusplus > 202002L
# define __cpp_lib_invoke_r 202106L

  /** Invoke a callable object and convert the result to `_Res`.
   *
   * `std::invoke_r<R>(f, args...)` is equivalent to `std::invoke(f, args...)`
   * with the result implicitly converted to `R`.
   *
   *  @since C++23
   */
  template<typename _Res, typename _Callable, typename... _Args>
    requires is_invocable_r_v<_Res, _Callable, _Args...>
    constexpr _Res
    invoke_r(_Callable&& __fn, _Args&&... __args)
    noexcept(is_nothrow_invocable_r_v<_Res, _Callable, _Args...>)
    {
      return std::__invoke_r<_Res>(std::forward<_Callable>(__fn),
				   std::forward<_Args>(__args)...);
    }
#endif // C++23
#endif // C++17

  /// @cond undocumented

  template<typename _MemFunPtr,
	   bool __is_mem_fn = is_member_function_pointer<_MemFunPtr>::value>
    class _Mem_fn_base
    : public _Mem_fn_traits<_MemFunPtr>::__maybe_type
    {
      using _Traits = _Mem_fn_traits<_MemFunPtr>;

      using _Arity = typename _Traits::__arity;
      using _Varargs = typename _Traits::__vararg;

      template<typename _Func, typename... _BoundArgs>
	friend struct _Bind_check_arity;

      _MemFunPtr _M_pmf;

    public:

      using result_type = typename _Traits::__result_type;

      explicit constexpr
      _Mem_fn_base(_MemFunPtr __pmf) noexcept : _M_pmf(__pmf) { }

      template<typename... _Args>
	_GLIBCXX20_CONSTEXPR
	auto
	operator()(_Args&&... __args) const
	noexcept(noexcept(
	      std::__invoke(_M_pmf, std::forward<_Args>(__args)...)))
	-> decltype(std::__invoke(_M_pmf, std::forward<_Args>(__args)...))
	{ return std::__invoke(_M_pmf, std::forward<_Args>(__args)...); }
    };

  // Partial specialization for member object pointers.
  template<typename _MemObjPtr>
    class _Mem_fn_base<_MemObjPtr, false>
    {
      using _Arity = integral_constant<size_t, 0>;
      using _Varargs = false_type;

      template<typename _Func, typename... _BoundArgs>
	friend struct _Bind_check_arity;

      _MemObjPtr _M_pm;

    public:
      explicit constexpr
      _Mem_fn_base(_MemObjPtr __pm) noexcept : _M_pm(__pm) { }

      template<typename _Tp>
	_GLIBCXX20_CONSTEXPR
	auto
	operator()(_Tp&& __obj) const
	noexcept(noexcept(std::__invoke(_M_pm, std::forward<_Tp>(__obj))))
	-> decltype(std::__invoke(_M_pm, std::forward<_Tp>(__obj)))
	{ return std::__invoke(_M_pm, std::forward<_Tp>(__obj)); }
    };

  template<typename _MemberPointer>
    struct _Mem_fn; // undefined

  template<typename _Res, typename _Class>
    struct _Mem_fn<_Res _Class::*>
    : _Mem_fn_base<_Res _Class::*>
    {
      using _Mem_fn_base<_Res _Class::*>::_Mem_fn_base;
    };
  /// @endcond

  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // 2048.  Unnecessary mem_fn overloads
  /**
   * @brief Returns a function object that forwards to the member pointer
   * pointer `pm`.
   *
   * This allows a pointer-to-member to be transformed into a function object
   * that can be called with an object expression as its first argument.
   *
   * For a pointer-to-data-member the result must be called with exactly one
   * argument, the object expression that would be used as the first operand
   * in a `obj.*memptr` or `objp->*memptr` expression.
   *
   * For a pointer-to-member-function the result must be called with an object
   * expression and any additional arguments to pass to the member function,
   * as in an expression like `(obj.*memfun)(args...)` or
   * `(objp->*memfun)(args...)`.
   *
   * The object expression can be a pointer, reference, `reference_wrapper`,
   * or smart pointer, and the call wrapper will dereference it as needed
   * to apply the pointer-to-member.
   *
   * @ingroup functors
   * @since C++11
   */
  template<typename _Tp, typename _Class>
    _GLIBCXX20_CONSTEXPR
    inline _Mem_fn<_Tp _Class::*>
    mem_fn(_Tp _Class::* __pm) noexcept
    {
      return _Mem_fn<_Tp _Class::*>(__pm);
    }

  /**
   * @brief Trait that identifies a bind expression.
   * 
   * Determines if the given type `_Tp` is a function object that
   * should be treated as a subexpression when evaluating calls to
   * function objects returned by `std::bind`.
   *
   * C++11 [func.bind.isbind].
   * @ingroup binders
   * @since C++11
   */
  template<typename _Tp>
    struct is_bind_expression
    : public false_type { };

  /**
   *  @brief Determines if the given type _Tp is a placeholder in a
   *  bind() expression and, if so, which placeholder it is.
   *
   *  C++11 [func.bind.isplace].
   *  @ingroup binders
   *  @since C++11
   */
  template<typename _Tp>
    struct is_placeholder
    : public integral_constant<int, 0>
    { };

#if __cplusplus > 201402L
  template <typename _Tp> inline constexpr bool is_bind_expression_v
    = is_bind_expression<_Tp>::value;
  template <typename _Tp> inline constexpr int is_placeholder_v
    = is_placeholder<_Tp>::value;
#endif // C++17

  /** @namespace std::placeholders
   *  @brief ISO C++ 2011 namespace for std::bind placeholders.
   *  @ingroup binders
   *  @since C++11
   */
  namespace placeholders
  {
  /* Define a large number of placeholders. There is no way to
   * simplify this with variadic templates, because we're introducing
   * unique names for each.
   */
    extern const _Placeholder<1> _1;
    extern const _Placeholder<2> _2;
    extern const _Placeholder<3> _3;
    extern const _Placeholder<4> _4;
    extern const _Placeholder<5> _5;
    extern const _Placeholder<6> _6;
    extern const _Placeholder<7> _7;
    extern const _Placeholder<8> _8;
    extern const _Placeholder<9> _9;
    extern const _Placeholder<10> _10;
    extern const _Placeholder<11> _11;
    extern const _Placeholder<12> _12;
    extern const _Placeholder<13> _13;
    extern const _Placeholder<14> _14;
    extern const _Placeholder<15> _15;
    extern const _Placeholder<16> _16;
    extern const _Placeholder<17> _17;
    extern const _Placeholder<18> _18;
    extern const _Placeholder<19> _19;
    extern const _Placeholder<20> _20;
    extern const _Placeholder<21> _21;
    extern const _Placeholder<22> _22;
    extern const _Placeholder<23> _23;
    extern const _Placeholder<24> _24;
    extern const _Placeholder<25> _25;
    extern const _Placeholder<26> _26;
    extern const _Placeholder<27> _27;
    extern const _Placeholder<28> _28;
    extern const _Placeholder<29> _29;
  }

  /**
   *  Partial specialization of is_placeholder that provides the placeholder
   *  number for the placeholder objects defined by libstdc++.
   *  @ingroup binders
   *  @since C++11
   */
  template<int _Num>
    struct is_placeholder<_Placeholder<_Num> >
    : public integral_constant<int, _Num>
    { };

  template<int _Num>
    struct is_placeholder<const _Placeholder<_Num> >
    : public integral_constant<int, _Num>
    { };

  /// @cond undocumented

  // Like tuple_element_t but SFINAE-friendly.
  template<std::size_t __i, typename _Tuple>
    using _Safe_tuple_element_t
      = typename enable_if<(__i < tuple_size<_Tuple>::value),
			   tuple_element<__i, _Tuple>>::type::type;

  /**
   *  Maps an argument to bind() into an actual argument to the bound
   *  function object [func.bind.bind]/10. Only the first parameter should
   *  be specified: the rest are used to determine among the various
   *  implementations. Note that, although this class is a function
   *  object, it isn't entirely normal because it takes only two
   *  parameters regardless of the number of parameters passed to the
   *  bind expression. The first parameter is the bound argument and
   *  the second parameter is a tuple containing references to the
   *  rest of the arguments.
   */
  template<typename _Arg,
	   bool _IsBindExp = is_bind_expression<_Arg>::value,
	   bool _IsPlaceholder = (is_placeholder<_Arg>::value > 0)>
    class _Mu;

  /**
   *  If the argument is reference_wrapper<_Tp>, returns the
   *  underlying reference.
   *  C++11 [func.bind.bind] p10 bullet 1.
   */
  template<typename _Tp>
    class _Mu<reference_wrapper<_Tp>, false, false>
    {
    public:
      /* Note: This won't actually work for const volatile
       * reference_wrappers, because reference_wrapper::get() is const
       * but not volatile-qualified. This might be a defect in the TR.
       */
      template<typename _CVRef, typename _Tuple>
	_GLIBCXX20_CONSTEXPR
	_Tp&
	operator()(_CVRef& __arg, _Tuple&) const volatile
	{ return __arg.get(); }
    };

  /**
   *  If the argument is a bind expression, we invoke the underlying
   *  function object with the same cv-qualifiers as we are given and
   *  pass along all of our arguments (unwrapped).
   *  C++11 [func.bind.bind] p10 bullet 2.
   */
  template<typename _Arg>
    class _Mu<_Arg, true, false>
    {
    public:
      template<typename _CVArg, typename... _Args>
	_GLIBCXX20_CONSTEXPR
	auto
	operator()(_CVArg& __arg,
		   tuple<_Args...>& __tuple) const volatile
	-> decltype(__arg(declval<_Args>()...))
	{
	  // Construct an index tuple and forward to __call
	  typedef typename _Build_index_tuple<sizeof...(_Args)>::__type
	    _Indexes;
	  return this->__call(__arg, __tuple, _Indexes());
	}

    private:
      // Invokes the underlying function object __arg by unpacking all
      // of the arguments in the tuple.
      template<typename _CVArg, typename... _Args, std::size_t... _Indexes>
	_GLIBCXX20_CONSTEXPR
	auto
	__call(_CVArg& __arg, tuple<_Args...>& __tuple,
	       const _Index_tuple<_Indexes...>&) const volatile
	-> decltype(__arg(declval<_Args>()...))
	{
	  return __arg(std::get<_Indexes>(std::move(__tuple))...);
	}
    };

  /**
   *  If the argument is a placeholder for the Nth argument, returns
   *  a reference to the Nth argument to the bind function object.
   *  C++11 [func.bind.bind] p10 bullet 3.
   */
  template<typename _Arg>
    class _Mu<_Arg, false, true>
    {
    public:
      template<typename _Tuple>
	_GLIBCXX20_CONSTEXPR
	_Safe_tuple_element_t<(is_placeholder<_Arg>::value - 1), _Tuple>&&
	operator()(const volatile _Arg&, _Tuple& __tuple) const volatile
	{
	  return
	    ::std::get<(is_placeholder<_Arg>::value - 1)>(std::move(__tuple));
	}
    };

  /**
   *  If the argument is just a value, returns a reference to that
   *  value. The cv-qualifiers on the reference are determined by the caller.
   *  C++11 [func.bind.bind] p10 bullet 4.
   */
  template<typename _Arg>
    class _Mu<_Arg, false, false>
    {
    public:
      template<typename _CVArg, typename _Tuple>
	_GLIBCXX20_CONSTEXPR
	_CVArg&&
	operator()(_CVArg&& __arg, _Tuple&) const volatile
	{ return std::forward<_CVArg>(__arg); }
    };

  // std::get<I> for volatile-qualified tuples
  template<std::size_t _Ind, typename... _Tp>
    inline auto
    __volget(volatile tuple<_Tp...>& __tuple)
    -> __tuple_element_t<_Ind, tuple<_Tp...>> volatile&
    { return std::get<_Ind>(const_cast<tuple<_Tp...>&>(__tuple)); }

  // std::get<I> for const-volatile-qualified tuples
  template<std::size_t _Ind, typename... _Tp>
    inline auto
    __volget(const volatile tuple<_Tp...>& __tuple)
    -> __tuple_element_t<_Ind, tuple<_Tp...>> const volatile&
    { return std::get<_Ind>(const_cast<const tuple<_Tp...>&>(__tuple)); }

  /// @endcond

#if __cplusplus == 201703L && _GLIBCXX_USE_DEPRECATED
# define _GLIBCXX_VOLATILE_BIND
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2487. bind() should be const-overloaded, not cv-overloaded
# define _GLIBCXX_DEPR_BIND \
      [[deprecated("std::bind does not support volatile in C++17")]]
#elif __cplusplus < 201703L
# define _GLIBCXX_VOLATILE_BIND
# define _GLIBCXX_DEPR_BIND
#endif

  /// Type of the function object returned from bind().
  template<typename _Signature>
    class _Bind;

   template<typename _Functor, typename... _Bound_args>
    class _Bind<_Functor(_Bound_args...)>
    : public _Weak_result_type<_Functor>
    {
      typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type
	_Bound_indexes;

      _Functor _M_f;
      tuple<_Bound_args...> _M_bound_args;

      // Call unqualified
      template<typename _Result, typename... _Args, std::size_t... _Indexes>
	_GLIBCXX20_CONSTEXPR
	_Result
	__call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
	{
	  return std::__invoke(_M_f,
	      _Mu<_Bound_args>()(std::get<_Indexes>(_M_bound_args), __args)...
	      );
	}

      // Call as const
      template<typename _Result, typename... _Args, std::size_t... _Indexes>
	_GLIBCXX20_CONSTEXPR
	_Result
	__call_c(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
	{
	  return std::__invoke(_M_f,
	      _Mu<_Bound_args>()(std::get<_Indexes>(_M_bound_args), __args)...
	      );
	}

#ifdef _GLIBCXX_VOLATILE_BIND
      // Call as volatile
      template<typename _Result, typename... _Args, std::size_t... _Indexes>
	_Result
	__call_v(tuple<_Args...>&& __args,
		 _Index_tuple<_Indexes...>) volatile
	{
	  return std::__invoke(_M_f,
	      _Mu<_Bound_args>()(__volget<_Indexes>(_M_bound_args), __args)...
	      );
	}

      // Call as const volatile
      template<typename _Result, typename... _Args, std::size_t... _Indexes>
	_Result
	__call_c_v(tuple<_Args...>&& __args,
		   _Index_tuple<_Indexes...>) const volatile
	{
	  return std::__invoke(_M_f,
	      _Mu<_Bound_args>()(__volget<_Indexes>(_M_bound_args), __args)...
	      );
	}
#endif // volatile

      template<typename _BoundArg, typename _CallArgs>
	using _Mu_type = decltype(
	    _Mu<typename remove_cv<_BoundArg>::type>()(
	      std::declval<_BoundArg&>(), std::declval<_CallArgs&>()) );

      template<typename _Fn, typename _CallArgs, typename... _BArgs>
	using _Res_type_impl
	  = typename result_of< _Fn&(_Mu_type<_BArgs, _CallArgs>&&...) >::type;

      template<typename _CallArgs>
	using _Res_type = _Res_type_impl<_Functor, _CallArgs, _Bound_args...>;

      template<typename _CallArgs>
	using __dependent = typename
	  enable_if<bool(tuple_size<_CallArgs>::value+1), _Functor>::type;

      template<typename _CallArgs, template<class> class __cv_quals>
	using _Res_type_cv = _Res_type_impl<
	  typename __cv_quals<__dependent<_CallArgs>>::type,
	  _CallArgs,
	  typename __cv_quals<_Bound_args>::type...>;

     public:
      template<typename... _Args>
	explicit _GLIBCXX20_CONSTEXPR
	_Bind(const _Functor& __f, _Args&&... __args)
	: _M_f(__f), _M_bound_args(std::forward<_Args>(__args)...)
	{ }

      template<typename... _Args>
	explicit _GLIBCXX20_CONSTEXPR
	_Bind(_Functor&& __f, _Args&&... __args)
	: _M_f(std::move(__f)), _M_bound_args(std::forward<_Args>(__args)...)
	{ }

      _Bind(const _Bind&) = default;
      _Bind(_Bind&&) = default;

      // Call unqualified
      template<typename... _Args,
	       typename _Result = _Res_type<tuple<_Args...>>>
	_GLIBCXX20_CONSTEXPR
	_Result
	operator()(_Args&&... __args)
	{
	  return this->__call<_Result>(
	      std::forward_as_tuple(std::forward<_Args>(__args)...),
	      _Bound_indexes());
	}

      // Call as const
      template<typename... _Args,
	       typename _Result = _Res_type_cv<tuple<_Args...>, add_const>>
	_GLIBCXX20_CONSTEXPR
	_Result
	operator()(_Args&&... __args) const
	{
	  return this->__call_c<_Result>(
	      std::forward_as_tuple(std::forward<_Args>(__args)...),
	      _Bound_indexes());
	}

#ifdef _GLIBCXX_VOLATILE_BIND
      // Call as volatile
      template<typename... _Args,
	       typename _Result = _Res_type_cv<tuple<_Args...>, add_volatile>>
	_GLIBCXX_DEPR_BIND
	_Result
	operator()(_Args&&... __args) volatile
	{
	  return this->__call_v<_Result>(
	      std::forward_as_tuple(std::forward<_Args>(__args)...),
	      _Bound_indexes());
	}

      // Call as const volatile
      template<typename... _Args,
	       typename _Result = _Res_type_cv<tuple<_Args...>, add_cv>>
	_GLIBCXX_DEPR_BIND
	_Result
	operator()(_Args&&... __args) const volatile
	{
	  return this->__call_c_v<_Result>(
	      std::forward_as_tuple(std::forward<_Args>(__args)...),
	      _Bound_indexes());
	}
#endif // volatile
    };

  /// Type of the function object returned from bind<R>().
  template<typename _Result, typename _Signature>
    class _Bind_result;

  template<typename _Result, typename _Functor, typename... _Bound_args>
    class _Bind_result<_Result, _Functor(_Bound_args...)>
    {
      typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type
	_Bound_indexes;

      _Functor _M_f;
      tuple<_Bound_args...> _M_bound_args;

      // Call unqualified
      template<typename _Res, typename... _Args, std::size_t... _Indexes>
	_GLIBCXX20_CONSTEXPR
	_Res
	__call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
	{
	  return std::__invoke_r<_Res>(_M_f, _Mu<_Bound_args>()
		      (std::get<_Indexes>(_M_bound_args), __args)...);
	}

      // Call as const
      template<typename _Res, typename... _Args, std::size_t... _Indexes>
	_GLIBCXX20_CONSTEXPR
	_Res
	__call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
	{
	  return std::__invoke                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        