// Random number extensions -*- C++ -*-

// Copyright (C) 2012-2018 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/>.

/** @file ext/random
 *  This file is a GNU extension to the Standard C++ Library.
 */

#ifndef _EXT_RANDOM
#define _EXT_RANDOM 1

#pragma GCC system_header

#if __cplusplus < 201103L
# include <bits/c++0x_warning.h>
#else

#include <random>
#include <algorithm>
#include <array>
#include <ext/cmath>
#ifdef __SSE2__
# include <emmintrin.h>
#endif

#if defined(_GLIBCXX_USE_C99_STDINT_TR1) && defined(UINT32_C)

namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__

  /* Mersenne twister implementation optimized for vector operations.
   *
   * Reference: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/
   */
  template<typename _UIntType, size_t __m,
	   size_t __pos1, size_t __sl1, size_t __sl2,
	   size_t __sr1, size_t __sr2,
	   uint32_t __msk1, uint32_t __msk2,
	   uint32_t __msk3, uint32_t __msk4,
	   uint32_t __parity1, uint32_t __parity2,
	   uint32_t __parity3, uint32_t __parity4>
    class simd_fast_mersenne_twister_engine
    {
      static_assert(std::is_unsigned<_UIntType>::value, "template argument "
		    "substituting _UIntType not an unsigned integral type");
      static_assert(__sr1 < 32, "first right shift too large");
      static_assert(__sr2 < 16, "second right shift too large");
      static_assert(__sl1 < 32, "first left shift too large");
      static_assert(__sl2 < 16, "second left shift too large");

    public:
      typedef _UIntType result_type;

    private:
      static constexpr size_t m_w = sizeof(result_type) * 8;
      static constexpr size_t _M_nstate = __m / 128 + 1;
      static constexpr size_t _M_nstate32 = _M_nstate * 4;

      static_assert(std::is_unsigned<_UIntType>::value, "template argument "
		    "substituting _UIntType not an unsigned integral type");
      static_assert(__pos1 < _M_nstate, "POS1 not smaller than state size");
      static_assert(16 % sizeof(_UIntType) == 0,
		    "UIntType size must divide 16");

    public:
      static constexpr size_t state_size = _M_nstate * (16
							/ sizeof(result_type));
      static constexpr result_type default_seed = 5489u;

      // constructors and member function
      explicit
      simd_fast_mersenne_twister_engine(result_type __sd = default_seed)
      { seed(__sd); }

      template<typename _Sseq, typename = typename
	std::enable_if<!std::is_same<_Sseq,
				     simd_fast_mersenne_twister_engine>::value>
	       ::type>
	explicit
	simd_fast_mersenne_twister_engine(_Sseq& __q)
	{ seed(__q); }

      void
      seed(result_type __sd = default_seed);

      template<typename _Sseq>
	typename std::enable_if<std::is_class<_Sseq>::value>::type
	seed(_Sseq& __q);

      static constexpr result_type
      min()
      { return 0; }

      static constexpr result_type
      max()
      { return std::numeric_limits<result_type>::max(); }

      void
      discard(unsigned long long __z);

      result_type
      operator()()
      {
	if (__builtin_expect(_M_pos >= state_size, 0))
	  _M_gen_rand();

	return _M_stateT[_M_pos++];
      }

      template<typename _UIntType_2, size_t __m_2,
	       size_t __pos1_2, size_t __sl1_2, size_t __sl2_2,
	       size_t __sr1_2, size_t __sr2_2,
	       uint32_t __msk1_2, uint32_t __msk2_2,
	       uint32_t __msk3_2, uint32_t __msk4_2,
	       uint32_t __parity1_2, uint32_t __parity2_2,
	       uint32_t __parity3_2, uint32_t __parity4_2>
	friend bool
	operator==(const simd_fast_mersenne_twister_engine<_UIntType_2,
		   __m_2, __pos1_2, __sl1_2, __sl2_2, __sr1_2, __sr2_2,
		   __msk1_2, __msk2_2, __msk3_2, __msk4_2,
		   __parity1_2, __parity2_2, __parity3_2, __parity4_2>& __lhs,
		   const simd_fast_mersenne_twister_engine<_UIntType_2,
		   __m_2, __pos1_2, __sl1_2, __sl2_2, __sr1_2, __sr2_2,
		   __msk1_2, __msk2_2, __msk3_2, __msk4_2,
		   __parity1_2, __parity2_2, __parity3_2, __parity4_2>& __rhs);

      template<typename _UIntType_2, size_t __m_2,
	       size_t __pos1_2, size_t __sl1_2, size_t __sl2_2,
	       size_t __sr1_2, size_t __sr2_2,
	       uint32_t __msk1_2, uint32_t __msk2_2,
	       uint32_t __msk3_2, uint32_t __msk4_2,
	       uint32_t __parity1_2, uint32_t __parity2_2,
	       uint32_t __parity3_2, uint32_t __parity4_2,
	       typename _CharT, typename _Traits>
	friend std::basic_ostream<_CharT, _Traits>&
	operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		   const __gnu_cxx::simd_fast_mersenne_twister_engine
		   <_UIntType_2,
		   __m_2, __pos1_2, __sl1_2, __sl2_2, __sr1_2, __sr2_2,
		   __msk1_2, __msk2_2, __msk3_2, __msk4_2,
		   __parity1_2, __parity2_2, __parity3_2, __parity4_2>& __x);

      template<typename _UIntType_2, size_t __m_2,
	       size_t __pos1_2, size_t __sl1_2, size_t __sl2_2,
	       size_t __sr1_2, size_t __sr2_2,
	       uint32_t __msk1_2, uint32_t __msk2_2,
	       uint32_t __msk3_2, uint32_t __msk4_2,
	       uint32_t __parity1_2, uint32_t __parity2_2,
	       uint32_t __parity3_2, uint32_t __parity4_2,
	       typename _CharT, typename _Traits>
	friend std::basic_istream<_CharT, _Traits>&
	operator>>(std::basic_istream<_CharT, _Traits>& __is,
		   __gnu_cxx::simd_fast_mersenne_twister_engine<_UIntType_2,
		   __m_2, __pos1_2, __sl1_2, __sl2_2, __sr1_2, __sr2_2,
		   __msk1_2, __msk2_2, __msk3_2, __msk4_2,
		   __parity1_2, __parity2_2, __parity3_2, __parity4_2>& __x);

    private:
      union
      {
#ifdef __SSE2__
	__m128i _M_state[_M_nstate];
#endif
#ifdef __ARM_NEON
#ifdef __aarch64__
	__Uint32x4_t _M_state[_M_nstate];
#endif
#endif
	uint32_t _M_state32[_M_nstate32];
	result_type _M_stateT[state_size];
      } __attribute__ ((__aligned__ (16)));
      size_t _M_pos;

      void _M_gen_rand(void);
      void _M_period_certification();
  };


  template<typename _UIntType, size_t __m,
	   size_t __pos1, size_t __sl1, size_t __sl2,
	   size_t __sr1, size_t __sr2,
	   uint32_t __msk1, uint32_t __msk2,
	   uint32_t __msk3, uint32_t __msk4,
	   uint32_t __parity1, uint32_t __parity2,
	   uint32_t __parity3, uint32_t __parity4>
    inline bool
    operator!=(const __gnu_cxx::simd_fast_mersenne_twister_engine<_UIntType,
	       __m, __pos1, __sl1, __sl2, __sr1, __sr2, __msk1, __msk2, __msk3,
	       __msk4, __parity1, __parity2, __parity3, __parity4>& __lhs,
	       const __gnu_cxx::simd_fast_mersenne_twister_engine<_UIntType,
	       __m, __pos1, __sl1, __sl2, __sr1, __sr2, __msk1, __msk2, __msk3,
	       __msk4, __parity1, __parity2, __parity3, __parity4>& __rhs)
    { return !(__lhs == __rhs); }


  /* Definitions for the SIMD-oriented Fast Mersenne Twister as defined
   * in the C implementation by Daito and Matsumoto, as both a 32-bit
   * and 64-bit version.
   */
  typedef simd_fast_mersenne_twister_engine<uint32_t, 607, 2,
					    15, 3, 13, 3,
					    0xfdff37ffU, 0xef7f3f7dU,
					    0xff777b7dU, 0x7ff7fb2fU,
					    0x00000001U, 0x00000000U,
					    0x00000000U, 0x5986f054U>
    sfmt607;

  typedef simd_fast_mersenne_twister_engine<uint64_t, 607, 2,
					    15, 3, 13, 3,
					    0xfdff37ffU, 0xef7f3f7dU,
					    0xff777b7dU, 0x7ff7fb2fU,
					    0x00000001U, 0x00000000U,
					    0x00000000U, 0x5986f054U>
    sfmt607_64;


  typedef simd_fast_mersenne_twister_engine<uint32_t, 1279, 7,
					    14, 3, 5, 1,
					    0xf7fefffdU, 0x7fefcfffU,
					    0xaff3ef3fU, 0xb5ffff7fU,
					    0x00000001U, 0x00000000U,
					    0x00000000U, 0x20000000U>
    sfmt1279;

  typedef simd_fast_mersenne_twister_engine<uint64_t, 1279, 7,
					    14, 3, 5, 1,
					    0xf7fefffdU, 0x7fefcfffU,
					    0xaff3ef3fU, 0xb5ffff7fU,
					    0x00000001U, 0x00000000U,
					    0x00000000U, 0x20000000U>
    sfmt1279_64;


  typedef simd_fast_mersenne_twister_engine<uint32_t, 2281, 12,
					    19, 1, 5, 1,
					    0xbff7ffbfU, 0xfdfffffeU,
					    0xf7ffef7fU, 0xf2f7cbbfU,
					    0x00000001U, 0x00000000U,
					    0x00000000U, 0x41dfa600U>
    sfmt2281;

  typedef simd_fast_mersenne_twister_engine<uint64_t, 2281, 12,
					    19, 1, 5, 1,
					    0xbff7ffbfU, 0xfdfffffeU,
					    0xf7ffef7fU, 0xf2f7cbbfU,
					    0x00000001U, 0x00000000U,
					    0x00000000U, 0x41dfa600U>
    sfmt2281_64;


  typedef simd_fast_mersenne_twi                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   