// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP___HASH_TABLE
#define _LIBCPP___HASH_TABLE

#include <__algorithm/max.h>
#include <__algorithm/min.h>
#include <__assert>
#include <__bit/countl.h>
#include <__config>
#include <__functional/hash.h>
#include <__functional/invoke.h>
#include <__iterator/iterator_traits.h>
#include <__memory/addressof.h>
#include <__memory/allocator_traits.h>
#include <__memory/compressed_pair.h>
#include <__memory/construct_at.h>
#include <__memory/pointer_traits.h>
#include <__memory/swap_allocator.h>
#include <__memory/unique_ptr.h>
#include <__type_traits/can_extract_key.h>
#include <__type_traits/conditional.h>
#include <__type_traits/is_const.h>
#include <__type_traits/is_constructible.h>
#include <__type_traits/is_nothrow_assignable.h>
#include <__type_traits/is_nothrow_constructible.h>
#include <__type_traits/is_pointer.h>
#include <__type_traits/is_reference.h>
#include <__type_traits/is_swappable.h>
#include <__type_traits/remove_const.h>
#include <__type_traits/remove_cvref.h>
#include <__utility/forward.h>
#include <__utility/move.h>
#include <__utility/pair.h>
#include <__utility/swap.h>
#include <cmath>
#include <cstring>
#include <initializer_list>
#include <new> // __launder

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

_LIBCPP_PUSH_MACROS
#include <__undef_macros>

_LIBCPP_BEGIN_NAMESPACE_STD

template <class _Key, class _Tp>
struct __hash_value_type;

template <class _Tp>
struct __is_hash_value_type_imp : false_type {};

template <class _Key, class _Value>
struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value> > : true_type {};

template <class... _Args>
struct __is_hash_value_type : false_type {};

template <class _One>
struct __is_hash_value_type<_One> : __is_hash_value_type_imp<__remove_cvref_t<_One> > {};

_LIBCPP_EXPORTED_FROM_ABI size_t __next_prime(size_t __n);

template <class _NodePtr>
struct __hash_node_base {
  typedef typename pointer_traits<_NodePtr>::element_type __node_type;
  typedef __hash_node_base __first_node;
  typedef __rebind_pointer_t<_NodePtr, __first_node> __node_base_pointer;
  typedef _NodePtr __node_pointer;

#if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB)
  typedef __node_base_pointer __next_pointer;
#else
  typedef __conditional_t<is_pointer<__node_pointer>::value, __node_base_pointer, __node_pointer> __next_pointer;
#endif

  __next_pointer __next_;

  _LIBCPP_HIDE_FROM_ABI __next_pointer __ptr() _NOEXCEPT {
    return static_cast<__next_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));
  }

  _LIBCPP_HIDE_FROM_ABI __node_pointer __upcast() _NOEXCEPT {
    return static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));
  }

  _LIBCPP_HIDE_FROM_ABI size_t __hash() const _NOEXCEPT { return static_cast<__node_type const&>(*this).__hash_; }

  _LIBCPP_HIDE_FROM_ABI __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
  _LIBCPP_HIDE_FROM_ABI explicit __hash_node_base(__next_pointer __next) _NOEXCEPT : __next_(__next) {}
};

template <class _Tp, class _VoidPtr>
struct __hash_node : public __hash_node_base< __rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > > {
  typedef _Tp __node_value_type;
  using _Base          = __hash_node_base<__rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > >;
  using __next_pointer = typename _Base::__next_pointer;

  size_t __hash_;

  // We allow starting the lifetime of nodes without initializing the value held by the node,
  // since that is handled by the hash table itself in order to be allocator-aware.
#ifndef _LIBCPP_CXX03_LANG

private:
  union {
    _Tp __value_;
  };

public:
  _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
#else

private:
  _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];

public:
  _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
#endif

  _LIBCPP_HIDE_FROM_ABI explicit __hash_node(__next_pointer __next, size_t __hash) : _Base(__next), __hash_(__hash) {}
  _LIBCPP_HIDE_FROM_ABI ~__hash_node() {}
};

inline _LIBCPP_HIDE_FROM_ABI bool __is_hash_power2(size_t __bc) { return __bc > 2 && !(__bc & (__bc - 1)); }

inline _LIBCPP_HIDE_FROM_ABI size_t __constrain_hash(size_t __h, size_t __bc) {
  return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : (__h < __bc ? __h : __h % __bc);
}

inline _LIBCPP_HIDE_FROM_ABI size_t __next_hash_pow2(size_t __n) {
  return __n < 2 ? __n : (size_t(1) << (numeric_limits<size_t>::digits - __libcpp_clz(__n - 1)));
}

template <class _Tp, class _Hash, class _Equal, class _Alloc>
class __hash_table;

template <class _NodePtr>
class _LIBCPP_TEMPLATE_VIS __hash_iterator;
template <class _ConstNodePtr>
class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
template <class _NodePtr>
class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
template <class _ConstNodePtr>
class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
template <class _HashIterator>
class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
template <class _HashIterator>
class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;

template <class _Tp>
struct __hash_key_value_types {
  static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
  typedef _Tp key_type;
  typedef _Tp __node_value_type;
  typedef _Tp __container_value_type;
  static const bool __is_map = false;

  _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(_Tp const& __v) { return __v; }
  _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(__node_value_type const& __v) { return __v; }
  _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) { return std::addressof(__n); }
  _LIBCPP_HIDE_FROM_ABI static __container_value_type&& __move(__node_value_type& __v) { return std::move(__v); }
};

template <class _Key, class _Tp>
struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
  typedef _Key key_type;
  typedef _Tp mapped_type;
  typedef __hash_value_type<_Key, _Tp> __node_value_type;
  typedef pair<const _Key, _Tp> __container_value_type;
  typedef __container_value_type __map_value_type;
  static const bool __is_map = true;

  _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(__container_value_type const& __v) { return __v.first; }

  template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __node_value_type>::value, int> = 0>
  _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {
    return __t.__get_value();
  }

  template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, int> = 0>
  _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {
    return __t;
  }

  _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) {
    return std::addressof(__n.__get_value());
  }
  _LIBCPP_HIDE_FROM_ABI static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { return __v.__move(); }
};

template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>, bool = _KVTypes::__is_map>
struct __hash_map_pointer_types {};

template <class _Tp, class _AllocPtr, class _KVTypes>
struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
  typedef typename _KVTypes::__map_value_type _Mv;
  typedef __rebind_pointer_t<_AllocPtr, _Mv> __map_value_type_pointer;
  typedef __rebind_pointer_t<_AllocPtr, const _Mv> __const_map_value_type_pointer;
};

template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
struct __hash_node_types;

template <class _NodePtr, class _Tp, class _VoidPtr>
struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
    : public __hash_key_value_types<_Tp>,
      __hash_map_pointer_types<_Tp, _VoidPtr>

{
  typedef __hash_key_value_types<_Tp> __base;

public:
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;

  typedef __rebind_pointer_t<_NodePtr, void> __void_pointer;

  typedef typename pointer_traits<_NodePtr>::element_type __node_type;
  typedef _NodePtr __node_pointer;

  typedef __hash_node_base<__node_pointer> __node_base_type;
  typedef __rebind_pointer_t<_NodePtr, __node_base_type> __node_base_pointer;

  typedef typename __node_base_type::__next_pointer __next_pointer;

  typedef _Tp __node_value_type;
  typedef __rebind_pointer_t<_VoidPtr, __node_value_type> __node_value_type_pointer;
  typedef __rebind_pointer_t<_VoidPtr, const __node_value_type> __const_node_value_type_pointer;

private:
  static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const");
  static_assert(is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value,
                "_VoidPtr does not point to unqualified void type");
  static_assert(is_same<__rebind_pointer_t<_VoidPtr, __node_type>, _NodePtr>::value,
                "_VoidPtr does not rebind to _NodePtr.");
};

template <class _HashIterator>
struct __hash_node_types_from_iterator;
template <class _NodePtr>
struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
template <class _NodePtr>
struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
template <class _NodePtr>
struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
template <class _NodePtr>
struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};

template <class _NodeValueTp, class _VoidPtr>
struct __make_hash_node_types {
  typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
  typedef __rebind_pointer_t<_VoidPtr, _NodeTp> _NodePtr;
  typedef __hash_node_types<_NodePtr> type;
};

template <class _NodePtr>
class _LIBCPP_TEMPLATE_VIS __hash_iterator {
  typedef __hash_node_types<_NodePtr> _NodeTypes;
  typedef _NodePtr __node_pointer;
  typedef typename _NodeTypes::__next_pointer __next_pointer;

  __next_pointer __node_;

public:
  typedef forward_iterator_tag iterator_category;
  typedef typename _NodeTypes::__node_value_type value_type;
  typedef typename _NodeTypes::difference_type difference_type;
  typedef value_type& reference;
  typedef typename _NodeTypes::__node_value_type_pointer pointer;

  _LIBCPP_HIDE_FROM_ABI __hash_iterator() _NOEXCEPT : __node_(nullptr) {}

  _LIBCPP_HIDE_FROM_ABI reference operator*() const {
    _LIBCPP_ASSERT_NON_NULL(
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");
    return __node_->__upcast()->__get_value();
  }

  _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
    _LIBCPP_ASSERT_NON_NULL(
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");
    return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
  }

  _LIBCPP_HIDE_FROM_ABI __hash_iterator& operator++() {
    _LIBCPP_ASSERT_NON_NULL(
        __node_ != nullptr, "Attempted to increment a non-incrementable unordered container iterator");
    __node_ = __node_->__next_;
    return *this;
  }

  _LIBCPP_HIDE_FROM_ABI __hash_iterator operator++(int) {
    __hash_iterator __t(*this);
    ++(*this);
    return __t;
  }

  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) {
    return __x.__node_ == __y.__node_;
  }
  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) {
    return !(__x == __y);
  }

private:
  _LIBCPP_HIDE_FROM_ABI explicit __hash_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}

  template <class, class, class, class>
  friend class __hash_table;
  template <class>
  friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
  template <class>
  friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
  template <class, class, class, class, class>
  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
  template <class, class, class, class, class>
  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
};

template <class _NodePtr>
class _LIBCPP_TEMPLATE_VIS __hash_const_iterator {
  static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
  typedef __hash_node_types<_NodePtr> _NodeTypes;
  typedef _NodePtr __node_pointer;
  typedef typename _NodeTypes::__next_pointer __next_pointer;

  __next_pointer __node_;

public:
  typedef __hash_iterator<_NodePtr> __non_const_iterator;

  typedef forward_iterator_tag iterator_category;
  typedef typename _NodeTypes::__node_value_type value_type;
  typedef typename _NodeTypes::difference_type difference_type;
  typedef const value_type& reference;
  typedef typename _NodeTypes::__const_node_value_type_pointer pointer;

  _LIBCPP_HIDE_FROM_ABI __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {}

  _LIBCPP_HIDE_FROM_ABI __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT : __node_(__x.__node_) {}

  _LIBCPP_HIDE_FROM_ABI reference operator*() const {
    _LIBCPP_ASSERT_NON_NULL(
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");
    return __node_->__upcast()->__get_value();
  }
  _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
    _LIBCPP_ASSERT_NON_NULL(
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");
    return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
  }

  _LIBCPP_HIDE_FROM_ABI __hash_const_iterator& operator++() {
    _LIBCPP_ASSERT_NON_NULL(
        __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_iterator");
    __node_ = __node_->__next_;
    return *this;
  }

  _LIBCPP_HIDE_FROM_ABI __hash_const_iterator operator++(int) {
    __hash_const_iterator __t(*this);
    ++(*this);
    return __t;
  }

  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {
    return __x.__node_ == __y.__node_;
  }
  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {
    return !(__x == __y);
  }

private:
  _LIBCPP_HIDE_FROM_ABI explicit __hash_const_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}

  template <class, class, class, class>
  friend class __hash_table;
  template <class>
  friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
  template <class, class, class, class, class>
  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
  template <class, class, class, class, class>
  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
};

template <class _NodePtr>
class _LIBCPP_TEMPLATE_VIS __hash_local_iterator {
  typedef __hash_node_types<_NodePtr> _NodeTypes;
  typedef _NodePtr __node_pointer;
  typedef typename _NodeTypes::__next_pointer __next_pointer;

  __next_pointer __node_;
  size_t __bucket_;
  size_t __bucket_count_;

public:
  typedef forward_iterator_tag iterator_category;
  typedef typename _NodeTypes::__node_value_type value_type;
  typedef typename _NodeTypes::difference_type difference_type;
  typedef value_type& reference;
  typedef typename _NodeTypes::__node_value_type_pointer pointer;

  _LIBCPP_HIDE_FROM_ABI __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {}

  _LIBCPP_HIDE_FROM_ABI reference operator*() const {
    _LIBCPP_ASSERT_NON_NULL(
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");
    return __node_->__upcast()->__get_value();
  }

  _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
    _LIBCPP_ASSERT_NON_NULL(
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");
    return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
  }

  _LIBCPP_HIDE_FROM_ABI __hash_local_iterator& operator++() {
    _LIBCPP_ASSERT_NON_NULL(
        __node_ != nullptr, "Attempted to increment a non-incrementable unordered container local_iterator");
    __node_ = __node_->__next_;
    if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
      __node_ = nullptr;
    return *this;
  }

  _LIBCPP_HIDE_FROM_ABI __hash_local_iterator operator++(int) {
    __hash_local_iterator __t(*this);
    ++(*this);
    return __t;
  }

  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {
    return __x.__node_ == __y.__node_;
  }
  friend _LIBCPP_HIDE_FROM                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       