// -*- C++ -*-
//===-------------------------- locale ------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is dual licensed under the MIT and the University of Illinois Open
// Source Licenses. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_LOCALE
#define _LIBCPP_LOCALE

/*
    locale synopsis

namespace std
{

class locale
{
public:
    // types:
    class facet;
    class id;

    typedef int category;
    static const category // values assigned here are for exposition only
        none     = 0x000,
        collate  = 0x010,
        ctype    = 0x020,
        monetary = 0x040,
        numeric  = 0x080,
        time     = 0x100,
        messages = 0x200,
        all = collate | ctype | monetary | numeric | time | messages;

    // construct/copy/destroy:
    locale() noexcept;
    locale(const locale& other) noexcept;
    explicit locale(const char* std_name);
    explicit locale(const string& std_name);
    locale(const locale& other, const char* std_name, category);
    locale(const locale& other, const string& std_name, category);
    template <class Facet> locale(const locale& other, Facet* f);
    locale(const locale& other, const locale& one, category);

    ~locale(); // not virtual

    const locale& operator=(const locale& other) noexcept;

    template <class Facet> locale combine(const locale& other) const;

    // locale operations:
    basic_string<char> name() const;
    bool operator==(const locale& other) const;
    bool operator!=(const locale& other) const;
    template <class charT, class Traits, class Allocator>
      bool operator()(const basic_string<charT,Traits,Allocator>& s1,
                      const basic_string<charT,Traits,Allocator>& s2) const;

    // global locale objects:
    static locale global(const locale&);
    static const locale& classic();
};

template <class Facet> const Facet& use_facet(const locale&);
template <class Facet> bool has_facet(const locale&) noexcept;

// 22.3.3, convenience interfaces:
template <class charT> bool isspace (charT c, const locale& loc);
template <class charT> bool isprint (charT c, const locale& loc);
template <class charT> bool iscntrl (charT c, const locale& loc);
template <class charT> bool isupper (charT c, const locale& loc);
template <class charT> bool islower (charT c, const locale& loc);
template <class charT> bool isalpha (charT c, const locale& loc);
template <class charT> bool isdigit (charT c, const locale& loc);
template <class charT> bool ispunct (charT c, const locale& loc);
template <class charT> bool isxdigit(charT c, const locale& loc);
template <class charT> bool isalnum (charT c, const locale& loc);
template <class charT> bool isgraph (charT c, const locale& loc);
template <class charT> charT toupper(charT c, const locale& loc);
template <class charT> charT tolower(charT c, const locale& loc);

template<class Codecvt, class Elem = wchar_t,
         class Wide_alloc = allocator<Elem>,
         class Byte_alloc = allocator<char>>
class wstring_convert
{
public:
    typedef basic_string<char, char_traits<char>, Byte_alloc> byte_string;
    typedef basic_string<Elem, char_traits<Elem>, Wide_alloc> wide_string;
    typedef typename Codecvt::state_type                      state_type;
    typedef typename wide_string::traits_type::int_type       int_type;

    explicit wstring_convert(Codecvt* pcvt = new Codecvt);          // explicit in C++14
    wstring_convert(Codecvt* pcvt, state_type state);
    explicit wstring_convert(const byte_string& byte_err,           // explicit in C++14
                    const wide_string& wide_err = wide_string());
    wstring_convert(const wstring_convert&) = delete;               // C++14
    wstring_convert & operator=(const wstring_convert &) = delete;  // C++14
    ~wstring_convert();

    wide_string from_bytes(char byte);
    wide_string from_bytes(const char* ptr);
    wide_string from_bytes(const byte_string& str);
    wide_string from_bytes(const char* first, const char* last);

    byte_string to_bytes(Elem wchar);
    byte_string to_bytes(const Elem* wptr);
    byte_string to_bytes(const wide_string& wstr);
    byte_string to_bytes(const Elem* first, const Elem* last);

    size_t converted() const; // noexcept in C++14
    state_type state() const;
};

template <class Codecvt, class Elem = wchar_t, class Tr = char_traits<Elem>>
class wbuffer_convert
    : public basic_streambuf<Elem, Tr>
{
public:
    typedef typename Tr::state_type state_type;

    explicit wbuffer_convert(streambuf* bytebuf = 0, Codecvt* pcvt = new Codecvt,
                    state_type state = state_type());       // explicit in C++14
    wbuffer_convert(const wbuffer_convert&) = delete;               // C++14
    wbuffer_convert & operator=(const wbuffer_convert &) = delete;  // C++14
    ~wbuffer_convert();                                             // C++14
    
    streambuf* rdbuf() const;
    streambuf* rdbuf(streambuf* bytebuf);

    state_type state() const;
};

// 22.4.1 and 22.4.1.3, ctype:
class ctype_base;
template <class charT> class ctype;
template <> class ctype<char>; // specialization
template <class charT> class ctype_byname;
template <> class ctype_byname<char>; // specialization

class codecvt_base;
template <class internT, class externT, class stateT> class codecvt;
template <class internT, class externT, class stateT> class codecvt_byname;

// 22.4.2 and 22.4.3, numeric:
template <class charT, class InputIterator> class num_get;
template <class charT, class OutputIterator> class num_put;
template <class charT> class numpunct;
template <class charT> class numpunct_byname;

// 22.4.4, col lation:
template <class charT> class collate;
template <class charT> class collate_byname;

// 22.4.5, date and time:
class time_base;
template <class charT, class InputIterator> class time_get;
template <class charT, class InputIterator> class time_get_byname;
template <class charT, class OutputIterator> class time_put;
template <class charT, class OutputIterator> class time_put_byname;

// 22.4.6, money:
class money_base;
template <class charT, class InputIterator> class money_get;
template <class charT, class OutputIterator> class money_put;
template <class charT, bool Intl> class moneypunct;
template <class charT, bool Intl> class moneypunct_byname;

// 22.4.7, message retrieval:
class messages_base;
template <class charT> class messages;
template <class charT> class messages_byname;

}  // std

*/

#include <__config>
#include <__locale>
#include <__debug>
#include <algorithm>
#include <memory>
#include <ios>
#include <streambuf>
#include <iterator>
#include <limits>
#ifndef __APPLE__
#include <cstdarg>
#endif
#include <cstdlib>
#include <ctime>
#include <cstdio>
#ifdef _LIBCPP_HAS_CATOPEN
#include <nl_types.h>
#endif

#ifdef __APPLE__
#include <Availability.h>
#endif

#ifdef _LIBCPP_LOCALE__L_EXTENSIONS
#include <__bsd_locale_defaults.h>
#else
#include <__bsd_locale_fallbacks.h>
#endif

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

_LIBCPP_PUSH_MACROS
#include <__undef_macros>


_LIBCPP_BEGIN_NAMESPACE_STD

#if defined(__APPLE__) || defined(__FreeBSD__)
#  define _LIBCPP_GET_C_LOCALE 0
#elif defined(__CloudABI__) || defined(__NetBSD__)
#  define _LIBCPP_GET_C_LOCALE LC_C_LOCALE
#else
#  define _LIBCPP_GET_C_LOCALE __cloc()
   // Get the C locale object
   _LIBCPP_FUNC_VIS locale_t __cloc();
#define __cloc_defined
#endif

// __scan_keyword
// Scans [__b, __e) until a match is found in the basic_strings range
//  [__kb, __ke) or until it can be shown that there is no match in [__kb, __ke).
//  __b will be incremented (visibly), consuming CharT until a match is found
//  or proved to not exist.  A keyword may be "", in which will match anything.
//  If one keyword is a prefix of another, and the next CharT in the input
//  might match another keyword, the algorithm will attempt to find the longest
//  matching keyword.  If the longer matching keyword ends up not matching, then
//  no keyword match is found.  If no keyword match is found, __ke is returned
//  and failbit is set in __err.
//  Else an iterator pointing to the matching keyword is found.  If more than
//  one keyword matches, an iterator to the first matching keyword is returned.
//  If on exit __b == __e, eofbit is set in __err.  If __case_sensitive is false,
//  __ct is used to force to lower case before comparing characters.
//  Examples:
//  Keywords:  "a", "abb"
//  If the input is "a", the first keyword matches and eofbit is set.
//  If the input is "abc", no match is found and "ab" are consumed.
template <class _InputIterator, class _ForwardIterator, class _Ctype>
_LIBCPP_HIDDEN
_ForwardIterator
__scan_keyword(_InputIterator& __b, _InputIterator __e,
               _ForwardIterator __kb, _ForwardIterator __ke,
               const _Ctype& __ct, ios_base::iostate& __err,
               bool __case_sensitive = true)
{
    typedef typename iterator_traits<_InputIterator>::value_type _CharT;
    size_t __nkw = static_cast<size_t>(_VSTD::distance(__kb, __ke));
    const unsigned char __doesnt_match = '\0';
    const unsigned char __might_match = '\1';
    const unsigned char __does_match = '\2';
    unsigned char __statbuf[100];
    unsigned char* __status = __statbuf;
    unique_ptr<unsigned char, void(*)(void*)> __stat_hold(0, free);
    if (__nkw > sizeof(__statbuf))
    {
        __status = (unsigned char*)malloc(__nkw);
        if (__status == 0)
            __throw_bad_alloc();
        __stat_hold.reset(__status);
    }
    size_t __n_might_match = __nkw;  // At this point, any keyword might match
    size_t __n_does_match = 0;       // but none of them definitely do
    // Initialize all statuses to __might_match, except for "" keywords are __does_match
    unsigned char* __st = __status;
    for (_ForwardIterator __ky = __kb; __ky != __ke; ++__ky, (void) ++__st)
    {
        if (!__ky->empty())
            *__st = __might_match;
        else
        {
            *__st = __does_match;
            --__n_might_match;
            ++__n_does_match;
        }
    }
    // While there might be a match, test keywords against the next CharT
    for (size_t __indx = 0; __b != __e && __n_might_match > 0; ++__indx)
    {
        // Peek at the next CharT but don't consume it
        _CharT __c = *__b;
        if (!__case_sensitive)
            __c = __ct.toupper(__c);
        bool __consume = false;
        // For each keyword which might match, see if the __indx character is __c
        // If a match if found, consume __c
        // If a match is found, and that is the last character in the keyword,
        //    then that keyword matches.
        // If the keyword doesn't match this character, then change the keyword
        //    to doesn't match
        __st = __status;
        for (_ForwardIterator __ky = __kb; __ky != __ke; ++__ky, (void) ++__st)
        {
            if (*__st == __might_match)
            {
                _CharT __kc = (*__ky)[__indx];
                if (!__case_sensitive)
                    __kc = __ct.toupper(__kc);
                if (__c == __kc)
                {
                    __consume = true;
                    if (__ky->size() == __indx+1)
                    {
                        *__st = __does_match;
                        --__n_might_match;
                        ++__n_does_match;
                    }
                }
                else
                {
                    *__st = __doesnt_match;
                    --__n_might_match;
                }
            }
        }
        // consume if we matched a character
        if (__consume)
        {
            ++__b;
            // If we consumed a character and there might be a matched keyword that
            //   was marked matched on a previous iteration, then such keywords
            //   which are now marked as not matching.
            if (__n_might_match + __n_does_match > 1)
            {
                __st = __status;
                for (_ForwardIterator __ky = __kb; __ky != __ke; ++__ky, (void) ++__st)
                {
                    if (*__st == __does_match && __ky->size() != __indx+1)
                    {
                        *__st = __doesnt_match;
                        --__n_does_match;
                    }
                }
            }
        }
    }
    // We've exited the loop because we hit eof and/or we have no more "might matches".
    if (__b == __e)
        __err |= ios_base::eofbit;
    // Return the first matching result
    for (__st = __status; __kb != __ke; ++__kb, (void) ++__st)
        if (*__st == __does_match)
            break;
    if (__kb == __ke)
        __err |= ios_base::failbit;
    return __kb;
}

struct _LIBCPP_TYPE_VIS __num_get_base
{
    static const int __num_get_buf_sz = 40;

    static int __get_base(ios_base&);
    static const char __src[33];
};

_LIBCPP_FUNC_VIS
void __check_grouping(const string& __grouping, unsigned* __g, unsigned* __g_end,
                      ios_base::iostate& __err);

template <class _CharT>
struct __num_get
    : protected __num_get_base
{
    static string __stage2_float_prep(ios_base& __iob, _CharT* __atoms, _CharT& __decimal_point,
                                      _CharT& __thousands_sep);

    static int __stage2_float_loop(_CharT __ct, bool& __in_units, char& __exp,
                                   char* __a, char*& __a_end,
                                   _CharT __decimal_point, _CharT __thousands_sep,
                                   const string& __grouping, unsigned* __g,
                                   unsigned*& __g_end, unsigned& __dc, _CharT* __atoms);
#ifndef _LIBCPP_ABI_OPTIMIZED_LOCALE_NUM_GET
    static string __stage2_int_prep(ios_base& __iob, _CharT* __atoms, _CharT& __thousands_sep);
    static int __stage2_int_loop(_CharT __ct, int __base, char* __a, char*& __a_end,
                  unsigned& __dc, _CharT __thousands_sep, const string& __grouping,
                  unsigned* __g, unsigned*& __g_end, _CharT* __atoms);

#else
    static string __stage2_int_prep(ios_base& __iob, _CharT& __thousands_sep)
    {
        locale __loc = __iob.getloc();
        const numpunct<_CharT>& __np = use_facet<numpunct<_CharT> >(__loc);
        __thousands_sep = __np.thousands_sep();
        return __np.grouping();
    }

    const _CharT* __do_widen(ios_base& __iob, _CharT* __atoms) const
    {
      return __do_widen_p(__iob, __atoms);
    }


    static int __stage2_int_loop(_CharT __ct, int __base, char* __a, char*& __a_end,
                  unsigned& __dc, _CharT __thousands_sep, const string& __grouping,
                  unsigned* __g, unsigned*& __g_end, const _CharT* __atoms);
private:
    template<typename T>
    const T* __do_widen_p(ios_base& __iob, T* __atoms) const
    {
      locale __loc = __iob.getloc();
      use_facet<ctype<T> >(__loc).widen(__src, __src + 26, __atoms);
      return __atoms;
    }

    const char* __do_widen_p(ios_base& __iob, char* __atoms) const
    {
      (void)__iob;
      (void)__atoms;
      return __src;
    }
#endif
};

#ifndef _LIBCPP_ABI_OPTIMIZED_LOCALE_NUM_GET
template <class _CharT>
string
__num_get<_CharT>::__stage2_int_prep(ios_base& __iob, _CharT* __atoms, _CharT& __thousands_sep)
{
    locale __loc = __iob.getloc();
    use_facet<ctype<_CharT> >(__loc).widen(__src, __src + 26, __atoms);
    const numpunct<_CharT>& __np = use_facet<numpunct<_CharT> >(__loc);
    __thousands_sep = __np.thousands_sep();
    return __np.grouping();
}
#endif

template <class _CharT>
string
__num_get<_CharT>::__stage2_float_prep(ios_base& __iob, _CharT* __atoms, _CharT& __decimal_point,
                    _CharT& __thousands_sep)
{
    locale __loc = __iob.getloc();
    use_facet<ctype<_CharT> >(__loc).widen(__src, __src + 32, __atoms);
    const numpunct<_CharT>& __np = use_facet<numpunct<_CharT> >(__loc);
    __decimal_point = __np.decimal_point();
    __thousands_sep = __np.thousands_sep();
    return __np.grouping();
}

template <class _CharT>
int
#ifndef _LIBCPP_ABI_OPTIMIZED_LOCALE_NUM_GET
__num_get<_CharT>::__stage2_int_loop(_CharT __ct, int __base, char* __a, char*& __a_end,
                  unsigned& __dc, _CharT __thousands_sep, const string& __grouping,
                  unsigned* __g, unsigned*& __g_end, _CharT* __atoms)
#else
__num_get<_CharT>::__stage2_int_loop(_CharT __ct, int __base, char* __a, char*& __a_end,
                  unsigned& __dc, _CharT __thousands_sep, const string& __grouping,
                  unsigned* __g, unsigned*& __g_end, const _CharT* __atoms)

#endif
{
    if (__a_end == __a && (__ct == __atoms[24] || __ct == __atoms[25]))
    {
        *__a_end++ = __ct == __atoms[24] ? '+' : '-';
        __dc = 0;
        return 0;
    }
    if (__grouping.size() != 0 && __ct == __thousands_sep)
    {
        if (__g_end-__g < __num_get_buf_sz)
        {
            *__g_end++ = __dc;
            __dc = 0;
        }
        return 0;
    }
    ptrdiff_t __f = find(__atoms, __atoms + 26, __ct) - __atoms;
    if (__f >= 24)
        return -1;
    switch (__base)
    {
    case 8:
    case 10:
        if (__f >= __base)
            return -1;
        break;
    case 16:
        if (__f < 22)
            break;
        if (__a_end != __a && __a_end - __a <= 2 && __a_end[-1] == '0')
        {
            __dc = 0;
            *__a_end++ = __src[__f];
            return 0;
        }
        return -1;
    }
    *__a_end++ = __src[__f];
    ++__dc;
    return 0;
}

template <class _CharT>
int
__num_get<_CharT>::__stage2_float_loop(_CharT __ct, bool& __in_units, char& __exp, char* __a, char*& __a_end,
                    _CharT __decimal_point, _CharT __thousands_sep, const string& __grouping,
                    unsigned* __g, unsigned*& __g_end, unsigned& __dc, _CharT* __atoms)
{
    if (__ct == __decimal_point)
    {
        if (!__in_units)
            return -1;
        __in_units = false;
        *__a_end++ = '.';
        if (__grouping.size() != 0 && __g_end-__g < __num_get_buf_sz)
            *__g_end++ = __dc;
        return 0;
    }
    if (__ct == __thousands_sep && __grouping.size() != 0)
    {
        if (!__in_units)
            return -1;
        if (__g_end-__g < __num_get_buf_sz)
        {
            *__g_end++ = __dc;
            __dc = 0;
        }
        return 0;
    }
    ptrdiff_t __f = find(__atoms, __atoms + 32, __ct) - __atoms;
    if (__f >= 32)
        return -1;
    char __x = __src[__f];
    if (__x == '-' || __x == '+')
    {
        if (__a_end == __a || (__a_end[-1] & 0x5F) == (__exp & 0x7F))
        {
            *__a_end++ = __x;
            return 0;
        }
        return -1;
    }
    if (__x == 'x' || __x == 'X')
        __exp = 'P';
    else if ((__x & 0x5F) == __exp)
    {
        __exp |= 0x80;
        if (__in_units)
        {
            __in_units = false;
            if (__grouping.size() != 0 && __g_end-__g < __num_get_buf_sz)
                *__g_end++ = __dc;
        }
    }
    *__a_end++ = __x;
    if (__f >= 22)
        return 0;
    ++__dc;
    return 0;
}

_LIBCPP_EXTERN_TEMPLATE2(struct _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __num_get<char>)
_LIBCPP_EXTERN_TEMPLATE2(struct _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __num_get<wchar_t>)

template <class _CharT, class _InputIterator = istreambuf_iterator<_CharT> >
class _LIBCPP_TEMPLATE_VIS num_get
    : public locale::facet,
      private __num_get<_CharT>
{
public:
    typedef _CharT char_type;
    typedef _InputIterator iter_type;

    _LIBCPP_INLINE_VISIBILITY
    explicit num_get(size_t __refs = 0)
        : locale::facet(__refs) {}

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, bool& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, long& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, long long& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, unsigned short& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, unsigned int& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, unsigned long& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, unsigned long long& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, float& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, double& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, long double& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type get(iter_type __b, iter_type __e, ios_base& __iob,
                  ios_base::iostate& __err, void*& __v) const
    {
        return do_get(__b, __e, __iob, __err, __v);
    }

    static locale::id id;

protected:
    _LIBCPP_INLINE_VISIBILITY
    ~num_get() {}

    template <class _Fp>
    _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS
    iter_type __do_get_floating_point
                            (iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, _Fp& __v) const;

    template <class _Signed>
    _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS
    iter_type __do_get_signed
                            (iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, _Signed& __v) const;

    template <class _Unsigned>
    _LIBCPP_METHOD_TEMPLATE_IMPLICIT_INSTANTIATION_VIS
    iter_type __do_get_unsigned
                            (iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, _Unsigned& __v) const;


    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, bool& __v) const;

    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, long& __v) const
    { return this->__do_get_signed ( __b, __e, __iob, __err, __v ); }

    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, long long& __v) const
    { return this->__do_get_signed ( __b, __e, __iob, __err, __v ); }

    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, unsigned short& __v) const
    { return this->__do_get_unsigned ( __b, __e, __iob, __err, __v ); }

    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, unsigned int& __v) const
    { return this->__do_get_unsigned ( __b, __e, __iob, __err, __v ); }

    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, unsigned long& __v) const
    { return this->__do_get_unsigned ( __b, __e, __iob, __err, __v ); }

    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, unsigned long long& __v) const
    { return this->__do_get_unsigned ( __b, __e, __iob, __err, __v ); }

    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, float& __v) const
    { return this->__do_get_floating_point ( __b, __e, __iob, __err, __v ); }

    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, double& __v) const
    { return this->__do_get_floating_point ( __b, __e, __iob, __err, __v ); }

    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, long double& __v) const
    { return this->__do_get_floating_point ( __b, __e, __iob, __err, __v ); }

    virtual iter_type do_get(iter_type __b, iter_type __e, ios_base& __iob,
                             ios_base::iostate& __err, void*& __v) const;
};

template <class _CharT, class _InputIterator>
locale::id
num_get<_CharT, _InputIterator>::id;

template <class _Tp>
_Tp
__num_get_signed_integral(const char* __a, const char* __a_end,
                          ios_base::iostate& __err, int __base)
{
    if (__a != __a_end)
    {
        typename remove_reference<decltype(errno)>::type __save_errno = errno;
        errno = 0;
        char *__p2;
        long long __ll = strtoll_l(__a, &__p2, __base, _LIBCPP_GET_C_LOCALE);
        typename remove_reference<decltype(errno)>::type __current_errno = errno;
        if (__current_errno == 0)
            errno = __save_errno;
        if (__p2 != __a_end)
        {
            __err = ios_base::failbit;
            return 0;
        }
        else if (__current_errno == ERANGE         ||
                 __ll < numeric_limits<_Tp>::min() ||
                 numeric_limits<_Tp>::max() < __ll)
        {
            __err = ios_base::failbit;
            if (__ll > 0)
                return numeric_limits<_Tp>::max();
            else
                return numeric_limits<_Tp>::min();
        }
        return static_cast<_Tp>(__ll);
    }
    __err = ios_base::failbit;
    return 0;
}

template <class _Tp>
_Tp
__num_get_unsigned_integral(const char* __a, const char* __a_end,
                            ios_base::iostate& __err, int __base)
{
    if (__a != __a_end)
    {
        const bool __negate = *__a == '-';
        if (__negate && ++__a == __a_end) {
          __err = ios_base::failbit;
          return 0;
        }
        typename remove_reference<decltype(errno)>::type __save_errno = errno;
        errno = 0;
        char *__p2;
        unsigned long long __ll = strtoull_l(__a, &__p2, __base, _LIBCPP_GET_C_LOCALE);
        typename remove_reference<decltype(errno)>::type __current_errno = errno;
        if (__current_errno == 0)
            errno = __save_errno;
        if (__p2 != __a_end)
        {
            __err = ios_base::failbit;
            return 0;
        }
        else if (__current_errno == ERANGE || numeric_limits<_Tp>::max() < __ll)
        {
            __err = ios_base::failbit;
            return numeric_limits<_Tp>::max();
        }
        _Tp __res = static_cast<_Tp>(__ll);
        if (__negate) __res = -__res;
        return __res;
    }
    __err = ios_base::failbit;
    return 0;
}

template <class _Tp>
_LIBCPP_INLINE_VISIBILITY
_Tp __do_strtod(const char* __a, char** __p2);

template <>
inline _LIBCPP_INLINE_VISIBILITY
float __do_strtod<float>(const char* __a, char** __p2) {
    return strtof_l(__a, __p2, _LIBCPP_GET_C_LOCALE);
}

template <>
inline _LIBCPP_INLINE_VISIBILITY
double __do_strtod<double>(const char* __a, char** __p2) {
    return strtod_l(__a, __p2, _LIBCPP_GET_C_LOCALE);
}

template <>
inline _LIBCPP_INLINE_VISIBILITY
long double __do_strtod<long double>(const char* __a, char** __p2) {
    return strtold_l(__a, __p2, _LIBCPP_GET_C_LOCALE);
}

template <class _Tp>
_LIBCPP_HIDDEN
_Tp
__num_get_float(const char* __a, const char* __a_end, ios_base::iostate& __err)
{
    if (__a != __a_end)
    {
        typename remove_reference<decltype(errno)>::type __save_errno = errno;
        errno = 0;
        char *__p2;
        _Tp __ld = __do_strtod<_Tp>(__a, &__p2);
        typename remove_reference<decltype(errno)>::type __current_errno = errno;
        if (__current_errno == 0)
            errno = __save_errno;
        if (__p2 != __a_end)
        {
            __err = ios_base::failbit;
            return 0;
        }
        else if (__current_errno == ERANGE)
            __err = ios_base::failbit;
        return __ld;
    }
    __err = ios_base::failbit;
    return 0;
}

template <class _CharT, class _InputIterator>
_InputIterator
num_get<_CharT, _InputIterator>::do_get(iter_type __b, iter_type __e,
                                        ios_base& __iob,
                                        ios_base::iostate& __err,
                                        bool& __v) const
{
    if ((__iob.flags() & ios_base::boolalpha) == 0)
    {
        long __lv = -1;
        __b = do_get(__b, __e, __iob, __err, __lv);
        switch (__lv)
        {
        case 0:
            __v = false;
            break;
        case 1:
            __v = true;
            break;
        default:
            __v = true;
            __err = ios_base::failbit;
            break;
        }
        return __b;
    }
    const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__iob.getloc());
    const numpunct<_CharT>& __np = use_facet<numpunct<_CharT> >(__iob.getloc());
    typedef typename numpunct<_CharT>::string_type string_type;
    const string_type __names[2] = {__np.truename(), __np.falsename()};
    const string_type* __i = __scan_keyword(__b, __e, __names, __names+2,
                                            __ct, __err);
    __v = __i == __names;
    return __b;
}

// signed

template <class _CharT, class _InputIterator>
template <class _Signed>
_InputIterator
num_get<_CharT, _InputIterator>::__do_get_signed(iter_type __b, iter_type __e,
                                        ios_base& __iob,
                                        ios_base::iostate& __err,
                                        _Signed& __v) const
{
    // Stage 1
    int __base = this->__get_base(__iob);
    // Stage 2
    char_type __thousands_sep;
    const int __atoms_size = 26;
#ifdef _LIBCPP_ABI_OPTIMIZED_LOCALE_NUM_GET
    char_type __atoms1[__atoms_size];
    const char_type *__atoms = this->__do_widen(__iob, __atoms1);
    string __grouping = this->__stage2_int_prep(__iob, __thousands_sep);
#else
    char_type __atoms[__atoms_size];
    string __grouping = this->__stage2_int_prep(__iob, __atoms, __thousands_sep);
#endif
    string __buf;
    __buf.resize(__buf.capacity());
    char* __a = &__buf[0];
    char* __a_end = __a;
    unsigned __g[__num_get_base::__num_get_buf_sz];
    unsigned* __g_end = __g;
    unsigned __dc = 0;
    for (; __b != __e; ++__b)
    {
        if (__a_end == __a + __buf.size())
        {
            size_t __tmp = __buf.size();
            __buf.resize(2*__buf.size());
            __buf.resize(__buf.capacity());
            __a = &__buf[0];
            __a_end = __a + __tmp;
        }
        if (this->__stage2_int_loop(*__b, __base, __a, __a_end, __dc,
                                    __thousands_sep, __grouping, __g, __g_end,
                                    __atoms))
            break;
    }
    if (__grouping.size() != 0 && __g_end-__g < __num_get_base::__num_get_buf_sz)
        *__g_end++ = __dc;
    // Stage 3
    __v = __num_get_signed_integral<_Signed>(__a, __a_end, __err, __base);
    // Digit grouping checked
    __check_grouping(__grouping, __g, __g_end, __err);
    // EOF checked
    if (__b == __e)
        __err |= ios_base::eofbit;
    return __b;
}

// unsigned

template <class _CharT, class _InputIterator>
template <class _Unsigned>
_InputIterator
num_get<_CharT, _InputIterator>::__do_get_unsigned(iter_type __b, iter_type __e,
                                        ios_base& __iob,
                                        ios_base::iostate& __err,
                                        _Unsigned& __v) const
{
    // Stage 1
    int __base = this->__get_base(__iob);
    // Stage 2
    char_type __thousands_sep;
    const int __atoms_size = 26;
#ifdef _LIBCPP_ABI_OPTIMIZED_LOCALE_NUM_GET
    char_type __atoms1[__atoms_size];
    const char_type *__atoms = this->__do_widen(__iob, __atoms1);
    string __grouping = this->__stage2_int_prep(__iob, __thousands_sep);
#else
    char_type __atoms[__atoms_size];
    string __grouping = this->__stage2_int_prep(__iob, __atoms, __thousands_sep);
#endif
    string __buf;
    __buf.resize(__buf.capacity());
    char* __a = &__buf[0];
    char* __a_end = __a;
    unsigned __g[__num_get_base::__num_get_buf_sz];
    unsigned* __g_end = __g;
    unsigned __dc = 0;
    for (; __b != __e; ++__b)
    {
        if (__a_end == __a + __buf.size())
        {
            size_t __tmp = __buf.size();
            __buf.resize(2*__buf.size());
            __buf.resize(__buf.capacity());
            __a = &__buf[0];
            __a_end = __a + __tmp;
        }
        if (this->__stage2_int_loop(*__b, __base, __a, __a_end, __dc,
                                    __thousands_sep, __grouping, __g, __g_end,
                                    __atoms))
            break;
    }
    if (__grouping.size() != 0 && __g_end-__g < __num_get_base::__num_get_buf_sz)
        *__g_end++ = __dc;
    // Stage 3
    __v = __num_get_unsigned_integral<_Unsigned>(__a, __a_end, __err, __base);
    // Digit grouping checked
    __check_grouping(__grouping, __g, __g_end, __err);
    // EOF checked
    if (__b == __e)
        __err |= ios_base::eofbit;
    return __b;
}

// floating point

template <class _CharT, class _InputIterator>
template <class _Fp>
_InputIterator
num_get<_CharT, _InputIterator>::__do_get_floating_point(iter_type __b, iter_type __e,
                                        ios_base& __iob,
                                        ios_base::iostate& __err,
                                        _Fp& __v) const
{
    // Stage 1, nothing to do
    // Stage 2
    char_type __atoms[32];
    char_type __decimal_point;
    char_type __thousands_sep;
    string __grouping = this->__stage2_float_prep(__iob, __atoms,
                                                  __decimal_point,
                                                  __thousands_sep);
    string __buf;
    __buf.resize(__buf.capacity());
    char* __a = &__buf[0];
    char* __a_end = __a;
    unsigned __g[__num_get_base::__num_get_buf_sz];
    unsigned* __g_end = __g;
    unsigned __dc = 0;
    bool __in_units = true;
    char __exp = 'E';
    for (; __b != __e; ++__b)
    {
        if (__a_end == __a + __buf.size())
        {
            size_t __tmp = __buf.size();
            __buf.resize(2*__buf.size());
            __buf.resize(__buf.capacity());
            __a = &__buf[0];
            __a_end = __a + __tmp;
        }
        if (this->__stage2_float_loop(*__b, __in_units, __exp, __a, __a_end,
                                      __decimal_point, __thousands_sep,
                                      __grouping, __g, __g_end,
                                      __dc, __atoms))
            break;
    }
    if (__grouping.size() != 0 && __in_units && __g_end-__g < __num_get_base::__num_get_buf_sz)
        *__g_end++ = __dc;
    // Stage 3
    __v = __num_get_float<_Fp>(__a, __a_end, __err);
    // Digit grouping checked
    __check_grouping(__grouping, __g, __g_end, __err);
    // EOF checked
    if (__b == __e)
        __err |= ios_base::eofbit;
    return __b;
}

template <class _CharT, class _InputIterator>
_InputIterator
num_get<_CharT, _InputIterator>::do_get(iter_type __b, iter_type __e,
                                        ios_base& __iob,
                                        ios_base::iostate& __err,
                                        void*& __v) const
{
    // Stage 1
    int __base = 16;
    // Stage 2
    char_type __atoms[26];
    char_type __thousands_sep = 0;
    string __grouping;
    use_facet<ctype<_CharT> >(__iob.getloc()).widen(__num_get_base::__src,
                                                    __num_get_base::__src + 26, __atoms);
    string __buf;
    __buf.resize(__buf.capacity());
    char* __a = &__buf[0];
    char* __a_end = __a;
    unsigned __g[__num_get_base::__num_get_buf_sz];
    unsigned* __g_end = __g;
    unsigned __dc = 0;
    for (; __b != __e; ++__b)
    {
        if (__a_end == __a + __buf.size())
        {
            size_t __tmp = __buf.size();
            __buf.resize(2*__buf.size());
            __buf.resize(__buf.capacity());
            __a = &__buf[0];
            __a_end = __a + __tmp;
        }
        if (this->__stage2_int_loop(*__b, __base, __a, __a_end, __dc,
                                    __thousands_sep, __grouping,
                                    __g, __g_end, __atoms))
            break;
    }
    // Stage 3
    __buf.resize(__a_end - __a);
    if (__libcpp_sscanf_l(__buf.c_str(), _LIBCPP_GET_C_LOCALE, "%p", &__v) != 1)
        __err = ios_base::failbit;
    // EOF checked
    if (__b == __e)
        __err |= ios_base::eofbit;
    return __b;
}

_LIBCPP_EXTERN_TEMPLATE2(class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS num_get<char>)
_LIBCPP_EXTERN_TEMPLATE2(class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS num_get<wchar_t>)

struct _LIBCPP_TYPE_VIS __num_put_base
{
protected:
    static void __format_int(char* __fmt, const char* __len, bool __signd,
                             ios_base::fmtflags __flags);
    static bool __format_float(char* __fmt, const char* __len,
                               ios_base::fmtflags __flags);
    static char* __identify_padding(char* __nb, char* __ne,
                                    const ios_base& __iob);
};

template <class _CharT>
struct __num_put
    : protected __num_put_base
{
    static void __widen_and_group_int(char* __nb, char* __np, char* __ne,
                                      _CharT* __ob, _CharT*& __op, _CharT*& __oe,
                                      const locale& __loc);
    static void __widen_and_group_float(char* __nb, char* __np, char* __ne,
                                        _CharT* __ob, _CharT*& __op, _CharT*& __oe,
                                        const locale& __loc);
};

template <class _CharT>
void
__num_put<_CharT>::__widen_and_group_int(char* __nb, char* __np, char* __ne,
                                         _CharT* __ob, _CharT*& __op, _CharT*& __oe,
                                         const locale& __loc)
{
    const ctype<_CharT>&    __ct = use_facet<ctype<_CharT> >   (__loc);
    const numpunct<_CharT>& __npt = use_facet<numpunct<_CharT> >(__loc);
    string __grouping = __npt.grouping();
    if (__grouping.empty())
    {
        __ct.widen(__nb, __ne, __ob);
        __oe = __ob + (__ne - __nb);
    }
    else
    {
        __oe = __ob;
        char* __nf = __nb;
        if (*__nf == '-' || *__nf == '+')
            *__oe++ = __ct.widen(*__nf++);
        if (__ne - __nf >= 2 && __nf[0] == '0' && (__nf[1] == 'x' ||
                                                   __nf[1] == 'X'))
        {
            *__oe++ = __ct.widen(*__nf++);
            *__oe++ = __ct.widen(*__nf++);
        }
        reverse(__nf, __ne);
        _CharT __thousands_sep = __npt.thousands_sep();
        unsigned __dc = 0;
        unsigned __dg = 0;
        for (char* __p = __nf; __p < __ne; ++__p)
        {
            if (static_cast<unsigned>(__grouping[__dg]) > 0 &&
                __dc == static_cast<unsigned>(__grouping[__dg]))
            {
                *__oe++ = __thousands_sep;
                __dc = 0;
                if (__dg < __grouping.size()-1)
                    ++__dg;
            }
            *__oe++ = __ct.widen(*__p);
            ++__dc;
        }
        reverse(__ob + (__nf - __nb), __oe);
    }
    if (__np == __ne)
        __op = __oe;
    else
        __op = __ob + (__np - __nb);
}

template <class _CharT>
void
__num_put<_CharT>::__widen_and_group_float(char* __nb, char* __np, char* __ne,
                                           _CharT* __ob, _CharT*& __op, _CharT*& __oe,
                                           const locale& __loc)
{
    const ctype<_CharT>&    __ct = use_facet<ctype<_CharT> >   (__loc);
    const numpunct<_CharT>& __npt = use_facet<numpunct<_CharT> >(__loc);
    string __grouping = __npt.grouping();
    __oe = __ob;
    char* __nf = __nb;
    if (*__nf == '-' || *__nf == '+')
        *__oe++ = __ct.widen(*__nf++);
    char* __ns;
    if (__ne - __nf >= 2 && __nf[0] == '0' && (__nf[1] == 'x' ||
                                               __nf[1] == 'X'))
    {
        *__oe++ = __ct.widen(*__nf++);
        *__oe++ = __ct.widen(*__nf++);
        for (__ns = __nf; __ns < __ne; ++__ns)
            if (!isxdigit_l(*__ns, _LIBCPP_GET_C_LOCALE))
                break;
    }
    else
    {
        for (__ns = __nf; __ns < __ne; ++__ns)
            if (!isdigit_l(*__ns, _LIBCPP_GET_C_LOCALE))
                break;
    }
    if (__grouping.empty())
    {
        __ct.widen(__nf, __ns, __oe);
        __oe += __ns - __nf;
    }
    else
    {
        reverse(__nf, __ns);
        _CharT __thousands_sep = __npt.thousands_sep();
        unsigned __dc = 0;
        unsigned __dg = 0;
        for (char* __p = __nf; __p < __ns; ++__p)
        {
            if (__grouping[__dg] > 0 && __dc == static_cast<unsigned>(__grouping[__dg]))
            {
                *__oe++ = __thousands_sep;
                __dc = 0;
                if (__dg < __grouping.size()-1)
                    ++__dg;
            }
            *__oe++ = __ct.widen(*__p);
            ++__dc;
        }
        reverse(__ob + (__nf - __nb), __oe);
    }
    for (__nf = __ns; __nf < __ne; ++__nf)
    {
        if (*__nf == '.')
        {
            *__oe++ = __npt.decimal_point();
            ++__nf;
            break;
        }
        else
            *__oe++ = __ct.widen(*__nf);
    }
    __ct.widen(__nf, __ne, __oe);
    __oe += __ne - __nf;
    if (__np == __ne)
        __op = __oe;
    else
        __op = __ob + (__np - __nb);
}

_LIBCPP_EXTERN_TEMPLATE2(struct _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __num_put<char>)
_LIBCPP_EXTERN_TEMPLATE2(struct _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __num_put<wchar_t>)

template <class _CharT, class _OutputIterator = ostreambuf_iterator<_CharT> >
class _LIBCPP_TEMPLATE_VIS num_put
    : public locale::facet,
      private __num_put<_CharT>
{
public:
    typedef _CharT char_type;
    typedef _OutputIterator iter_type;

    _LIBCPP_INLINE_VISIBILITY
    explicit num_put(size_t __refs = 0)
        : locale::facet(__refs) {}

    _LIBCPP_INLINE_VISIBILITY
    iter_type put(iter_type __s, ios_base& __iob, char_type __fl,
                  bool __v) const
    {
        return do_put(__s, __iob, __fl, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type put(iter_type __s, ios_base& __iob, char_type __fl,
                  long __v) const
    {
        return do_put(__s, __iob, __fl, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type put(iter_type __s, ios_base& __iob, char_type __fl,
                  long long __v) const
    {
        return do_put(__s, __iob, __fl, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type put(iter_type __s, ios_base& __iob, char_type __fl,
                  unsigned long __v) const
    {
        return do_put(__s, __iob, __fl, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type put(iter_type __s, ios_base& __iob, char_type __fl,
                  unsigned long long __v) const
    {
        return do_put(__s, __iob, __fl, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type put(iter_type __s, ios_base& __iob, char_type __fl,
                  double __v) const
    {
        return do_put(__s, __iob, __fl, __v);
    }

    _LIBCPP_INLINE_VISIBILITY
    iter_type put(iter_type __s, ios_base& __iob, char_type __fl,
                  long double __v) const
    {                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  