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

#ifndef _LIBCPP_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;                              // removed C++20
    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                                      // Removed in C++26
{
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;

    wstring_convert(Codecvt* pcvt = new Codecvt);          // before C++14
    explicit wstring_convert(Codecvt* pcvt = new Codecvt); // before C++20
    wstring_convert() : wstring_convert(new Codecvt) {}    // C++20
    explicit wstring_convert(Codecvt* pcvt);               // C++20

    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                                               // Removed in C++26
    : public basic_streambuf<Elem, Tr>
{
public:
    typedef typename Tr::state_type state_type;

    wbuffer_convert(streambuf* bytebuf = 0, Codecvt* pcvt = new Codecvt,
                    state_type state = state_type());          // before C++14
    explicit wbuffer_convert(streambuf* bytebuf = nullptr, Codecvt* pcvt = new Codecvt,
                            state_type state = state_type()); // before C++20
    wbuffer_convert() : wbuffer_convert(nullptr) {} // C++20
    explicit wbuffer_convert(streambuf* bytebuf, Codecvt* pcvt = new Codecvt,
                            state_type state = state_type()); // C++20

    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>

#if !defined(_LIBCPP_HAS_NO_LOCALIZATION)

#  include <__algorithm/copy.h>
#  include <__algorithm/equal.h>
#  include <__algorithm/find.h>
#  include <__algorithm/max.h>
#  include <__algorithm/reverse.h>
#  include <__algorithm/unwrap_iter.h>
#  include <__assert>
#  include <__iterator/access.h>
#  include <__iterator/back_insert_iterator.h>
#  include <__iterator/istreambuf_iterator.h>
#  include <__iterator/ostreambuf_iterator.h>
#  include <__locale>
#  include <__memory/unique_ptr.h>
#  include <__type_traits/make_unsigned.h>
#  include <cerrno>
#  include <cstdio>
#  include <cstdlib>
#  include <ctime>
#  include <ios>
#  include <limits>
#  include <new>
#  include <streambuf>
#  include <version>

// TODO: Fix __bsd_locale_defaults.h
// NOLINTBEGIN(libcpp-robust-against-adl)

#  if defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
// Most unix variants have catopen.  These are the specific ones that don't.
#    if !defined(__BIONIC__) && !defined(_NEWLIB_VERSION) && !defined(__EMSCRIPTEN__)
#      define _LIBCPP_HAS_CATOPEN 1
#      include <nl_types.h>
#    endif
#  endif

#  ifdef _LIBCPP_LOCALE__L_EXTENSIONS
#    include <__locale_dir/locale_base_api/bsd_locale_defaults.h>
#  else
#    include <__locale_dir/locale_base_api/bsd_locale_fallbacks.h>
#  endif

#  if defined(__APPLE__) || defined(__FreeBSD__)
#    include <xlocale.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(__NetBSD__)
#    define _LIBCPP_GET_C_LOCALE LC_C_LOCALE
#  else
#    define _LIBCPP_GET_C_LOCALE __cloc()
// Get the C locale object
_LIBCPP_EXPORTED_FROM_ABI 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_HIDE_FROM_ABI _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>(std::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(nullptr, free);
  if (__nkw > sizeof(__statbuf)) {
    __status = (unsigned char*)malloc(__nkw);
    if (__status == nullptr)
      __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_EXPORTED_FROM_ABI __num_get_base {
  static const int __num_get_buf_sz = 40;

  static int __get_base(ios_base&);
  static const char __src[33]; // "0123456789abcdefABCDEFxX+-pPiInN"
  // count of leading characters in __src used for parsing integers ("012..X+-")
  static const size_t __int_chr_cnt = 26;
  // count of leading characters in __src used for parsing floating-point values ("012..-pP")
  static const size_t __fp_chr_cnt = 28;
};

_LIBCPP_EXPORTED_FROM_ABI 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 _Tp>
  const _Tp* __do_widen_p(ios_base& __iob, _Tp* __atoms) const {
    locale __loc = __iob.getloc();
    use_facet<ctype<_Tp> >(__loc).widen(__src, __src + __int_chr_cnt, __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();
  std::use_facet<ctype<_CharT> >(__loc).widen(__src, __src + __int_chr_cnt, __atoms);
  const numpunct<_CharT>& __np = std::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();
  std::use_facet<ctype<_CharT> >(__loc).widen(__src, __src + __fp_chr_cnt, __atoms);
  const numpunct<_CharT>& __np = std::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 = std::find(__atoms, __atoms + __int_chr_cnt, __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 = std::find(__atoms, __atoms + __num_get_base::__fp_chr_cnt, __ct) - __atoms;
  if (__f >= static_cast<ptrdiff_t>(__num_get_base::__fp_chr_cnt))
    return -1;
  char __x = __src[__f];
  if (__x == '-' || __x == '+') {
    if (__a_end == __a || (std::toupper(__a_end[-1]) == std::toupper(__exp))) {
      *__a_end++ = __x;
      return 0;
    }
    return -1;
  }
  if (__x == 'x' || __x == 'X')
    __exp = 'P';
  else if (std::toupper(__x) == __exp) {
    __exp = std::tolower(__exp);
    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;
}

extern template struct _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __num_get<char>;
#  ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
extern template struct _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __num_get<wchar_t>;
#  endif

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_HIDE_FROM_ABI explicit num_get(size_t __refs = 0) : locale::facet(__refs) {}

  _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI 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_HIDE_FROM_ABI_VIRTUAL ~num_get() override {}

  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>
_LIBCPP_HIDE_FROM_ABI _Tp
__num_get_signed_integral(const char* __a, const char* __a_end, ios_base::iostate& __err, int __base) {
  if (__a != __a_end) {
    __libcpp_remove_reference_t<decltype(errno)> __save_errno = errno;
    errno                                                     = 0;
    char* __p2;
    long long __ll                                               = strtoll_l(__a, &__p2, __base, _LIBCPP_GET_C_LOCALE);
    __libcpp_remove_reference_t<decltype(errno)> __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>
_LIBCPP_HIDE_FROM_ABI _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;
    }
    __libcpp_remove_reference_t<decltype(errno)> __save_errno = errno;
    errno                                                     = 0;
    char* __p2;
    unsigned long long __ll                                      = strtoull_l(__a, &__p2, __base, _LIBCPP_GET_C_LOCALE);
    __libcpp_remove_reference_t<decltype(errno)> __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_HIDE_FROM_ABI _Tp __do_strtod(const char* __a, char** __p2);

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

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

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

template <class _Tp>
_LIBCPP_HIDE_FROM_ABI _Tp __num_get_float(const char* __a, const char* __a_end, ios_base::iostate& __err) {
  if (__a != __a_end) {
    __libcpp_remove_reference_t<decltype(errno)> __save_errno = errno;
    errno                                                     = 0;
    char* __p2;
    _Tp __ld                                                     = std::__do_strtod<_Tp>(__a, &__p2);
    __libcpp_remove_reference_t<decltype(errno)> __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    = std::use_facet<ctype<_CharT> >(__iob.getloc());
  const numpunct<_CharT>& __np = std::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       = std::__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 = __num_get_base::__int_chr_cnt;
#  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 = std::__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 = __num_get_base::__int_chr_cnt;
#  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 = std::__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[__num_get_base::__fp_chr_cnt];
  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';
  bool __is_leading_parsed = false;
  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;

    // the leading character excluding the sign must be a decimal digit
    if (!__is_leading_parsed) {
      if (__a_end - __a >= 1 && __a[0] != '-' && __a[0] != '+') {
        if (('0' <= __a[0] && __a[0] <= '9') || __a[0] == '.')
          __is_leading_parsed = true;
        else
          break;
      } else if (__a_end - __a >= 2 && (__a[0] == '-' || __a[0] == '+')) {
        if (('0' <= __a[1] && __a[1] <= '9') || __a[1] == '.')
          __is_leading_parsed = true;
        else
          break;
      }
    }
  }
  if (__grouping.size() != 0 && __in_units && __g_end - __g < __num_get_base::__num_get_buf_sz)
    *__g_end++ = __dc;
  // Stage 3
  __v = std::__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[__num_get_base::__int_chr_cnt];
  char_type __thousands_sep = char_type();
  string __grouping;
  std::use_facet<ctype<_CharT> >(__iob.getloc())
      .widen(__num_get_base::__src, __num_get_base::__src + __num_get_base::__int_chr_cnt, __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;
}

extern template class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS num_get<char>;
#  ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
extern template class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS num_get<wchar_t>;
#  endif

struct _LIBCPP_EXPORTED_FROM_ABI __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     = std::use_facet<ctype<_CharT> >(__loc);
  const numpunct<_CharT>& __npt = std::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++);
    }
    std::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;
    }
    std::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     = std::use_facet<ctype<_CharT> >(__loc);
  const numpunct<_CharT>& __npt = std::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 {
    std::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;
    }
    std::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);
}

extern template struct _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __num_put<char>;
#  ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
extern template struct _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __num_put<wchar_t>;
#  endif

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_HIDE_FROM_ABI explicit num_put(size_t __refs = 0) : locale::facet(__refs) {}

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

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

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

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

  _LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI iter_type put(iter_type __s, ios_base& __iob, char_type __fl, double __v) const {
    return do_put(__s, __iob, __fl, __v);
  }

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

  _LIBCPP_HIDE_FROM_ABI iter_type put(iter_type __s, ios_base& __iob, char_type __fl, const void* __v) const {
    return do_put(__s, __iob, __fl, __v);
  }

  static locale::id id;

protected:
  _LIBCPP_HIDE_FROM_ABI_VIRTUAL ~num_put() override {}

  virtual iter_type do_put(iter_type __s, ios_base& __iob, char_type __fl, bool __v) const;
  virtual iter_type do_put(iter_type __s, ios_base& __iob, char_type __fl, long __v) const;
  virtual iter_type do_put(iter_type __s, ios_base& __iob, char_type __fl, long long __v) const;
  virtual iter_type do_put(iter_type __s, ios_base& __iob, char_type __fl, unsigned long) const;
  virtual iter_type do_put(iter_type __s, ios_base& __iob, char_type __fl, unsigned long long) const;
  virtual iter_type do_put(iter_type __s, ios_base& __iob, char_type __fl, double __v) const;
  virtual iter_type do_put(iter_type __s, ios_base& __iob, char_type __fl, long double __v) const;
  virtual iter_type do_put(iter_type __s, ios_base& __iob, char_type __fl, const void* __v) const;

  template <class _Integral>
  _LIBCPP_HIDE_FROM_ABI inline _OutputIterator
  __do_put_integral(iter_type __s, ios_base& __iob, char_type __fl, _Integral __v, char const* __len) const;

  template <class _Float>
  _LIBCPP_HIDE_FROM_ABI inline _OutputIterator
  __do_put_floating_point(iter_type __s, ios_base& __iob, char_type __fl, _Float __v, char const* __len) const;
};

template <class _CharT, class _OutputIterator>
locale::id num_put<_CharT, _OutputIterator>::id;

template <class _CharT, class _OutputIterator>
_LIBCPP_HIDE_FROM_ABI _OutputIterator __pad_and_output(
    _OutputIterator __s, const _CharT* __ob, const _CharT* __op, const _CharT* __oe, ios_base& __iob, _CharT __fl) {
  streamsize __sz = __oe - __ob;
  streamsize __ns = __iob.width();
  if (__ns > __sz)
    __ns -= __sz;
  else
    __ns = 0;
  for (; __ob < __op; ++__ob, ++__s)
    *__s = *__ob;
  for (; __ns; --__ns, ++__s)
    *__s = __fl;
  for (; __ob < __oe; ++__ob, ++__s)
    *__s = *__ob;
  __iob.width(0);
  return __s;
}

template <class _CharT, class _Traits>
_LIBCPP_HIDE_FROM_ABI ostreambuf_iterator<_CharT, _Traits> __pad_and_output(
    ostreambuf_iterator<_CharT, _Traits> __s,
    const _CharT* __ob,
    const _CharT* __op,
    const _CharT* __oe,
    ios_base& __iob,
    _CharT __fl) {
  if (__s.__sbuf_ == nullptr)
    return __s;
  streamsize __sz = __oe - __ob;
  streamsize __ns = __iob.width();
  if (__ns > __sz)
    __ns -= __sz;
  else
    __ns = 0;
  streamsize __np = __op - __ob;
  if (__np > 0) {
    if (__s.__sbuf_->sputn(__ob, __np) != __np) {
      __s.__sbuf_ = nullptr;
      return __s;
    }
  }
  if (__ns > 0) {
    basic_string<_CharT, _Traits> __sp(__ns, __fl);
    if (__s.__sbuf_->sputn(__sp.data(), __ns) != __ns) {
      __s.__sbuf_ = nullptr;
      return __s;
    }
  }
  __np = __oe - __op;
  if (__np > 0) {
    if (__s.__sbuf_->sputn(__op, __np) != __np) {
      __s.__sbuf_ = nullptr;
      return __s;
    }
  }
  __iob.width(0);
  return __s;
}

template <class _CharT, class _OutputIterator>
_OutputIterator
num_put<_CharT, _OutputIterator>::do_put(iter_type __s, ios_base& __iob, char_type __fl, bool __v) const {
  if ((__iob.flags() & ios_base::boolalpha) == 0)
    return do_put(__s, __iob, __fl, (unsigned long)__v);
  const numpunct<char_type>& __np = std::use_facet<numpunct<char_type> >(__iob.getloc());
  typedef typename numpunct<char_type>::string_type string_type;
  string_type __nm = __v ? __np.truename() : __np.falsename();
  for (typename string_type::iterator __i = __nm.begin(); __i != __nm.end(); ++__i, ++__s)
    *__s = *__i;
  return __s;
}

template <class _CharT, class _OutputIterator>
template <class _Integral>
_LIBCPP_HIDE_FROM_ABI inline _OutputIterator num_put<_CharT, _OutputIterator>::__do_put_integral(
    iter_type __s, ios_base& __iob, char_type __fl, _Integral __v, char const* __len) const {
  // Stage 1 - Get number in narrow char
  char __fmt[8] = {'%', 0};
  this->__format_int(__fmt + 1, __len, is_signed<_Integral>::value, __iob.flags());
  // Worst case is octal, with showbase enabled. Note that octal is always
  // printed as an unsigned value.
  using _Unsigned = typename make_unsigned<_Integral>::type;
  _LIBCPP_CONSTEXPR const unsigned __nbuf =
      (numeric_limits<_Unsigned>::digits / 3)          // 1 char per 3 bits
      + ((numeric_limits<_Unsigned>::digits % 3) != 0) // round up
      + 2;                                             // base prefix + terminating null character
  char __nar[__nbuf];
  _LIBCPP_DIAGNOSTIC_PUSH
  _LIBCPP_CLANG_DIAGNOSTIC_IGNORED("-Wformat-nonliteral")
  _LIBCPP_GCC_DIAGNOSTIC_IGNORED("-Wformat-nonliteral")
  int __nc = __libcpp_snprintf_l(__nar, sizeof(__nar), _LIBCPP_GET_C_LOCALE, __fmt, __v);
  _LIBCPP_DIAGNOSTIC_POP
  char* __ne = __nar + __nc;
  char* __np = this->__identify_padding(__nar, __ne, __iob);
  // Stage 2 - Widen __nar while adding thousands separators
  char_type __o[2 * (__nbuf - 1) - 1];
  char_type* __op; // pad here
  char_type* __oe; // end of output
  this->__widen_and_group_int(__nar, __np, __ne, __o, __op, __oe, __iob.getloc());
  // [__o, __oe) contains thousands_sep'd wide number
  // Stage 3 & 4
  return std::__pad_and_output(__s, __o, __op, __oe, __iob, __fl);
}

template <class _CharT, class _OutputIterator>
_OutputIterator
num_put<_CharT, _OutputIterator>::do_put(iter_type __s, ios_base& __iob, char_type __fl, long __v) const {
  return this->__do_put_integral(__s, __iob, __fl, __v, "l");
}

template <class _CharT, class _OutputIterator>
_OutputIterator
num_put<_CharT, _OutputIterator>::do_put(iter_type __s, ios_base& __iob, char_type __fl, long long __v) const {
  return this->__do_put_integral(__s, __iob, __fl, __v, "ll");
}

template <class _CharT, class _OutputIterator>
_OutputIterator
num_put<_CharT, _OutputIterator>::do_put(iter_type __s, ios_base& __iob, char_type __fl, unsigned long __v) const {
  return this->__do_put_integral(__s, __iob, __fl, __v, "l");
}

template <class _CharT, class _OutputIterator>
_OutputIterator
num_put<_CharT, _OutputIterator>::do_put(iter_type __s, ios_base& __iob, char_type __fl, unsigned long long __v) const {
  return this->__do_put_integral(__s, __iob, __fl, __v, "ll");
}

template <class _CharT, class _OutputIterator>
template <class _Float>
_LIBCPP_HIDE_FROM_ABI inline _OutputIterator num_put<_CharT, _OutputIterator>::__do_put_floating_point(
    iter_type __s, ios_base& __iob, char_type __fl, _Float __v, char const* __len) const {
  // Stage 1 - Get number in narrow char
  char __fmt[8]            = {'%', 0};
  bool __specify_precision = this->__format_float(__fmt + 1, __len, __iob.flags());
  const unsigned __nbuf    = 30;
  char __nar[__nbuf];
  char* __nb = __nar;
  int __nc;
  _LIBCPP_DIAGNOSTIC_PUSH
  _LIBCPP_CLANG_DIAGNOSTIC_IGNORED("-Wformat-nonliteral")
  _LIBCPP_GCC_DIAGNOSTIC_IGNORED("-Wformat-nonliteral")
  if (__specify_precision)
    __nc = __libcpp_snprintf_l(__nb, __nbuf, _LIBCPP_GET_C_LOCALE, __fmt, (int)__iob.precision(), __v);
  else
    __nc = __libcpp_snprintf_l(__nb, __nbuf, _LIBCPP_GET_C_LOCALE, __fmt, __v);
  unique_ptr<char, void (*)(void*)> __nbh(nullptr, free);
  if (__nc > static_cast<int>(__nbuf - 1)) {
    if (__specify_precision)
      __nc = __libcpp_asprintf_l(&__nb, _LIBCPP_GET_C_LOCALE, __fmt, (int)__iob.precision(), __v);
    else
      __nc = __libcpp_asprintf_l(&__nb, _LIBCPP_GET_C_LOCALE, __fmt, __v);
    if (__nc == -1)
      __throw_bad_alloc();
    __nbh.reset(__nb);
  }
  _LIBCPP_DIAGNOSTIC_POP
  char* __ne = __nb + __nc;
  char* __np = this->__identify_padding(__nb, __ne, __iob);
  // Stage 2 - Widen __nar while adding thousands separators
  char_type __o[2 * (__nbuf - 1) - 1];
  char_type* __ob = __o;
  unique_ptr<char_type, void (*)(void*)> __obh(0, free);
  if (__nb != __nar) {
    __ob = (char_type*)malloc(2 * static_cast<size_t>(__nc) * sizeof(char_type));
    if (__ob == 0)
      __throw_bad_alloc();
    __obh.reset(__ob);
  }
  char_type* __op; // pad here
  char_type* __oe; // end of output
  this->__widen_and_group_float(__nb, __np, __ne, __ob, __op, __oe, __iob.getloc());
  // [__o, __oe) contains thousands_sep'd wide number
  // Stage 3 & 4
  __s = std::__pad_and_output(__s, __ob, __op, __oe, __iob, __fl);
  return __s;
}

template <class _CharT, class _OutputIterator>
_OutputIterator
num_put<_CharT, _OutputIterator>::do_put(iter_type __s, ios_base& __iob, char_type __fl, double __v) const {
  return this->__do_put_floating_point(__s, __iob, __fl, __v, "");
}

template <class _CharT, class _OutputIterator>
_OutputIterator
num_put<_CharT, _OutputIterator>::do_put(iter_type __s, ios_base& __iob, char_type __fl, long double __v) const {
  return this->__do_put_floating_point(__s, __iob, __fl, __v, "L");
}

template <class _CharT, class _OutputIterator>
_OutputIterator
num_put<_CharT, _OutputIterator>::do_put(iter_type __s, ios_base& __iob, char_type __fl, const void* __v) const {
  // Stage 1 - Get pointer in narrow char
  const unsigned __nbuf = 20;
  char __nar[__nbuf];
  int __nc   = __libcpp_snprintf_l(__nar, sizeof(__nar), _LIBCPP_GET_C_LOCALE, "%p", __v);
  char* __ne = __nar + __nc;
  char* __np = this->__identify_padding(__nar, __ne, __iob);
  // Stage 2 - Widen __nar
  char_type __o[2 * (__nbuf - 1) - 1];
  char_type* __op; // pad here
  char_type* __oe; // end of output
  const ctype<char_type>& __ct = std::use_facet<ctype<char_type> >(__iob.getloc());
  __ct.widen(__nar, __ne, __o);
  __oe = __o + (__ne - __nar);
  if (__np == __ne)
    __op = __oe;
  else
    __op = __o + (__np - __nar);
  // [__o, __oe) contains wide number
  // Stage 3 & 4
  return std::__pad_and_output(__s, __o, __op, __oe, __iob, __fl);
}

extern template class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS num_put<char>;
#  ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
extern template class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS num_put<wchar_t>;
#  endif

template <class _CharT, class _InputIterator>
_LIBCPP_HIDE_FROM_ABI int __get_up_to_n_digits(
    _InputIterator& __b, _InputIterator __e, ios_base::iostate& __err, const ctype<_CharT>& __ct, int __n) {
  // Precondition:  __n >= 1
  if (__b == __e) {
    __err |= ios_base::eofbit | ios_base::failbit;
    return 0;
  }
  // get first digit
  _CharT __c = *__b;
  if (!__ct.is(ctype_base::digit, __c)) {
    __err |= ios_base::failbit;
    return 0;
  }
  int __r = __ct.narrow(__c, 0) - '0';
  for (++__b, (void)--__n; __b != __e && __n > 0; ++__b, (void)--__n) {
    // get next digit
    __c = *__b;
    if (!__ct.is(ctype_base::digit, __c))
      return __r;
    __r = __r * 10 + __ct.narrow(__c, 0) - '0';
  }
  if (__b == __e)
    __err |= ios_base::eofbit;
  return __r;
}

class _LIBCPP_EXPORTED_FROM_ABI time_base {
public:
  enum dateorder { no_order, dmy, mdy, ymd, ydm };
};

template <class _CharT>
class _LIBCPP_TEMPLATE_VIS __time_get_c_storage {
protected:
  typedef basic_string<_CharT> string_type;

  virtual const string_type* __weeks() const;
  virtual const string_type* __months() const;
  virtual const string_type* __am_pm() const;
  virtual const string_type& __c() const;
  virtual const string_type& __r() const;
  virtual const string_type& __x() const;
  virtual const string_type& __X() const;

  _LIBCPP_HIDE_FROM_ABI ~__time_get_c_storage() {}
};

template <>
_LIBCPP_EXPORTED_FROM_ABI const string* __time_get_c_storage<char>::__weeks() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const string* __time_get_c_storage<char>::__months() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const string* __time_get_c_storage<char>::__am_pm() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const string& __time_get_c_storage<char>::__c() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const string& __time_get_c_storage<char>::__r() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const string& __time_get_c_storage<char>::__x() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const string& __time_get_c_storage<char>::__X() const;

#  ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
template <>
_LIBCPP_EXPORTED_FROM_ABI const wstring* __time_get_c_storage<wchar_t>::__weeks() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const wstring* __time_get_c_storage<wchar_t>::__months() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const wstring* __time_get_c_storage<wchar_t>::__am_pm() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const wstring& __time_get_c_storage<wchar_t>::__c() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const wstring& __time_get_c_storage<wchar_t>::__r() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const wstring& __time_get_c_storage<wchar_t>::__x() const;
template <>
_LIBCPP_EXPORTED_FROM_ABI const wstring& __time_get_c_storage<wchar_t>::__X() const;
#  endif

template <class _CharT, class _InputIterator = istreambuf_iterator<_CharT> >
class _LIBCPP_TEMPLATE_VIS time_get : public locale::facet, public time_base, private __time_get_c_storage<_CharT> {
public:
  typedef _CharT char_type;
  typedef _InputIterator iter_type;
  typedef time_base::dateorder dateorder;
  typedef basic_string<char_type> string_type;

  _LIBCPP_HIDE_FROM_ABI explicit time_get(size_t __refs = 0) : locale::facet(__refs) {}

  _LIBCPP_HIDE_FROM_ABI dateorder date_order() const { return this->do_date_order(); }

  _LIBCPP_HIDE_FROM_ABI iter_type
  get_time(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm) const {
    return do_get_time(__b, __e, __iob, __err, __tm);
  }

  _LIBCPP_HIDE_FROM_ABI iter_type
  get_date(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm) const {
    return do_get_date(__b, __e, __iob, __err, __tm);
  }

  _LIBCPP_HIDE_FROM_ABI iter_type
  get_weekday(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm) const {
    return do_get_weekday(__b, __e, __iob, __err, __tm);
  }

  _LIBCPP_HIDE_FROM_ABI iter_type
  get_monthname(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm) const {
    return do_get_monthname(__b, __e, __iob, __err, __tm);
  }

  _LIBCPP_HIDE_FROM_ABI iter_type
  get_year(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm) const {
    return do_get_year(__b, __e, __iob, __err, __tm);
  }

  _LIBCPP_HIDE_FROM_ABI iter_type
  get(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm, char __fmt, char __mod = 0)
      const {
    return do_get(__b, __e, __iob, __err, __tm, __fmt, __mod);
  }

  iter_type
  get(iter_type __b,
      iter_type __e,
      ios_base& __iob,
      ios_base::iostate& __err,
      tm* __tm,
      const char_type* __fmtb,
      const char_type* __fmte) const;

  static locale::id id;

protected:
  _LIBCPP_HIDE_FROM_ABI_VIRTUAL ~time_get() override {}

  virtual dateorder do_date_order() const;
  virtual iter_type
  do_get_time(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm) const;
  virtual iter_type
  do_get_date(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm) const;
  virtual iter_type
  do_get_weekday(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm) const;
  virtual iter_type
  do_get_monthname(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm) const;
  virtual iter_type
  do_get_year(iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm) const;
  virtual iter_type do_get(
      iter_type __b, iter_type __e, ios_base& __iob, ios_base::iostate& __err, tm* __tm, char __fmt, char __mod) const;

private:
  void __get_white_space(iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void __get_percent(iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;

  void __get_weekdayname(
      int& __m, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void __get_monthname(
      int& __m, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void __get_day(int& __d, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void
  __get_month(int& __m, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void
  __get_year(int& __y, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void
  __get_year4(int& __y, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void
  __get_hour(int& __d, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void
  __get_12_hour(int& __h, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void
  __get_am_pm(int& __h, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void
  __get_minute(int& __m, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void
  __get_second(int& __s, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void
  __get_weekday(int& __w, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
  void __get_day_year_num(
      int& __w, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const;
};

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

// time_get primitives

template <class _CharT, class _InputIterator>
void time_get<_CharT, _InputIterator>::__get_weekdayname(
    int& __w, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const {
  // Note:  ignoring case comes from the POSIX strptime spec
  const string_type* __wk = this->__weeks();
  ptrdiff_t __i           = std::__scan_keyword(__b, __e, __wk, __wk + 14, __ct, __err, false) - __wk;
  if (__i < 14)
    __w = __i % 7;
}

template <class _CharT, class _InputIterator>
void time_get<_CharT, _InputIterator>::__get_monthname(
    int& __m, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const {
  // Note:  ignoring case comes from the POSIX strptime spec
  const string_type* __month = this->__months();
  ptrdiff_t __i              = std::__scan_keyword(__b, __e, __month, __month + 24, __ct, __err, false) - __month;
  if (__i < 24)
    __m = __i % 12;
}

template <class _CharT, class _InputIterator>
void time_get<_CharT, _InputIterator>::__get_day(
    int& __d, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const {
  int __t = std::__get_up_to_n_digits(__b, __e, __err, __ct, 2);
  if (!(__err & ios_base::failbit) && 1 <= __t && __t <= 31)
    __d = __t;
  else
    __err |= ios_base::failbit;
}

template <class _CharT, class _InputIterator>
void time_get<_CharT, _InputIterator>::__get_month(
    int& __m, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const {
  int __t = std::__get_up_to_n_digits(__b, __e, __err, __ct, 2) - 1;
  if (!(__err & ios_base::failbit) && 0 <= __t && __t <= 11)
    __m = __t;
  else
    __err |= ios_base::failbit;
}

template <class _CharT, class _InputIterator>
void time_get<_CharT, _InputIterator>::__get_year(
    int& __y, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const {
  int __t = std::__get_up_to_n_digits(__b, __e, __err, __ct, 4);
  if (!(__err & ios_base::failbit)) {
    if (__t < 69)
      __t += 2000;
    else if (69 <= __t && __t <= 99)
      __t += 1900;
    __y = __t - 1900;
  }
}

template <class _CharT, class _InputIterator>
void time_get<_CharT, _InputIterator>::__get_year4(
    int& __y, iter_type& __b, iter_type __e, ios_base::iostate& __err, const ctype<char_type>& __ct) const {
  int __t = std::__get_up_to_n_digits(__b, __e, __err, __ct, 4);
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        