Skip to content

Instantly share code, notes, and snippets.

@ivankra

ivankra/gist:1026446

Created June 15, 2011 04:00
Show Gist options
  • Save ivankra/1026446 to your computer and use it in GitHub Desktop.
Save ivankra/1026446 to your computer and use it in GitHub Desktop.
Download ZIP
Assertion failure at vho_lower.cxx:2183 in pathscale
Raw
gistfile1.txt
namespace std { }
namespace __std_alias = std;
namespace NStl { }
namespace NStlPriv {
using namespace NStl;
}
namespace stlport = NStl;
namespace _STL = NStl;
namespace __rw {
extern "C++" {
template <bool __b>
struct __rw_compile_assert;
template<>
struct __rw_compile_assert<true> { enum { _C_ok }; };
void
__rw_assert_fail (const char*, const char*, int, const char*)
__attribute__ ((nothrow)) __attribute__ ((noreturn));
}
}
namespace std {
}
extern "C" {
typedef unsigned char __u_char;
typedef unsigned short int __u_short;
typedef unsigned int __u_int;
typedef unsigned long int __u_long;
typedef signed char __int8_t;
typedef unsigned char __uint8_t;
typedef signed short int __int16_t;
typedef unsigned short int __uint16_t;
typedef signed int __int32_t;
typedef unsigned int __uint32_t;
typedef signed long int __int64_t;
typedef unsigned long int __uint64_t;
typedef long int __quad_t;
typedef unsigned long int __u_quad_t;
typedef unsigned long int __dev_t;
typedef unsigned int __uid_t;
typedef unsigned int __gid_t;
typedef unsigned long int __ino_t;
typedef unsigned long int __ino64_t;
typedef unsigned int __mode_t;
typedef unsigned long int __nlink_t;
typedef long int __off_t;
typedef long int __off64_t;
typedef int __pid_t;
typedef struct { int __val[2]; } __fsid_t;
typedef long int __clock_t;
typedef unsigned long int __rlim_t;
typedef unsigned long int __rlim64_t;
typedef unsigned int __id_t;
typedef long int __time_t;
typedef unsigned int __useconds_t;
typedef long int __suseconds_t;
typedef int __daddr_t;
typedef long int __swblk_t;
typedef int __key_t;
typedef int __clockid_t;
typedef void * __timer_t;
typedef long int __blksize_t;
typedef long int __blkcnt_t;
typedef long int __blkcnt64_t;
typedef unsigned long int __fsblkcnt_t;
typedef unsigned long int __fsblkcnt64_t;
typedef unsigned long int __fsfilcnt_t;
typedef unsigned long int __fsfilcnt64_t;
typedef long int __ssize_t;
typedef __off64_t __loff_t;
typedef __quad_t *__qaddr_t;
typedef char *__caddr_t;
typedef long int __intptr_t;
typedef unsigned int __socklen_t;
typedef __u_char u_char;
typedef __u_short u_short;
typedef __u_int u_int;
typedef __u_long u_long;
typedef __quad_t quad_t;
typedef __u_quad_t u_quad_t;
typedef __fsid_t fsid_t;
typedef __loff_t loff_t;
typedef __ino64_t ino_t;
typedef __ino64_t ino64_t;
typedef __dev_t dev_t;
typedef __gid_t gid_t;
typedef __mode_t mode_t;
typedef __nlink_t nlink_t;
typedef __uid_t uid_t;
typedef __off64_t off_t;
typedef __off64_t off64_t;
typedef __pid_t pid_t;
typedef __id_t id_t;
typedef __ssize_t ssize_t;
typedef __daddr_t daddr_t;
typedef __caddr_t caddr_t;
typedef __key_t key_t;
typedef __clock_t clock_t;
typedef __time_t time_t;
typedef __clockid_t clockid_t;
typedef __timer_t timer_t;
typedef __useconds_t useconds_t;
typedef __suseconds_t suseconds_t;
typedef long unsigned int size_t;
typedef unsigned long int ulong;
typedef unsigned short int ushort;
typedef unsigned int uint;
typedef int int8_t __attribute__ ((__mode__ (__QI__)));
typedef int int16_t __attribute__ ((__mode__ (__HI__)));
typedef int int32_t __attribute__ ((__mode__ (__SI__)));
typedef int int64_t __attribute__ ((__mode__ (__DI__)));
typedef unsigned int u_int8_t __attribute__ ((__mode__ (__QI__)));
typedef unsigned int u_int16_t __attribute__ ((__mode__ (__HI__)));
typedef unsigned int u_int32_t __attribute__ ((__mode__ (__SI__)));
typedef unsigned int u_int64_t __attribute__ ((__mode__ (__DI__)));
typedef int register_t __attribute__ ((__mode__ (__word__)));
typedef int __sig_atomic_t;
typedef struct
{
unsigned long int __val[(1024 / (8 * sizeof (unsigned long int)))];
} __sigset_t;
typedef __sigset_t sigset_t;
struct timespec
{
__time_t tv_sec;
long int tv_nsec;
};
struct timeval
{
__time_t tv_sec;
__suseconds_t tv_usec;
};
typedef long int __fd_mask;
typedef struct
{
__fd_mask fds_bits[1024 / (8 * (int) sizeof (__fd_mask))];
} fd_set;
typedef __fd_mask fd_mask;
extern "C" {
extern int select (int __nfds, fd_set *__restrict __readfds,
fd_set *__restrict __writefds,
fd_set *__restrict __exceptfds,
struct timeval *__restrict __timeout);
extern int pselect (int __nfds, fd_set *__restrict __readfds,
fd_set *__restrict __writefds,
fd_set *__restrict __exceptfds,
const struct timespec *__restrict __timeout,
const __sigset_t *__restrict __sigmask);
}
__extension__
extern unsigned int gnu_dev_major (unsigned long long int __dev)
throw ();
__extension__
extern unsigned int gnu_dev_minor (unsigned long long int __dev)
throw ();
__extension__
extern unsigned long long int gnu_dev_makedev (unsigned int __major,
unsigned int __minor)
throw ();
typedef __blksize_t blksize_t;
typedef __blkcnt64_t blkcnt_t;
typedef __fsblkcnt64_t fsblkcnt_t;
typedef __fsfilcnt64_t fsfilcnt_t;
typedef __blkcnt64_t blkcnt64_t;
typedef __fsblkcnt64_t fsblkcnt64_t;
typedef __fsfilcnt64_t fsfilcnt64_t;
typedef unsigned long int pthread_t;
typedef union
{
char __size[56];
long int __align;
} pthread_attr_t;
typedef struct __pthread_internal_list
{
struct __pthread_internal_list *__prev;
struct __pthread_internal_list *__next;
} __pthread_list_t;
typedef union
{
struct __pthread_mutex_s
{
int __lock;
unsigned int __count;
int __owner;
unsigned int __nusers;
int __kind;
int __spins;
__pthread_list_t __list;
} __data;
char __size[40];
long int __align;
} pthread_mutex_t;
typedef union
{
char __size[4];
int __align;
} pthread_mutexattr_t;
typedef union
{
struct
{
int __lock;
unsigned int __futex;
__extension__ unsigned long long int __total_seq;
__extension__ unsigned long long int __wakeup_seq;
__extension__ unsigned long long int __woken_seq;
void *__mutex;
unsigned int __nwaiters;
unsigned int __broadcast_seq;
} __data;
char __size[48];
__extension__ long long int __align;
} pthread_cond_t;
typedef union
{
char __size[4];
int __align;
} pthread_condattr_t;
typedef unsigned int pthread_key_t;
typedef int pthread_once_t;
typedef union
{
struct
{
int __lock;
unsigned int __nr_readers;
unsigned int __readers_wakeup;
unsigned int __writer_wakeup;
unsigned int __nr_readers_queued;
unsigned int __nr_writers_queued;
int __writer;
int __shared;
unsigned long int __pad1;
unsigned long int __pad2;
unsigned int __flags;
} __data;
char __size[56];
long int __align;
} pthread_rwlock_t;
typedef union
{
char __size[8];
long int __align;
} pthread_rwlockattr_t;
typedef volatile int pthread_spinlock_t;
typedef union
{
char __size[32];
long int __align;
} pthread_barrier_t;
typedef union
{
char __size[4];
int __align;
} pthread_barrierattr_t;
}
typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;
typedef unsigned int uint32_t;
typedef unsigned long int uint64_t;
typedef signed char int_least8_t;
typedef short int int_least16_t;
typedef int int_least32_t;
typedef long int int_least64_t;
typedef unsigned char uint_least8_t;
typedef unsigned short int uint_least16_t;
typedef unsigned int uint_least32_t;
typedef unsigned long int uint_least64_t;
typedef signed char int_fast8_t;
typedef long int int_fast16_t;
typedef long int int_fast32_t;
typedef long int int_fast64_t;
typedef unsigned char uint_fast8_t;
typedef unsigned long int uint_fast16_t;
typedef unsigned long int uint_fast32_t;
typedef unsigned long int uint_fast64_t;
typedef long int intptr_t;
typedef unsigned long int uintptr_t;
typedef long int intmax_t;
typedef unsigned long int uintmax_t;
extern "C" {
typedef struct
{
long int quot;
long int rem;
} imaxdiv_t;
extern intmax_t imaxabs (intmax_t __n) throw () __attribute__ ((__const__));
extern imaxdiv_t imaxdiv (intmax_t __numer, intmax_t __denom)
throw () __attribute__ ((__const__));
extern intmax_t strtoimax (__const char *__restrict __nptr,
char **__restrict __endptr, int __base) throw ();
extern uintmax_t strtoumax (__const char *__restrict __nptr,
char ** __restrict __endptr, int __base) throw ();
extern intmax_t wcstoimax (__const wchar_t *__restrict __nptr,
wchar_t **__restrict __endptr, int __base)
throw ();
extern uintmax_t wcstoumax (__const wchar_t *__restrict __nptr,
wchar_t ** __restrict __endptr, int __base)
throw ();
}
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef uint8_t ui8;
typedef uint16_t ui16;
typedef uint32_t ui32;
typedef uint64_t ui64;
typedef ui16 __attribute__((__may_alias__)) ui16a;
typedef ui32 __attribute__((__may_alias__)) ui32a;
typedef ui64 __attribute__((__may_alias__)) ui64a;
union u_u16 {
ui16a v;
struct {
ui8 lo8, hi8;
} __attribute__((__may_alias__)) u;
} __attribute__((__may_alias__));
union u_u32 {
ui32a v;
float __attribute__((__may_alias__)) f;
struct {
u_u16 lo16, hi16;
} u;
} __attribute__((__may_alias__));
union u_u64 {
ui64a v;
double __attribute__((__may_alias__)) f;
struct {
u_u32 lo32, hi32;
} u;
} __attribute__((__may_alias__));
typedef i64 SUPERLONG;
typedef ui16 wchar16;
typedef wchar16 TChar;
typedef ui32 wchar32;
typedef i32 dochandle;
typedef ui32 udochandle;
template <bool>
struct TStaticAssertionFailed;
template <>
struct TStaticAssertionFailed <true> {
};
template <int x>
struct TStaticAssertTest {
};
template<int> struct TCompileTimeError;
template<> struct TCompileTimeError<true> {};
struct TNone {
enum {
Length = 0
};
template <class V>
struct THave {
enum {
Result = false
};
};
template <template <class> class P>
struct TSelectBy {
typedef TNone TResult;
};
};
typedef long int ptrdiff_t;
namespace std __attribute__ ((__visibility__ ("default"))) {
using ::ptrdiff_t;
using ::size_t;
}
extern "C" {
extern void *memcpy (void *__restrict __dest,
__const void *__restrict __src, size_t __n)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern void *memmove (void *__dest, __const void *__src, size_t __n)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern void *memccpy (void *__restrict __dest, __const void *__restrict __src,
int __c, size_t __n)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern void *memset (void *__s, int __c, size_t __n) throw () __attribute__ ((__nonnull__ (1)));
extern int memcmp (__const void *__s1, __const void *__s2, size_t __n)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern void *memchr (__const void *__s, int __c, size_t __n)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern void *rawmemchr (__const void *__s, int __c)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern void *memrchr (__const void *__s, int __c, size_t __n)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern char *strcpy (char *__restrict __dest, __const char *__restrict __src)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern char *strncpy (char *__restrict __dest,
__const char *__restrict __src, size_t __n)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern char *strcat (char *__restrict __dest, __const char *__restrict __src)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern char *strncat (char *__restrict __dest, __const char *__restrict __src,
size_t __n) throw () __attribute__ ((__nonnull__ (1, 2)));
extern int strcmp (__const char *__s1, __const char *__s2)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern int strncmp (__const char *__s1, __const char *__s2, size_t __n)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern int strcoll (__const char *__s1, __const char *__s2)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern size_t strxfrm (char *__restrict __dest,
__const char *__restrict __src, size_t __n)
throw () __attribute__ ((__nonnull__ (2)));
typedef struct __locale_struct
{
struct __locale_data *__locales[13];
const unsigned short int *__ctype_b;
const int *__ctype_tolower;
const int *__ctype_toupper;
const char *__names[13];
} *__locale_t;
typedef __locale_t locale_t;
extern int strcoll_l (__const char *__s1, __const char *__s2, __locale_t __l)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2, 3)));
extern size_t strxfrm_l (char *__dest, __const char *__src, size_t __n,
__locale_t __l) throw () __attribute__ ((__nonnull__ (2, 4)));
extern char *strdup (__const char *__s)
throw () __attribute__ ((__malloc__)) __attribute__ ((__nonnull__ (1)));
extern char *strndup (__const char *__string, size_t __n)
throw () __attribute__ ((__malloc__)) __attribute__ ((__nonnull__ (1)));
extern char *strchr (__const char *__s, int __c)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern char *strrchr (__const char *__s, int __c)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern char *strchrnul (__const char *__s, int __c)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern size_t strcspn (__const char *__s, __const char *__reject)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern size_t strspn (__const char *__s, __const char *__accept)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strpbrk (__const char *__s, __const char *__accept)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strstr (__const char *__haystack, __const char *__needle)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strtok (char *__restrict __s, __const char *__restrict __delim)
throw () __attribute__ ((__nonnull__ (2)));
extern char *__strtok_r (char *__restrict __s,
__const char *__restrict __delim,
char **__restrict __save_ptr)
throw () __attribute__ ((__nonnull__ (2, 3)));
extern char *strtok_r (char *__restrict __s, __const char *__restrict __delim,
char **__restrict __save_ptr)
throw () __attribute__ ((__nonnull__ (2, 3)));
extern char *strcasestr (__const char *__haystack, __const char *__needle)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern void *memmem (__const void *__haystack, size_t __haystacklen,
__const void *__needle, size_t __needlelen)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 3)));
extern void *__mempcpy (void *__restrict __dest,
__const void *__restrict __src, size_t __n)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern void *mempcpy (void *__restrict __dest,
__const void *__restrict __src, size_t __n)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern size_t strlen (__const char *__s)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern size_t strnlen (__const char *__string, size_t __maxlen)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern char *strerror (int __errnum) throw ();
extern char *strerror_r (int __errnum, char *__buf, size_t __buflen)
throw () __attribute__ ((__nonnull__ (2)));
extern char *strerror_l (int __errnum, __locale_t __l) throw ();
extern void __bzero (void *__s, size_t __n) throw () __attribute__ ((__nonnull__ (1)));
extern void bcopy (__const void *__src, void *__dest, size_t __n)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern void bzero (void *__s, size_t __n) throw () __attribute__ ((__nonnull__ (1)));
extern int bcmp (__const void *__s1, __const void *__s2, size_t __n)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *index (__const char *__s, int __c)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern char *rindex (__const char *__s, int __c)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1)));
extern int ffs (int __i) throw () __attribute__ ((__const__));
extern int ffsl (long int __l) throw () __attribute__ ((__const__));
__extension__ extern int ffsll (long long int __ll)
throw () __attribute__ ((__const__));
extern int strcasecmp (__const char *__s1, __const char *__s2)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern int strncasecmp (__const char *__s1, __const char *__s2, size_t __n)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern int strcasecmp_l (__const char *__s1, __const char *__s2,
__locale_t __loc)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2, 3)));
extern int strncasecmp_l (__const char *__s1, __const char *__s2,
size_t __n, __locale_t __loc)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2, 4)));
extern char *strsep (char **__restrict __stringp,
__const char *__restrict __delim)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern char *strsignal (int __sig) throw ();
extern char *__stpcpy (char *__restrict __dest, __const char *__restrict __src)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern char *stpcpy (char *__restrict __dest, __const char *__restrict __src)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern char *__stpncpy (char *__restrict __dest,
__const char *__restrict __src, size_t __n)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern char *stpncpy (char *__restrict __dest,
__const char *__restrict __src, size_t __n)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern int strverscmp (__const char *__s1, __const char *__s2)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1, 2)));
extern char *strfry (char *__string) throw () __attribute__ ((__nonnull__ (1)));
extern void *memfrob (void *__s, size_t __n) throw () __attribute__ ((__nonnull__ (1)));
extern char *basename (__const char *__filename) throw () __attribute__ ((__nonnull__ (1)));
}
namespace std __attribute__ ((__visibility__ ("default"))) {
using ::memchr;
using ::memcmp;
using ::memcpy;
using ::memmove;
using ::memset;
using ::strcat;
using ::strcmp;
using ::strcoll;
using ::strcpy;
using ::strcspn;
using ::strerror;
using ::strlen;
using ::strncat;
using ::strncmp;
using ::strncpy;
using ::strspn;
using ::strtok;
using ::strxfrm;
using ::strchr;
using ::strpbrk;
using ::strrchr;
using ::strstr;
inline void*
memchr(void* __p, int __c, size_t __n)
{ return memchr(const_cast<const void*>(__p), __c, __n); }
inline char*
strchr(char* __s1, int __n)
{ return __builtin_strchr(const_cast<const char*>(__s1), __n); }
inline char*
strpbrk(char* __s1, const char* __s2)
{ return __builtin_strpbrk(const_cast<const char*>(__s1), __s2); }
inline char*
strrchr(char* __s1, int __n)
{ return __builtin_strrchr(const_cast<const char*>(__s1), __n); }
inline char*
strstr(char* __s1, const char* __s2)
{ return __builtin_strstr(const_cast<const char*>(__s1), __s2); }
}
namespace NStl {
using __std_alias::size_t;
using __std_alias::memmove;
using __std_alias::memcpy;
using __std_alias::strcoll;
using __std_alias::strerror;
using __std_alias::strxfrm;
using __std_alias::memchr;
using __std_alias::strchr;
using __std_alias::strpbrk;
using __std_alias::strrchr;
using __std_alias::strstr;
using __std_alias::memcmp;
using __std_alias::memset;
using __std_alias::strcat;
using __std_alias::strcmp;
using __std_alias::strcpy;
using __std_alias::strcspn;
using __std_alias::strlen;
using __std_alias::strncat;
using __std_alias::strncmp;
using __std_alias::strncpy;
using __std_alias::strspn;
using __std_alias::strtok;
}
namespace NStl {
struct __true_type {};
struct __false_type {};
} namespace NStlPriv {
using ::NStl::__true_type;
using ::NStl::__false_type;
} namespace NStl {
template <int _Is>
struct __bool2type
{ typedef __true_type _Ret; };
template<>
struct __bool2type<1> { typedef __true_type _Ret; };
template<>
struct __bool2type<0> { typedef __false_type _Ret; };
template <class __bool_type>
struct __type2bool { enum {_Ret = 1}; };
template<>
struct __type2bool<__true_type> { enum {_Ret = 1}; };
template<>
struct __type2bool<__false_type> { enum {_Ret = 0}; };
template <class _BoolType>
struct _Not { typedef __false_type _Ret; };
template<>
struct _Not<__false_type> { typedef __true_type _Ret; };
template <class _P1, class _P2>
struct _Land2 { typedef __false_type _Ret; };
template<>
struct _Land2<__true_type, __true_type> { typedef __true_type _Ret; };
template <class _P1, class _P2, class _P3>
struct _Land3 { typedef __false_type _Ret; };
template<>
struct _Land3<__true_type, __true_type, __true_type> { typedef __true_type _Ret; };
template <class _P1, class _P2>
struct _Lor2 { typedef __true_type _Ret; };
template<>
struct _Lor2<__false_type, __false_type> { typedef __false_type _Ret; };
template <class _P1, class _P2, class _P3>
struct _Lor3 { typedef __true_type _Ret; };
template<>
struct _Lor3<__false_type, __false_type, __false_type> { typedef __false_type _Ret; };
template <bool _Cond, class _Tp1, class _Tp2>
struct __select { typedef _Tp1 _Ret; };
template <class _Tp1, class _Tp2>
struct __select<false, _Tp1, _Tp2> { typedef _Tp2 _Ret; };
template <class _Tp1, class _Tp2>
struct _IsSameAux {
typedef __false_type _RetT;
enum { _Ret = 0 };
};
template <class _Tp>
struct _UnConstType { typedef _Tp _Type; };
template <class _Tp>
struct _UnVolatileType { typedef _Tp _Type; };
template <class _Tp>
struct _UnCVType {
typedef typename _UnVolatileType<_Tp>::_Type _UnVType;
typedef typename _UnConstType<_UnVType>::_Type _Type;
};
template <class _Tp>
struct _IsSameAux<_Tp, _Tp> {
typedef __true_type _RetT;
enum { _Ret = 1 };
};
template <class _Tp>
struct _UnConstType<const _Tp> { typedef _Tp _Type; };
template <class _Tp>
struct _UnVolatileType<volatile _Tp> { typedef _Tp _Type; };
template <class _Tp1, class _Tp2>
struct _IsSame {
typedef typename _UnCVType<_Tp1>::_Type _Type1;
typedef typename _UnCVType<_Tp2>::_Type _Type2;
typedef _IsSameAux<_Type1, _Type2> _Aux;
enum { _Ret = _Aux::_Ret };
typedef typename _Aux::_RetT _RetT;
};
template <class _Tp1, class _Tp2>
struct _AreSameUnCVTypes {
enum { _Same = _IsSame<_Tp1, _Tp2>::_Ret };
typedef typename _IsSame<_Tp1, _Tp2>::_RetT _Ret;
};
template <class _Src, class _Dst>
struct _ConversionHelper {
static char _Test(bool, _Dst);
static char* _Test(bool, ...);
static _Src _MakeSource();
};
template <class _Src, class _Dst>
struct _IsConvertible {
typedef _ConversionHelper<_Src*, const volatile _Dst*> _H;
enum { value = (sizeof(char) == sizeof(_H::_Test(false, _H::_MakeSource()))) };
typedef typename __bool2type<value>::_Ret _Ret;
};
template <class _Src, class _Dst>
struct _IsCVConvertible {
typedef _ConversionHelper<_Src, _Dst> _H;
enum { value = (sizeof(char) == sizeof(_H::_Test(false, _H::_MakeSource()))) };
typedef typename __bool2type<value>::_Ret _Ret;
};
template <class _Tp>
struct _IsConst { typedef __false_type _Ret; };
template <class _Tp>
struct _IsConst <const _Tp> { typedef __true_type _Ret; };
}
namespace NStl {
template <class _Tp> struct _IsIntegral
{ typedef __false_type _Ret; };
template<> struct _IsIntegral<bool>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<char>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<signed char>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<unsigned char>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<wchar_t>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<short>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<unsigned short>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<int>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<unsigned int>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<long>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<unsigned long>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<long long>
{ typedef __true_type _Ret; };
template<> struct _IsIntegral<unsigned long long>
{ typedef __true_type _Ret; };
template <class _Tp> struct _IsRational
{ typedef __false_type _Ret; };
template<> struct _IsRational<float>
{ typedef __true_type _Ret; };
template<> struct _IsRational<double>
{ typedef __true_type _Ret; };
template<> struct _IsRational<long double>
{ typedef __true_type _Ret; };
template <class _Tp> struct __type_traits;
template <class _IsPOD> struct __type_traits_aux {
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};
template<>
struct __type_traits_aux<__false_type> {
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};
template<>
struct __type_traits_aux<__true_type> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
template <class _Tp>
struct _IsRef {
typedef __false_type _Ret;
};
template <class _Tp> struct _IsPtr {
typedef __false_type _Ret;
};
template <class _Tp>
struct __type_traits {
typedef __true_type this_dummy_member_must_be_first;
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};
template <class _Tp> struct _IsPtr<_Tp*>
{ typedef __true_type _Ret; };
template <class _Tp> struct _IsRef<_Tp&>
{ typedef __true_type _Ret; };
template <class _Tp> struct __type_traits<_Tp*> : __type_traits_aux<__true_type>
{};
template<> struct __type_traits< bool > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const bool > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile bool > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile bool > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< char > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const char > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile char > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile char > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< signed char > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const signed char > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile signed char > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile signed char > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< unsigned char > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const unsigned char > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile unsigned char > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile unsigned char > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< wchar_t > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const wchar_t > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile wchar_t > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile wchar_t > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< short > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const short > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile short > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile short > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< unsigned short > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const unsigned short > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile unsigned short > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile unsigned short > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< int > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const int > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile int > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile int > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< unsigned int > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const unsigned int > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile unsigned int > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile unsigned int > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile long > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< unsigned long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const unsigned long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile unsigned long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile unsigned long > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< long long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const long long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile long long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile long long > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< unsigned long long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const unsigned long long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile unsigned long long > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile unsigned long long > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< float > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const float > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile float > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile float > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< double > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const double > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile double > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile double > : __type_traits_aux<__true_type> {};
template<> struct __type_traits< long double > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const long double > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< volatile long double > : __type_traits_aux<__true_type> {}; template<> struct __type_traits< const volatile long double > : __type_traits_aux<__true_type> {};
template <class _ArePtrs, class _Src, class _Dst>
struct _IsCVConvertibleIf
{ typedef typename _IsCVConvertible<_Src, _Dst>::_Ret _Ret; };
template <class _Src, class _Dst>
struct _IsCVConvertibleIf<__false_type, _Src, _Dst>
{ typedef __false_type _Ret; };
template <class _Src, class _Dst>
struct _TrivialNativeTypeCopy {
typedef typename _IsPtr<_Src>::_Ret _Ptr1;
typedef typename _IsPtr<_Dst>::_Ret _Ptr2;
typedef typename _Land2<_Ptr1, _Ptr2>::_Ret _BothPtrs;
typedef typename _IsCVConvertibleIf<_BothPtrs, _Src, _Dst>::_Ret _Convertible;
typedef typename _Land2<_BothPtrs, _Convertible>::_Ret _Trivial1;
typedef typename __bool2type<(sizeof(_Src) == sizeof(_Dst))>::_Ret _SameSize;
typedef typename _IsIntegral<_Src>::_Ret _Int1;
typedef typename _IsIntegral<_Dst>::_Ret _Int2;
typedef typename _Land2<_Int1, _Int2>::_Ret _BothInts;
typedef typename _IsRational<_Src>::_Ret _Rat1;
typedef typename _IsRational<_Dst>::_Ret _Rat2;
typedef typename _Land2<_Rat1, _Rat2>::_Ret _BothRats;
typedef typename _Lor2<_BothInts, _BothRats>::_Ret _BothNatives;
typedef typename _Land2<_BothNatives, _SameSize>::_Ret _Trivial2;
typedef typename _Lor2<_Trivial1, _Trivial2>::_Ret _Ret;
};
template <class _Src, class _Dst>
struct _TrivialCopy {
typedef typename _TrivialNativeTypeCopy<_Src, _Dst>::_Ret _NativeRet;
typedef typename __type_traits<_Src>::has_trivial_assignment_operator _Tr1;
typedef typename _AreSameUnCVTypes<_Src, _Dst>::_Ret _Tr2;
typedef typename _Land2<_Tr1, _Tr2>::_Ret _UserRet;
typedef typename _Lor2<_NativeRet, _UserRet>::_Ret _Ret;
static _Ret _Answer() { return _Ret(); }
};
template <class _Src, class _Dst>
struct _TrivialUCopy {
typedef typename _TrivialNativeTypeCopy<_Src, _Dst>::_Ret _NativeRet;
typedef typename __type_traits<_Src>::has_trivial_copy_constructor _Tr1;
typedef typename _AreSameUnCVTypes<_Src, _Dst>::_Ret _Tr2;
typedef typename _Land2<_Tr1, _Tr2>::_Ret _UserRet;
typedef typename _Lor2<_NativeRet, _UserRet>::_Ret _Ret;
static _Ret _Answer() { return _Ret(); }
};
template <class _Tp>
struct _DefaultZeroValue {
typedef typename _IsIntegral<_Tp>::_Ret _Tr1;
typedef typename _IsRational<_Tp>::_Ret _Tr2;
typedef typename _IsPtr<_Tp>::_Ret _Tr3;
typedef typename _Lor3<_Tr1, _Tr2, _Tr3>::_Ret _Ret;
};
template <class _Tp>
struct _TrivialInit {
typedef typename __type_traits<_Tp>::has_trivial_default_constructor _Tr1;
typedef typename _DefaultZeroValue<_Tp>::_Ret _Tr2;
typedef typename _Not<_Tr2>::_Ret _Tr3;
typedef typename _Land2<_Tr1, _Tr3>::_Ret _Ret;
static _Ret _Answer() { return _Ret(); }
};
template <class _Tp>
struct _IsPtrType {
typedef typename _IsPtr<_Tp>::_Ret _Type;
static _Type _Ret() { return _Type(); }
};
template <class _Tp>
struct _IsRefType {
typedef typename _IsRef<_Tp>::_Ret _Type;
static _Type _Ret() { return _Type();}
};
template <class _Tp>
struct __call_traits {
typedef const _Tp& param_type;
};
template <class _Tp>
struct __call_traits<_Tp&>
{ typedef _Tp& param_type; };
template <class _Tp1, class _Tp2>
struct _BothPtrType {
typedef typename _IsPtr<_Tp1>::_Ret _IsPtr1;
typedef typename _IsPtr<_Tp2>::_Ret _IsPtr2;
typedef typename _Land2<_IsPtr1, _IsPtr2>::_Ret _Ret;
static _Ret _Answer() { return _Ret(); }
};
template <class _Tp1, class _Tp2, class _IsRef1, class _IsRef2>
struct _OKToSwap {
typedef typename _AreSameUnCVTypes<_Tp1, _Tp2>::_Ret _Same;
typedef typename _Land3<_Same, _IsRef1, _IsRef2>::_Ret _Type;
static _Type _Answer() { return _Type(); }
};
template <class _Tp1, class _Tp2, class _IsRef1, class _IsRef2>
inline _OKToSwap<_Tp1, _Tp2, _IsRef1, _IsRef2>
_IsOKToSwap(_Tp1*, _Tp2*, const _IsRef1&, const _IsRef2&)
{ return _OKToSwap<_Tp1, _Tp2, _IsRef1, _IsRef2>(); }
template <class _Src, class _Dst>
inline _TrivialCopy<_Src, _Dst> _UseTrivialCopy(_Src*, _Dst*)
{ return _TrivialCopy<_Src, _Dst>(); }
template <class _Src, class _Dst>
inline _TrivialUCopy<_Src, _Dst> _UseTrivialUCopy(_Src*, _Dst*)
{ return _TrivialUCopy<_Src, _Dst>(); }
template <class _Tp>
inline _TrivialInit<_Tp> _UseTrivialInit(_Tp*)
{ return _TrivialInit<_Tp>(); }
template <class _Tp>
struct _IsPOD {
typedef typename __type_traits<_Tp>::is_POD_type _Type;
static _Type _Answer() { return _Type(); }
};
template <class _Tp>
inline _IsPOD<_Tp> _Is_POD(_Tp*)
{ return _IsPOD<_Tp>(); }
template <class _Tp>
struct _DefaultZeroValueQuestion {
typedef typename _DefaultZeroValue<_Tp>::_Ret _Ret;
static _Ret _Answer() { return _Ret(); }
};
template <class _Tp>
inline _DefaultZeroValueQuestion<_Tp> _HasDefaultZeroValue(_Tp*)
{ return _DefaultZeroValueQuestion<_Tp>(); }
template <class _Tp>
struct __stlport_class
{ typedef _Tp _Type; };
template <class _Tp>
struct _IsSTLportClass {
typedef typename _IsConvertible<_Tp, __stlport_class<_Tp> >::_Ret _Ret;
};
template <class _Tp>
class _TpWithState : private _Tp {
_TpWithState();
int _state;
};
template <class _Tp>
struct _IsStateless {
enum { _Is = sizeof(_TpWithState<_Tp>) == sizeof(int) };
typedef typename __bool2type<_Is>::_Ret _Ret;
};
}
namespace NStl {
template <class _Tp>
class __move_source {
public:
explicit __move_source (_Tp &_src) : _M_data(_src)
{}
_Tp& get() const
{ return _M_data; }
private:
_Tp &_M_data;
typedef __move_source<_Tp> _Self;
_Self& operator = (_Self const&);
};
template <class _Tp>
struct __move_traits {
typedef __false_type implemented;
typedef typename __type_traits<_Tp>::has_trivial_destructor complete;
};
typedef __true_type __stlp_movable;
} namespace NStlPriv {
template <class _Tp>
struct _MoveSourceTraits {
typedef typename __move_traits<_Tp>::implemented _MvImpRet;
enum {_MvImp = __type2bool<_MvImpRet>::_Ret};
typedef typename __select<_MvImp,
__move_source<_Tp>,
_Tp const&>::_Ret _Type;
};
template <class _Tp>
inline typename _MoveSourceTraits<_Tp>::_Type
_AsMoveSource (_Tp &src) {
typedef typename _MoveSourceTraits<_Tp>::_Type _SrcType;
return _SrcType(src);
}
template <class _Tp>
struct __move_traits_aux {
typedef typename __move_traits<_Tp>::implemented implemented;
typedef typename __move_traits<_Tp>::complete complete;
};
template <class _Tp1, class _Tp2>
struct __move_traits_aux2 {
typedef __move_traits<_Tp1> _MoveTraits1;
typedef __move_traits<_Tp2> _MoveTraits2;
typedef typename _Lor2<typename _MoveTraits1::implemented,
typename _MoveTraits2::implemented>::_Ret implemented;
typedef typename _Land2<typename _MoveTraits1::complete,
typename _MoveTraits2::complete>::_Ret complete;
};
template <class _Tp>
struct __move_traits_help {
typedef __true_type implemented;
typedef typename __move_traits<_Tp>::complete complete;
};
template <class _Tp1, class _Tp2>
struct __move_traits_help1 {
typedef __move_traits<_Tp1> _MoveTraits1;
typedef __move_traits<_Tp2> _MoveTraits2;
typedef typename _Lor2<typename _MoveTraits1::implemented,
typename _MoveTraits2::implemented>::_Ret implemented;
typedef typename _Land2<typename _MoveTraits1::complete,
typename _MoveTraits2::complete>::_Ret complete;
};
template <class _Tp1, class _Tp2>
struct __move_traits_help2 {
typedef __move_traits<_Tp1> _MoveTraits1;
typedef __move_traits<_Tp2> _MoveTraits2;
typedef __stlp_movable implemented;
typedef typename _Land2<typename _MoveTraits1::complete,
typename _MoveTraits2::complete>::_Ret complete;
};
} namespace NStl {
}
namespace NStl {
template <class _T1, class _T2>
struct pair {
typedef _T1 first_type;
typedef _T2 second_type;
_T1 first;
_T2 second;
pair() : first(_T1()), second(_T2()) {}
pair(const _T1& __a, const _T2& __b) : first(__a), second(__b) {}
template <class _U1, class _U2>
pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {}
pair(const pair<_T1,_T2>& __o) : first(__o.first), second(__o.second) {}
pair(__move_source<pair<_T1, _T2> > src) : first(::NStlPriv:: _AsMoveSource(src.get().first)),
second(::NStlPriv:: _AsMoveSource(src.get().second))
{}
};
template <class _T1, class _T2>
inline bool operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return __x.first == __y.first && __x.second == __y.second; }
template <class _T1, class _T2>
inline bool operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) {
return __x.first < __y.first ||
(!(__y.first < __x.first) && __x.second < __y.second);
}
template <class _T1, class _T2>
inline bool operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return !(__x == __y); }
template <class _T1, class _T2>
inline bool operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return __y < __x; }
template <class _T1, class _T2>
inline bool operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return !(__y < __x); }
template <class _T1, class _T2>
inline bool operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
{ return !(__x < __y); }
template <class _T1, class _T2, int _Sz>
inline pair<_T1, _T2 const*> make_pair(_T1 const& __x,
_T2 const (&__y)[_Sz])
{ return pair<_T1, _T2 const*>(__x, static_cast<_T2 const*>(__y)); }
template <class _T1, class _T2, int _Sz>
inline pair<_T1 const*, _T2> make_pair(_T1 const (&__x)[_Sz],
_T2 const& __y)
{ return pair<_T1 const*, _T2>(static_cast<_T1 const*>(__x), __y); }
template <class _T1, class _T2, int _Sz1, int _Sz2>
inline pair<_T1 const*, _T2 const*> make_pair(_T1 const (&__x)[_Sz1],
_T2 const (&__y)[_Sz2]) {
return pair<_T1 const*, _T2 const*>(static_cast<_T1 const*>(__x),
static_cast<_T2 const*>(__y));
}
template <class _T1, class _T2>
inline pair<_T1, _T2> make_pair(_T1 __x, _T2 __y)
{ return pair<_T1, _T2>(__x, __y); }
}
namespace NStl { namespace rel_ops {
template <class _Tp>
inline bool operator!=(const _Tp& __x, const _Tp& __y)
{ return !(__x == __y); }
template <class _Tp>
inline bool operator>(const _Tp& __x, const _Tp& __y)
{ return __y < __x; }
template <class _Tp>
inline bool operator<=(const _Tp& __x, const _Tp& __y)
{ return !(__y < __x); }
template <class _Tp>
inline bool operator>=(const _Tp& __x, const _Tp& __y)
{ return !(__x < __y); }
} }
namespace NStl {
template <class _T1, class _T2>
struct __type_traits<pair<_T1, _T2> > {
typedef __type_traits<_T1> _T1Traits;
typedef __type_traits<_T2> _T2Traits;
typedef typename _Land2<typename _T1Traits::has_trivial_default_constructor,
typename _T2Traits::has_trivial_default_constructor>::_Ret has_trivial_default_constructor;
typedef typename _Land2<typename _T1Traits::has_trivial_copy_constructor,
typename _T2Traits::has_trivial_copy_constructor>::_Ret has_trivial_copy_constructor;
typedef typename _Land2<typename _T1Traits::has_trivial_assignment_operator,
typename _T2Traits::has_trivial_assignment_operator>::_Ret has_trivial_assignment_operator;
typedef typename _Land2<typename _T1Traits::has_trivial_destructor,
typename _T2Traits::has_trivial_destructor>::_Ret has_trivial_destructor;
typedef __false_type is_POD_type;
};
template <class _T1, class _T2>
struct __move_traits<pair<_T1, _T2> >
: ::NStlPriv:: __move_traits_help1<_T1, _T2> {};
}
template <class T1, class T2 = T1>
struct TPair : NStl::pair<T1, T2> {
typedef T1 TFirst;
typedef T2 TSecond;
TPair() {
}
TPair(const T1& x, const T2& y)
: NStl::pair<T1, T2> (x, y)
{
}
TPair(NStl::__move_source<TPair<T1, T2> > src)
: NStl::pair<T1, T2> (src)
{
}
TPair(NStl::__move_source<NStl::pair<T1, T2> > src)
: NStl::pair<T1, T2> (src)
{
}
template <class TU, class TV>
TPair(const NStl::pair<TU, TV>& p)
: NStl::pair<T1, T2>(p)
{
}
template <class TU, class TV>
TPair(const TPair<TU, TV>& p)
: NStl::pair<T1, T2>(p)
{
}
TFirst& First() {
return this->first;
}
TSecond& Second() {
return this->second;
}
const TFirst& First() const {
return this->first;
}
const TSecond& Second() const {
return this->second;
}
};
template<class T1, class T2>
inline TPair<T1, T2> MakePair(T1 v1, T2 v2) {
return (TPair<T1, T2>(v1, v2));
}
template<class T>
inline TPair<T, T> MakePair(T v) {
return (TPair<T, T>(v, v));
}
typedef TPair<ui64, ui64> uint128;
inline ui64 Uint128Low64(const uint128& x) {
return x.first;
}
inline ui64 Uint128High64(const uint128& x) {
return x.second;
}
ui64 CityHash64(const char* buf, size_t len);
ui64 CityHash64WithSeed(const char* buf, size_t len, ui64 seed);
ui64 CityHash64WithSeeds(const char* buf, size_t len, ui64 seed0, ui64 seed1);
uint128 CityHash128(const char* s, size_t len);
uint128 CityHash128WithSeed(const char* s, size_t len, uint128 seed);
inline ui64 Hash128to64(const uint128& x) {
const ui64 kMul = 0x9ddfea08eb382d69ULL;
ui64 a = (Uint128Low64(x) ^ Uint128High64(x)) * kMul;
a ^= (a >> 47);
ui64 b = (Uint128High64(x) ^ a) * kMul;
b ^= (b >> 47);
b *= kMul;
return b;
}
typedef ui8 uint8;
typedef ui32 uint32;
typedef ui64 uint64;
extern "C" {
struct _IO_FILE;
typedef struct _IO_FILE FILE;
typedef struct _IO_FILE __FILE;
typedef struct
{
int __count;
union
{
unsigned int __wch;
char __wchb[4];
} __value;
} __mbstate_t;
typedef struct
{
__off_t __pos;
__mbstate_t __state;
} _G_fpos_t;
typedef struct
{
__off64_t __pos;
__mbstate_t __state;
} _G_fpos64_t;
typedef int _G_int16_t __attribute__ ((__mode__ (__HI__)));
typedef int _G_int32_t __attribute__ ((__mode__ (__SI__)));
typedef unsigned int _G_uint16_t __attribute__ ((__mode__ (__HI__)));
typedef unsigned int _G_uint32_t __attribute__ ((__mode__ (__SI__)));
typedef __builtin_va_list __gnuc_va_list;
struct _IO_jump_t; struct _IO_FILE;
typedef void _IO_lock_t;
struct _IO_marker {
struct _IO_marker *_next;
struct _IO_FILE *_sbuf;
int _pos;
};
enum __codecvt_result
{
__codecvt_ok,
__codecvt_partial,
__codecvt_error,
__codecvt_noconv
};
struct _IO_FILE {
int _flags;
char* _IO_read_ptr;
char* _IO_read_end;
char* _IO_read_base;
char* _IO_write_base;
char* _IO_write_ptr;
char* _IO_write_end;
char* _IO_buf_base;
char* _IO_buf_end;
char *_IO_save_base;
char *_IO_backup_base;
char *_IO_save_end;
struct _IO_marker *_markers;
struct _IO_FILE *_chain;
int _fileno;
int _flags2;
__off_t _old_offset;
unsigned short _cur_column;
signed char _vtable_offset;
char _shortbuf[1];
_IO_lock_t *_lock;
__off64_t _offset;
void *__pad1;
void *__pad2;
void *__pad3;
void *__pad4;
size_t __pad5;
int _mode;
char _unused2[15 * sizeof (int) - 4 * sizeof (void *) - sizeof (size_t)];
};
struct _IO_FILE_plus;
extern struct _IO_FILE_plus _IO_2_1_stdin_;
extern struct _IO_FILE_plus _IO_2_1_stdout_;
extern struct _IO_FILE_plus _IO_2_1_stderr_;
typedef __ssize_t __io_read_fn (void *__cookie, char *__buf, size_t __nbytes);
typedef __ssize_t __io_write_fn (void *__cookie, __const char *__buf,
size_t __n);
typedef int __io_seek_fn (void *__cookie, __off64_t *__pos, int __w);
typedef int __io_close_fn (void *__cookie);
typedef __io_read_fn cookie_read_function_t;
typedef __io_write_fn cookie_write_function_t;
typedef __io_seek_fn cookie_seek_function_t;
typedef __io_close_fn cookie_close_function_t;
typedef struct
{
__io_read_fn *read;
__io_write_fn *write;
__io_seek_fn *seek;
__io_close_fn *close;
} _IO_cookie_io_functions_t;
typedef _IO_cookie_io_functions_t cookie_io_functions_t;
struct _IO_cookie_file;
extern void _IO_cookie_init (struct _IO_cookie_file *__cfile, int __read_write,
void *__cookie, _IO_cookie_io_functions_t __fns);
extern "C" {
extern int __underflow (_IO_FILE *);
extern int __uflow (_IO_FILE *);
extern int __overflow (_IO_FILE *, int);
extern int _IO_getc (_IO_FILE *__fp);
extern int _IO_putc (int __c, _IO_FILE *__fp);
extern int _IO_feof (_IO_FILE *__fp) throw ();
extern int _IO_ferror (_IO_FILE *__fp) throw ();
extern int _IO_peekc_locked (_IO_FILE *__fp);
extern void _IO_flockfile (_IO_FILE *) throw ();
extern void _IO_funlockfile (_IO_FILE *) throw ();
extern int _IO_ftrylockfile (_IO_FILE *) throw ();
extern int _IO_vfscanf (_IO_FILE * __restrict, const char * __restrict,
__gnuc_va_list, int *__restrict);
extern int _IO_vfprintf (_IO_FILE *__restrict, const char *__restrict,
__gnuc_va_list);
extern __ssize_t _IO_padn (_IO_FILE *, int, __ssize_t);
extern size_t _IO_sgetn (_IO_FILE *, void *, size_t);
extern __off64_t _IO_seekoff (_IO_FILE *, __off64_t, int, int);
extern __off64_t _IO_seekpos (_IO_FILE *, __off64_t, int);
extern void _IO_free_backup_area (_IO_FILE *) throw ();
}
typedef __gnuc_va_list va_list;
typedef _G_fpos64_t fpos_t;
typedef _G_fpos64_t fpos64_t;
extern struct _IO_FILE *stdin;
extern struct _IO_FILE *stdout;
extern struct _IO_FILE *stderr;
extern int remove (__const char *__filename) throw ();
extern int rename (__const char *__old, __const char *__new) throw ();
extern int renameat (int __oldfd, __const char *__old, int __newfd,
__const char *__new) throw ();
extern FILE *tmpfile (void) __asm__ ("" "tmpfile64") ;
extern FILE *tmpfile64 (void) ;
extern char *tmpnam (char *__s) throw () ;
extern char *tmpnam_r (char *__s) throw () ;
extern char *tempnam (__const char *__dir, __const char *__pfx)
throw () __attribute__ ((__malloc__)) ;
extern int fclose (FILE *__stream);
extern int fflush (FILE *__stream);
extern int fflush_unlocked (FILE *__stream);
extern int fcloseall (void);
extern FILE *fopen (__const char *__restrict __filename, __const char *__restrict __modes) __asm__ ("" "fopen64")
;
extern FILE *freopen (__const char *__restrict __filename, __const char *__restrict __modes, FILE *__restrict __stream) __asm__ ("" "freopen64")
;
extern FILE *fopen64 (__const char *__restrict __filename,
__const char *__restrict __modes) ;
extern FILE *freopen64 (__const char *__restrict __filename,
__const char *__restrict __modes,
FILE *__restrict __stream) ;
extern FILE *fdopen (int __fd, __const char *__modes) throw () ;
extern FILE *fopencookie (void *__restrict __magic_cookie,
__const char *__restrict __modes,
_IO_cookie_io_functions_t __io_funcs) throw () ;
extern FILE *fmemopen (void *__s, size_t __len, __const char *__modes)
throw () ;
extern FILE *open_memstream (char **__bufloc, size_t *__sizeloc) throw () ;
extern void setbuf (FILE *__restrict __stream, char *__restrict __buf) throw ();
extern int setvbuf (FILE *__restrict __stream, char *__restrict __buf,
int __modes, size_t __n) throw ();
extern void setbuffer (FILE *__restrict __stream, char *__restrict __buf,
size_t __size) throw ();
extern void setlinebuf (FILE *__stream) throw ();
extern int fprintf (FILE *__restrict __stream,
__const char *__restrict __format, ...);
extern int printf (__const char *__restrict __format, ...);
extern int sprintf (char *__restrict __s,
__const char *__restrict __format, ...) throw ();
extern int vfprintf (FILE *__restrict __s, __const char *__restrict __format,
__gnuc_va_list __arg);
extern int vprintf (__const char *__restrict __format, __gnuc_va_list __arg);
extern int vsprintf (char *__restrict __s, __const char *__restrict __format,
__gnuc_va_list __arg) throw ();
extern int snprintf (char *__restrict __s, size_t __maxlen,
__const char *__restrict __format, ...)
throw () __attribute__ ((__format__ (__printf__, 3, 4)));
extern int vsnprintf (char *__restrict __s, size_t __maxlen,
__const char *__restrict __format, __gnuc_va_list __arg)
throw () __attribute__ ((__format__ (__printf__, 3, 0)));
extern int vasprintf (char **__restrict __ptr, __const char *__restrict __f,
__gnuc_va_list __arg)
throw () __attribute__ ((__format__ (__printf__, 2, 0))) ;
extern int __asprintf (char **__restrict __ptr,
__const char *__restrict __fmt, ...)
throw () __attribute__ ((__format__ (__printf__, 2, 3))) ;
extern int asprintf (char **__restrict __ptr,
__const char *__restrict __fmt, ...)
throw () __attribute__ ((__format__ (__printf__, 2, 3))) ;
extern int vdprintf (int __fd, __const char *__restrict __fmt,
__gnuc_va_list __arg)
__attribute__ ((__format__ (__printf__, 2, 0)));
extern int dprintf (int __fd, __const char *__restrict __fmt, ...)
__attribute__ ((__format__ (__printf__, 2, 3)));
extern int fscanf (FILE *__restrict __stream,
__const char *__restrict __format, ...) ;
extern int scanf (__const char *__restrict __format, ...) ;
extern int sscanf (__const char *__restrict __s,
__const char *__restrict __format, ...) throw ();
extern int vfscanf (FILE *__restrict __s, __const char *__restrict __format,
__gnuc_va_list __arg)
__attribute__ ((__format__ (__scanf__, 2, 0))) ;
extern int vscanf (__const char *__restrict __format, __gnuc_va_list __arg)
__attribute__ ((__format__ (__scanf__, 1, 0))) ;
extern int vsscanf (__const char *__restrict __s,
__const char *__restrict __format, __gnuc_va_list __arg)
throw () __attribute__ ((__format__ (__scanf__, 2, 0)));
extern int fgetc (FILE *__stream);
extern int getc (FILE *__stream);
extern int getchar (void);
extern int getc_unlocked (FILE *__stream);
extern int getchar_unlocked (void);
extern int fgetc_unlocked (FILE *__stream);
extern int fputc (int __c, FILE *__stream);
extern int putc (int __c, FILE *__stream);
extern int putchar (int __c);
extern int fputc_unlocked (int __c, FILE *__stream);
extern int putc_unlocked (int __c, FILE *__stream);
extern int putchar_unlocked (int __c);
extern int getw (FILE *__stream);
extern int putw (int __w, FILE *__stream);
extern char *fgets (char *__restrict __s, int __n, FILE *__restrict __stream)
;
extern char *gets (char *__s) ;
extern char *fgets_unlocked (char *__restrict __s, int __n,
FILE *__restrict __stream) ;
extern __ssize_t __getdelim (char **__restrict __lineptr,
size_t *__restrict __n, int __delimiter,
FILE *__restrict __stream) ;
extern __ssize_t getdelim (char **__restrict __lineptr,
size_t *__restrict __n, int __delimiter,
FILE *__restrict __stream) ;
extern __ssize_t getline (char **__restrict __lineptr,
size_t *__restrict __n,
FILE *__restrict __stream) ;
extern int fputs (__const char *__restrict __s, FILE *__restrict __stream);
extern int puts (__const char *__s);
extern int ungetc (int __c, FILE *__stream);
extern size_t fread (void *__restrict __ptr, size_t __size,
size_t __n, FILE *__restrict __stream) ;
extern size_t fwrite (__const void *__restrict __ptr, size_t __size,
size_t __n, FILE *__restrict __s);
extern int fputs_unlocked (__const char *__restrict __s,
FILE *__restrict __stream);
extern size_t fread_unlocked (void *__restrict __ptr, size_t __size,
size_t __n, FILE *__restrict __stream) ;
extern size_t fwrite_unlocked (__const void *__restrict __ptr, size_t __size,
size_t __n, FILE *__restrict __stream);
extern int fseek (FILE *__stream, long int __off, int __whence);
extern long int ftell (FILE *__stream) ;
extern void rewind (FILE *__stream);
extern int fseeko (FILE *__stream, __off64_t __off, int __whence) __asm__ ("" "fseeko64");
extern __off64_t ftello (FILE *__stream) __asm__ ("" "ftello64");
extern int fgetpos (FILE *__restrict __stream, fpos_t *__restrict __pos) __asm__ ("" "fgetpos64");
extern int fsetpos (FILE *__stream, __const fpos_t *__pos) __asm__ ("" "fsetpos64");
extern int fseeko64 (FILE *__stream, __off64_t __off, int __whence);
extern __off64_t ftello64 (FILE *__stream) ;
extern int fgetpos64 (FILE *__restrict __stream, fpos64_t *__restrict __pos);
extern int fsetpos64 (FILE *__stream, __const fpos64_t *__pos);
extern void clearerr (FILE *__stream) throw ();
extern int feof (FILE *__stream) throw () ;
extern int ferror (FILE *__stream) throw () ;
extern void clearerr_unlocked (FILE *__stream) throw ();
extern int feof_unlocked (FILE *__stream) throw () ;
extern int ferror_unlocked (FILE *__stream) throw () ;
extern void perror (__const char *__s);
extern int sys_nerr;
extern __const char *__const sys_errlist[];
extern int _sys_nerr;
extern __const char *__const _sys_errlist[];
extern int fileno (FILE *__stream) throw () ;
extern int fileno_unlocked (FILE *__stream) throw () ;
extern FILE *popen (__const char *__command, __const char *__modes) ;
extern int pclose (FILE *__stream);
extern char *ctermid (char *__s) throw ();
extern char *cuserid (char *__s);
struct obstack;
extern int obstack_printf (struct obstack *__restrict __obstack,
__const char *__restrict __format, ...)
throw () __attribute__ ((__format__ (__printf__, 2, 3)));
extern int obstack_vprintf (struct obstack *__restrict __obstack,
__const char *__restrict __format,
__gnuc_va_list __args)
throw () __attribute__ ((__format__ (__printf__, 2, 0)));
extern void flockfile (FILE *__stream) throw ();
extern int ftrylockfile (FILE *__stream) throw () ;
extern void funlockfile (FILE *__stream) throw ();
}
namespace std __attribute__ ((__visibility__ ("default"))) {
using ::FILE;
using ::fpos_t;
using ::clearerr;
using ::fclose;
using ::feof;
using ::ferror;
using ::fflush;
using ::fgetc;
using ::fgetpos;
using ::fgets;
using ::fopen;
using ::fprintf;
using ::fputc;
using ::fputs;
using ::fread;
using ::freopen;
using ::fscanf;
using ::fseek;
using ::fsetpos;
using ::ftell;
using ::fwrite;
using ::getc;
using ::getchar;
using ::gets;
using ::perror;
using ::printf;
using ::putc;
using ::putchar;
using ::puts;
using ::remove;
using ::rename;
using ::rewind;
using ::scanf;
using ::setbuf;
using ::setvbuf;
using ::sprintf;
using ::sscanf;
using ::tmpfile;
using ::tmpnam;
using ::ungetc;
using ::vfprintf;
using ::vprintf;
using ::vsprintf;
}
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
using ::snprintf;
using ::vfscanf;
using ::vscanf;
using ::vsnprintf;
using ::vsscanf;
}
namespace std __attribute__ ((__visibility__ ("default"))) {
using ::__gnu_cxx::snprintf;
using ::__gnu_cxx::vfscanf;
using ::__gnu_cxx::vscanf;
using ::__gnu_cxx::vsnprintf;
using ::__gnu_cxx::vsscanf;
}
namespace NStl {
using __std_alias::FILE;
using __std_alias::fpos_t;
using __std_alias::size_t;
using __std_alias::clearerr;
using __std_alias::fclose;
using __std_alias::feof;
using __std_alias::ferror;
using __std_alias::fflush;
using __std_alias::fgetc;
using __std_alias::fgetpos;
using __std_alias::fgets;
using __std_alias::fopen;
using __std_alias::fprintf;
using __std_alias::fputc;
using __std_alias::fputs;
using __std_alias::fread;
using __std_alias::freopen;
using __std_alias::fscanf;
using __std_alias::fseek;
using __std_alias::fsetpos;
using __std_alias::ftell;
using __std_alias::fwrite;
using __std_alias::getc;
using __std_alias::putc;
using __std_alias::getchar;
using __std_alias::putchar;
using __std_alias::gets;
using __std_alias::perror;
using __std_alias::printf;
using __std_alias::puts;
using __std_alias::remove;
using __std_alias::rename;
using __std_alias::rewind;
using __std_alias::setbuf;
using __std_alias::tmpfile;
using __std_alias::tmpnam;
using __std_alias::scanf;
using __std_alias::setvbuf;
using __std_alias::sprintf;
using __std_alias::sscanf;
using __std_alias::ungetc;
using __std_alias::vfprintf;
using __std_alias::vprintf;
using __std_alias::vsprintf;
}
namespace NStl {
using __std_alias::ptrdiff_t;
using __std_alias::size_t;
}
extern "C" {
union wait
{
int w_status;
struct
{
unsigned int __w_termsig:7;
unsigned int __w_coredump:1;
unsigned int __w_retcode:8;
unsigned int:16;
} __wait_terminated;
struct
{
unsigned int __w_stopval:8;
unsigned int __w_stopsig:8;
unsigned int:16;
} __wait_stopped;
};
typedef struct
{
int quot;
int rem;
} div_t;
typedef struct
{
long int quot;
long int rem;
} ldiv_t;
__extension__ typedef struct
{
long long int quot;
long long int rem;
} lldiv_t;
extern size_t __ctype_get_mb_cur_max (void) throw () ;
extern double atof (__const char *__nptr)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1))) ;
extern int atoi (__const char *__nptr)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1))) ;
extern long int atol (__const char *__nptr)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1))) ;
__extension__ extern long long int atoll (__const char *__nptr)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1))) ;
extern double strtod (__const char *__restrict __nptr,
char **__restrict __endptr)
throw () __attribute__ ((__nonnull__ (1))) ;
extern float strtof (__const char *__restrict __nptr,
char **__restrict __endptr) throw () __attribute__ ((__nonnull__ (1))) ;
extern long double strtold (__const char *__restrict __nptr,
char **__restrict __endptr)
throw () __attribute__ ((__nonnull__ (1))) ;
extern long int strtol (__const char *__restrict __nptr,
char **__restrict __endptr, int __base)
throw () __attribute__ ((__nonnull__ (1))) ;
extern unsigned long int strtoul (__const char *__restrict __nptr,
char **__restrict __endptr, int __base)
throw () __attribute__ ((__nonnull__ (1))) ;
__extension__
extern long long int strtoq (__const char *__restrict __nptr,
char **__restrict __endptr, int __base)
throw () __attribute__ ((__nonnull__ (1))) ;
__extension__
extern unsigned long long int strtouq (__const char *__restrict __nptr,
char **__restrict __endptr, int __base)
throw () __attribute__ ((__nonnull__ (1))) ;
__extension__
extern long long int strtoll (__const char *__restrict __nptr,
char **__restrict __endptr, int __base)
throw () __attribute__ ((__nonnull__ (1))) ;
__extension__
extern unsigned long long int strtoull (__const char *__restrict __nptr,
char **__restrict __endptr, int __base)
throw () __attribute__ ((__nonnull__ (1))) ;
extern long int strtol_l (__const char *__restrict __nptr,
char **__restrict __endptr, int __base,
__locale_t __loc) throw () __attribute__ ((__nonnull__ (1, 4))) ;
extern unsigned long int strtoul_l (__const char *__restrict __nptr,
char **__restrict __endptr,
int __base, __locale_t __loc)
throw () __attribute__ ((__nonnull__ (1, 4))) ;
__extension__
extern long long int strtoll_l (__const char *__restrict __nptr,
char **__restrict __endptr, int __base,
__locale_t __loc)
throw () __attribute__ ((__nonnull__ (1, 4))) ;
__extension__
extern unsigned long long int strtoull_l (__const char *__restrict __nptr,
char **__restrict __endptr,
int __base, __locale_t __loc)
throw () __attribute__ ((__nonnull__ (1, 4))) ;
extern double strtod_l (__const char *__restrict __nptr,
char **__restrict __endptr, __locale_t __loc)
throw () __attribute__ ((__nonnull__ (1, 3))) ;
extern float strtof_l (__const char *__restrict __nptr,
char **__restrict __endptr, __locale_t __loc)
throw () __attribute__ ((__nonnull__ (1, 3))) ;
extern long double strtold_l (__const char *__restrict __nptr,
char **__restrict __endptr,
__locale_t __loc)
throw () __attribute__ ((__nonnull__ (1, 3))) ;
extern char *l64a (long int __n) throw () ;
extern long int a64l (__const char *__s)
throw () __attribute__ ((__pure__)) __attribute__ ((__nonnull__ (1))) ;
extern long int random (void) throw ();
extern void srandom (unsigned int __seed) throw ();
extern char *initstate (unsigned int __seed, char *__statebuf,
size_t __statelen) throw () __attribute__ ((__nonnull__ (2)));
extern char *setstate (char *__statebuf) throw () __attribute__ ((__nonnull__ (1)));
struct random_data
{
int32_t *fptr;
int32_t *rptr;
int32_t *state;
int rand_type;
int rand_deg;
int rand_sep;
int32_t *end_ptr;
};
extern int random_r (struct random_data *__restrict __buf,
int32_t *__restrict __result) throw () __attribute__ ((__nonnull__ (1, 2)));
extern int srandom_r (unsigned int __seed, struct random_data *__buf)
throw () __attribute__ ((__nonnull__ (2)));
extern int initstate_r (unsigned int __seed, char *__restrict __statebuf,
size_t __statelen,
struct random_data *__restrict __buf)
throw () __attribute__ ((__nonnull__ (2, 4)));
extern int setstate_r (char *__restrict __statebuf,
struct random_data *__restrict __buf)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern int rand (void) throw ();
extern void srand (unsigned int __seed) throw ();
extern int rand_r (unsigned int *__seed) throw ();
extern double drand48 (void) throw ();
extern double erand48 (unsigned short int __xsubi[3]) throw () __attribute__ ((__nonnull__ (1)));
extern long int lrand48 (void) throw ();
extern long int nrand48 (unsigned short int __xsubi[3])
throw () __attribute__ ((__nonnull__ (1)));
extern long int mrand48 (void) throw ();
extern long int jrand48 (unsigned short int __xsubi[3])
throw () __attribute__ ((__nonnull__ (1)));
extern void srand48 (long int __seedval) throw ();
extern unsigned short int *seed48 (unsigned short int __seed16v[3])
throw () __attribute__ ((__nonnull__ (1)));
extern void lcong48 (unsigned short int __param[7]) throw () __attribute__ ((__nonnull__ (1)));
struct drand48_data
{
unsigned short int __x[3];
unsigned short int __old_x[3];
unsigned short int __c;
unsigned short int __init;
unsigned long long int __a;
};
extern int drand48_r (struct drand48_data *__restrict __buffer,
double *__restrict __result) throw () __attribute__ ((__nonnull__ (1, 2)));
extern int erand48_r (unsigned short int __xsubi[3],
struct drand48_data *__restrict __buffer,
double *__restrict __result) throw () __attribute__ ((__nonnull__ (1, 2)));
extern int lrand48_r (struct drand48_data *__restrict __buffer,
long int *__restrict __result)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern int nrand48_r (unsigned short int __xsubi[3],
struct drand48_data *__restrict __buffer,
long int *__restrict __result)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern int mrand48_r (struct drand48_data *__restrict __buffer,
long int *__restrict __result)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern int jrand48_r (unsigned short int __xsubi[3],
struct drand48_data *__restrict __buffer,
long int *__restrict __result)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern int srand48_r (long int __seedval, struct drand48_data *__buffer)
throw () __attribute__ ((__nonnull__ (2)));
extern int seed48_r (unsigned short int __seed16v[3],
struct drand48_data *__buffer) throw () __attribute__ ((__nonnull__ (1, 2)));
extern int lcong48_r (unsigned short int __param[7],
struct drand48_data *__buffer)
throw () __attribute__ ((__nonnull__ (1, 2)));
extern void *malloc (size_t __size) throw () __attribute__ ((__malloc__)) ;
extern void *calloc (size_t __nmemb, size_t __size)
throw () __attribute__ ((__malloc__)) ;
extern void *realloc (void *__ptr, size_t __size)
throw () __attribute__ ((__warn_unused_result__));
extern void free (void *__ptr) throw ();
extern void cfree (void *__ptr) throw ();
extern "C" {
extern void *alloca (size_t __size) throw ();
}
extern void *valloc (size_t __size) throw () __attribute__ ((__malloc__)) ;
extern int posix_memalign (void **__memptr, size_t __alignment, size_t __size)
throw () __attribute__ ((__nonnull__ (1))) ;
extern void abort (void) throw () __attribute__ ((__noreturn__));
extern int atexit (void (*__func) (void)) throw () __attribute__ ((__nonnull__ (1)));
extern "C++" int at_quick_exit (void (*__func) (void))
throw () __asm ("at_quick_exit") __attribute__ ((__nonnull__ (1)));
extern int on_exit (void (*__func) (int __status, void *__arg), void *__arg)
throw () __attribute__ ((__nonnull__ (1)));
extern void exit (int __status) throw () __attribute__ ((__noreturn__));
extern void quick_exit (int __status) throw () __attribute__ ((__noreturn__));
extern void _Exit (int __status) throw () __attribute__ ((__noreturn__));
extern char *getenv (__const char *__name) throw () __attribute__ ((__nonnull__ (1))) ;
extern char *__secure_getenv (__const char *__name)
throw () __attribute__ ((__nonnull__ (1))) ;
extern int putenv (char *__string) throw () __attribute__ ((__nonnull__ (1)));
extern int setenv (__const char *__name, __const char *__value, int __replace)
throw () __attribute__ ((__nonnull__ (2)));
extern int unsetenv (__const char *__name) throw () __attribute__ ((__nonnull__ (1)));
extern int clearenv (void) throw ();
extern char *mktemp (char *__template) throw () __attribute__ ((__nonnull__ (1))) ;
extern int mkstemp (char *__template) __asm__ ("" "mkstemp64")
__attribute__ ((__nonnull__ (1))) ;
extern int mkstemp64 (char *__template) __attribute__ ((__nonnull__ (1))) ;
extern int mkstemps (char *__template, int __suffixlen) __asm__ ("" "mkstemps64") __attribute__ ((__nonnull__ (1))) ;
extern int mkstemps64 (char *__template, int __suffixlen)
__attribute__ ((__nonnull__ (1))) ;
extern char *mkdtemp (char *__template) throw () __attribute__ ((__nonnull__ (1))) ;
extern int mkostemp (char *__template, int __flags) __asm__ ("" "mkostemp64")
__attribute__ ((__nonnull__ (1))) ;
extern int mkostemp64 (char *__template, int __flags) __attribute__ ((__nonnull__ (1))) ;
extern int mkostemps (char *__template, int __suffixlen, int __flags) __asm__ ("" "mkostemps64")
__attribute__ ((__nonnull__ (1))) ;
extern int mkostemps64 (char *__template, int __suffixlen, int __flags)
__attribute__ ((__nonnull__ (1))) ;
extern int system (__const char *__command) ;
extern char *canonicalize_file_name (__const char *__name)
throw () __attribute__ ((__nonnull__ (1))) ;
extern char *realpath (__const char *__restrict __name,
char *__restrict __resolved) throw () ;
typedef int (*__compar_fn_t) (__const void *, __const void *);
typedef __compar_fn_t comparison_fn_t;
typedef int (*__compar_d_fn_t) (__const void *, __const void *, void *);
extern void *bsearch (__const void *__key, __const void *__base,
size_t __nmemb, size_t __size, __compar_fn_t __compar)
__attribute__ ((__nonnull__ (1, 2, 5))) ;
extern void qsort (void *__base, size_t __nmemb, size_t __size,
__compar_fn_t __compar) __attribute__ ((__nonnull__ (1, 4)));
extern void qsort_r (void *__base, size_t __nmemb, size_t __size,
__compar_d_fn_t __compar, void *__arg)
__attribute__ ((__nonnull__ (1, 4)));
extern int abs (int __x) throw () __attribute__ ((__const__)) ;
extern long int labs (long int __x) throw () __attribute__ ((__const__)) ;
__extension__ extern long long int llabs (long long int __x)
throw () __attribute__ ((__const__)) ;
extern div_t div (int __numer, int __denom)
throw () __attribute__ ((__const__)) ;
extern ldiv_t ldiv (long int __numer, long int __denom)
throw () __attribute__ ((__const__)) ;
__extension__ extern lldiv_t lldiv (long long int __numer,
long long int __denom)
throw () __attribute__ ((__const__)) ;
extern char *ecvt (double __value, int __ndigit, int *__restrict __decpt,
int *__restrict __sign) throw () __attribute__ ((__nonnull__ (3, 4))) ;
extern char *fcvt (double __value, int __ndigit, int *__restrict __decpt,
int *__restrict __sign) throw () __attribute__ ((__nonnull__ (3, 4))) ;
extern char *gcvt (double __value, int __ndigit, char *__buf)
throw () __attribute__ ((__nonnull__ (3))) ;
extern char *qecvt (long double __value, int __ndigit,
int *__restrict __decpt, int *__restrict __sign)
throw () __attribute__ ((__nonnull__ (3, 4))) ;
extern char *qfcvt (long double __value, int __ndigit,
int *__restrict __decpt, int *__restrict __sign)
throw () __attribute__ ((__nonnull__ (3, 4))) ;
extern char *qgcvt (long double __value, int __ndigit, char *__buf)
throw () __attribute__ ((__nonnull__ (3))) ;
extern int ecvt_r (double __value, int __ndigit, int *__restrict __decpt,
int *__restrict __sign, char *__restrict __buf,
size_t __len) throw () __attribute__ ((__nonnull__ (3, 4, 5)));
extern int fcvt_r (double __value, int __ndigit, int *__restrict __decpt,
int *__restrict __sign, char *__restrict __buf,
size_t __len) throw () __attribute__ ((__nonnull__ (3, 4, 5)));
extern int qecvt_r (long double __value, int __ndigit,
int *__restrict __decpt, int *__restrict __sign,
char *__restrict __buf, size_t __len)
throw () __attribute__ ((__nonnull__ (3, 4, 5)));
extern int qfcvt_r (long double __value, int __ndigit,
int *__restrict __decpt, int *__restrict __sign,
char *__restrict __buf, size_t __len)
throw () __attribute__ ((__nonnull__ (3, 4, 5)));
extern int mblen (__const char *__s, size_t __n) throw () ;
extern int mbtowc (wchar_t *__restrict __pwc,
__const char *__restrict __s, size_t __n) throw () ;
extern int wctomb (char *__s, wchar_t __wchar) throw () ;
extern size_t mbstowcs (wchar_t *__restrict __pwcs,
__const char *__restrict __s, size_t __n) throw ();
extern size_t wcstombs (char *__restrict __s,
__const wchar_t *__restrict __pwcs, size_t __n)
throw ();
extern int rpmatch (__const char *__response) throw () __attribute__ ((__nonnull__ (1))) ;
extern int getsubopt (char **__restrict __optionp,
char *__const *__restrict __tokens,
char **__restrict __valuep)
throw () __attribute__ ((__nonnull__ (1, 2, 3))) ;
extern void setkey (__const char *__key) throw () __attribute__ ((__nonnull__ (1)));
extern int posix_openpt (int __oflag) ;
extern int grantpt (int __fd) throw ();
extern int unlockpt (int __fd) throw ();
extern char *ptsname (int __fd) throw () ;
extern int ptsname_r (int __fd, char *__buf, size_t __buflen)
throw () __attribute__ ((__nonnull__ (2)));
extern int getpt (void);
extern int getloadavg (double __loadavg[], int __nelem)
throw () __attribute__ ((__nonnull__ (1)));
}
namespace std __attribute__ ((__visibility__ ("default"))) {
using ::div_t;
using ::ldiv_t;
using ::abort;
using ::abs;
using ::atexit;
using ::atof;
using ::atoi;
using ::atol;
using ::bsearch;
using ::calloc;
using ::div;
using ::exit;
using ::free;
using ::getenv;
using ::labs;
using ::ldiv;
using ::malloc;
using ::mblen;
using ::mbstowcs;
using ::mbtowc;
using ::qsort;
using ::rand;
using ::realloc;
using ::srand;
using ::strtod;
using ::strtol;
using ::strtoul;
using ::system;
using ::wcstombs;
using ::wctomb;
inline long
abs(long __i) { return labs(__i); }
inline ldiv_t
div(long __i, long __j) { return ldiv(__i, __j); }
}
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
using ::lldiv_t;
using ::_Exit;
inline long long
abs(long long __x) { return __x >= 0 ? __x : -__x; }
using ::llabs;
inline lldiv_t
div(long long __n, long long __d)
{ lldiv_t __q; __q.quot = __n / __d; __q.rem = __n % __d; return __q; }
using ::lldiv;
using ::atoll;
using ::strtoll;
using ::strtoull;
using ::strtof;
using ::strtold;
}
namespace std __attribute__ ((__visibility__ ("default"))) {
using ::__gnu_cxx::lldiv_t;
using ::__gnu_cxx::_Exit;
using ::__gnu_cxx::abs;
using ::__gnu_cxx::llabs;
using ::__gnu_cxx::div;
using ::__gnu_cxx::lldiv;
using ::__gnu_cxx::atoll;
using ::__gnu_cxx::strtof;
using ::__gnu_cxx::strtoll;
using ::__gnu_cxx::strtoull;
using ::__gnu_cxx::strtold;
}
namespace NStl {
using __std_alias::div_t;
using __std_alias::ldiv_t;
using __std_alias::size_t;
using __std_alias::abort;
using __std_alias::getenv;
using __std_alias::mblen;
using __std_alias::mbtowc;
using __std_alias::system;
using __std_alias::bsearch;
using __std_alias::atexit;
using __std_alias::exit;
using __std_alias::calloc;
using __std_alias::free;
using __std_alias::malloc;
using __std_alias::realloc;
using __std_alias::atof;
using __std_alias::atoi;
using __std_alias::atol;
using __std_alias::mbstowcs;
using __std_alias::strtod;
using __std_alias::strtol;
using __std_alias::strtoul;
using __std_alias::wcstombs;
using __std_alias::wctomb;
using __std_alias::qsort;
using __std_alias::labs;
using __std_alias::ldiv;
using __std_alias::llabs;
using __std_alias::lldiv_t;
using __std_alias::lldiv;
using __std_alias::rand;
using __std_alias::srand;
}
inline long abs(long __x) { return __std_alias::labs(__x); }
inline __std_alias::ldiv_t div(long __x, long __y) { return __std_alias::ldiv(__x, __y); }
inline long long abs(long long __x) { return __std_alias::llabs(__x); }
inline lldiv_t div(long long __x, long long __y) { return __std_alias::lldiv(__x, __y); }
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
template<typename _Iterator, typename _Container>
class __normal_iterator;
}
namespace std __attribute__ ((__visibility__ ("default"))) {
struct __true_type { };
struct __false_type { };
template<bool>
struct __truth_type
{ typedef __false_type __type; };
template<>
struct __truth_type<true>
{ typedef __true_type __type; };
template<class _Sp, class _Tp>
struct __traitor
{
enum { __value = bool(_Sp::__value) || bool(_Tp::__value) };
typedef typename __truth_type<__value>::__type __type;
};
template<typename, typename>
struct __are_same
{
enum { __value = 0 };
typedef __false_type __type;
};
template<typename _Tp>
struct __are_same<_Tp, _Tp>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<typename _Tp>
struct __is_void
{
enum { __value = 0 };
typedef __false_type __type;
};
template<>
struct __is_void<void>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<typename _Tp>
struct __is_integer
{
enum { __value = 0 };
typedef __false_type __type;
};
template<>
struct __is_integer<bool>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<char>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<signed char>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<unsigned char>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<wchar_t>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<short>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<unsigned short>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<int>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<unsigned int>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<long>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<unsigned long>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<long long>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_integer<unsigned long long>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<typename _Tp>
struct __is_floating
{
enum { __value = 0 };
typedef __false_type __type;
};
template<>
struct __is_floating<float>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_floating<double>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_floating<long double>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<typename _Tp>
struct __is_pointer
{
enum { __value = 0 };
typedef __false_type __type;
};
template<typename _Tp>
struct __is_pointer<_Tp*>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<typename _Tp>
struct __is_normal_iterator
{
enum { __value = 0 };
typedef __false_type __type;
};
template<typename _Iterator, typename _Container>
struct __is_normal_iterator< __gnu_cxx::__normal_iterator<_Iterator,
_Container> >
{
enum { __value = 1 };
typedef __true_type __type;
};
template<typename _Tp>
struct __is_arithmetic
: public __traitor<__is_integer<_Tp>, __is_floating<_Tp> >
{ };
template<typename _Tp>
struct __is_fundamental
: public __traitor<__is_void<_Tp>, __is_arithmetic<_Tp> >
{ };
template<typename _Tp>
struct __is_scalar
: public __traitor<__is_arithmetic<_Tp>, __is_pointer<_Tp> >
{ };
template<typename _Tp>
struct __is_char
{
enum { __value = 0 };
typedef __false_type __type;
};
template<>
struct __is_char<char>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_char<wchar_t>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<typename _Tp>
struct __is_byte
{
enum { __value = 0 };
typedef __false_type __type;
};
template<>
struct __is_byte<char>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_byte<signed char>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<>
struct __is_byte<unsigned char>
{
enum { __value = 1 };
typedef __true_type __type;
};
template<typename _Tp>
struct __is_move_iterator
{
enum { __value = 0 };
typedef __false_type __type;
};
}
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
template<bool, typename>
struct __enable_if
{ };
template<typename _Tp>
struct __enable_if<true, _Tp>
{ typedef _Tp __type; };
template<bool _Cond, typename _Iftrue, typename _Iffalse>
struct __conditional_type
{ typedef _Iftrue __type; };
template<typename _Iftrue, typename _Iffalse>
struct __conditional_type<false, _Iftrue, _Iffalse>
{ typedef _Iffalse __type; };
template<typename _Tp>
struct __add_unsigned
{
private:
typedef __enable_if<std::__is_integer<_Tp>::__value, _Tp> __if_type;
public:
typedef typename __if_type::__type __type;
};
template<>
struct __add_unsigned<char>
{ typedef unsigned char __type; };
template<>
struct __add_unsigned<signed char>
{ typedef unsigned char __type; };
template<>
struct __add_unsigned<short>
{ typedef unsigned short __type; };
template<>
struct __add_unsigned<int>
{ typedef unsigned int __type; };
template<>
struct __add_unsigned<long>
{ typedef unsigned long __type; };
template<>
struct __add_unsigned<long long>
{ typedef unsigned long long __type; };
template<>
struct __add_unsigned<bool>;
template<>
struct __add_unsigned<wchar_t>;
template<typename _Tp>
struct __remove_unsigned
{
private:
typedef __enable_if<std::__is_integer<_Tp>::__value, _Tp> __if_type;
public:
typedef typename __if_type::__type __type;
};
template<>
struct __remove_unsigned<char>
{ typedef signed char __type; };
template<>
struct __remove_unsigned<unsigned char>
{ typedef signed char __type; };
template<>
struct __remove_unsigned<unsigned short>
{ typedef short __type; };
template<>
struct __remove_unsigned<unsigned int>
{ typedef int __type; };
template<>
struct __remove_unsigned<unsigned long>
{ typedef long __type; };
template<>
struct __remove_unsigned<unsigned long long>
{ typedef long long __type; };
template<>
struct __remove_unsigned<bool>;
template<>
struct __remove_unsigned<wchar_t>;
template<typename _Type>
inline bool
__is_null_pointer(_Type* __ptr)
{ return __ptr == 0; }
template<typename _Type>
inline bool
__is_null_pointer(_Type)
{ return false; }
template<typename _Tp, bool = std::__is_integer<_Tp>::__value>
struct __promote
{ typedef double __type; };
template<typename _Tp>
struct __promote<_Tp, false>
{ typedef _Tp __type; };
template<typename _Tp, typename _Up>
struct __promote_2
{
private:
typedef typename __promote<_Tp>::__type __type1;
typedef typename __promote<_Up>::__type __type2;
public:
typedef __typeof__(__type1() + __type2()) __type;
};
template<typename _Tp, typename _Up, typename _Vp>
struct __promote_3
{
private:
typedef typename __promote<_Tp>::__type __type1;
typedef typename __promote<_Up>::__type __type2;
typedef typename __promote<_Vp>::__type __type3;
public:
typedef __typeof__(__type1() + __type2() + __type3()) __type;
};
template<typename _Tp, typename _Up, typename _Vp, typename _Wp>
struct __promote_4
{
private:
typedef typename __promote<_Tp>::__type __type1;
typedef typename __promote<_Up>::__type __type2;
typedef typename __promote<_Vp>::__type __type3;
typedef typename __promote<_Wp>::__type __type4;
public:
typedef __typeof__(__type1() + __type2() + __type3() + __type4()) __type;
};
}
extern "C" {
typedef float float_t;
typedef double double_t;
extern double acos (double __x) throw (); extern double __acos (double __x) throw ();
extern double asin (double __x) throw (); extern double __asin (double __x) throw ();
extern double atan (double __x) throw (); extern double __atan (double __x) throw ();
extern double atan2 (double __y, double __x) throw (); extern double __atan2 (double __y, double __x) throw ();
extern double cos (double __x) throw (); extern double __cos (double __x) throw ();
extern double sin (double __x) throw (); extern double __sin (double __x) throw ();
extern double tan (double __x) throw (); extern double __tan (double __x) throw ();
extern double cosh (double __x) throw (); extern double __cosh (double __x) throw ();
extern double sinh (double __x) throw (); extern double __sinh (double __x) throw ();
extern double tanh (double __x) throw (); extern double __tanh (double __x) throw ();
extern void sincos (double __x, double *__sinx, double *__cosx) throw (); extern void __sincos (double __x, double *__sinx, double *__cosx) throw ();
extern double acosh (double __x) throw (); extern double __acosh (double __x) throw ();
extern double asinh (double __x) throw (); extern double __asinh (double __x) throw ();
extern double atanh (double __x) throw (); extern double __atanh (double __x) throw ();
extern double exp (double __x) throw (); extern double __exp (double __x) throw ();
extern double frexp (double __x, int *__exponent) throw (); extern double __frexp (double __x, int *__exponent) throw ();
extern double ldexp (double __x, int __exponent) throw (); extern double __ldexp (double __x, int __exponent) throw ();
extern double log (double __x) throw (); extern double __log (double __x) throw ();
extern double log10 (double __x) throw (); extern double __log10 (double __x) throw ();
extern double modf (double __x, double *__iptr) throw (); extern double __modf (double __x, double *__iptr) throw ();
extern double exp10 (double __x) throw (); extern double __exp10 (double __x) throw ();
extern double pow10 (double __x) throw (); extern double __pow10 (double __x) throw ();
extern double expm1 (double __x) throw (); extern double __expm1 (double __x) throw ();
extern double log1p (double __x) throw (); extern double __log1p (double __x) throw ();
extern double logb (double __x) throw (); extern double __logb (double __x) throw ();
extern double exp2 (double __x) throw (); extern double __exp2 (double __x) throw ();
extern double log2 (double __x) throw (); extern double __log2 (double __x) throw ();
extern double pow (double __x, double __y) throw (); extern double __pow (double __x, double __y) throw ();
extern double sqrt (double __x) throw (); extern double __sqrt (double __x) throw ();
extern double hypot (double __x, double __y) throw (); extern double __hypot (double __x, double __y) throw ();
extern double cbrt (double __x) throw (); extern double __cbrt (double __x) throw ();
extern double ceil (double __x) throw () __attribute__ ((__const__)); extern double __ceil (double __x) throw () __attribute__ ((__const__));
extern double fabs (double __x) throw () __attribute__ ((__const__)); extern double __fabs (double __x) throw () __attribute__ ((__const__));
extern double floor (double __x) throw () __attribute__ ((__const__)); extern double __floor (double __x) throw () __attribute__ ((__const__));
extern double fmod (double __x, double __y) throw (); extern double __fmod (double __x, double __y) throw ();
extern int __isinf (double __value) throw () __attribute__ ((__const__));
extern int __finite (double __value) throw () __attribute__ ((__const__));
extern int isinf (double __value) throw () __attribute__ ((__const__));
extern int finite (double __value) throw () __attribute__ ((__const__));
extern double drem (double __x, double __y) throw (); extern double __drem (double __x, double __y) throw ();
extern double significand (double __x) throw (); extern double __significand (double __x) throw ();
extern double copysign (double __x, double __y) throw () __attribute__ ((__const__)); extern double __copysign (double __x, double __y) throw () __attribute__ ((__const__));
extern double nan (__const char *__tagb) throw () __attribute__ ((__const__)); extern double __nan (__const char *__tagb) throw () __attribute__ ((__const__));
extern int __isnan (double __value) throw () __attribute__ ((__const__));
extern int isnan (double __value) throw () __attribute__ ((__const__));
extern double j0 (double) throw (); extern double __j0 (double) throw ();
extern double j1 (double) throw (); extern double __j1 (double) throw ();
extern double jn (int, double) throw (); extern double __jn (int, double) throw ();
extern double y0 (double) throw (); extern double __y0 (double) throw ();
extern double y1 (double) throw (); extern double __y1 (double) throw ();
extern double yn (int, double) throw (); extern double __yn (int, double) throw ();
extern double erf (double) throw (); extern double __erf (double) throw ();
extern double erfc (double) throw (); extern double __erfc (double) throw ();
extern double lgamma (double) throw (); extern double __lgamma (double) throw ();
extern double tgamma (double) throw (); extern double __tgamma (double) throw ();
extern double gamma (double) throw (); extern double __gamma (double) throw ();
extern double lgamma_r (double, int *__signgamp) throw (); extern double __lgamma_r (double, int *__signgamp) throw ();
extern double rint (double __x) throw (); extern double __rint (double __x) throw ();
extern double nextafter (double __x, double __y) throw () __attribute__ ((__const__)); extern double __nextafter (double __x, double __y) throw () __attribute__ ((__const__));
extern double nexttoward (double __x, long double __y) throw () __attribute__ ((__const__)); extern double __nexttoward (double __x, long double __y) throw () __attribute__ ((__const__));
extern double remainder (double __x, double __y) throw (); extern double __remainder (double __x, double __y) throw ();
extern double scalbn (double __x, int __n) throw (); extern double __scalbn (double __x, int __n) throw ();
extern int ilogb (double __x) throw (); extern int __ilogb (double __x) throw ();
extern double scalbln (double __x, long int __n) throw (); extern double __scalbln (double __x, long int __n) throw ();
extern double nearbyint (double __x) throw (); extern double __nearbyint (double __x) throw ();
extern double round (double __x) throw () __attribute__ ((__const__)); extern double __round (double __x) throw () __attribute__ ((__const__));
extern double trunc (double __x) throw () __attribute__ ((__const__)); extern double __trunc (double __x) throw () __attribute__ ((__const__));
extern double remquo (double __x, double __y, int *__quo) throw (); extern double __remquo (double __x, double __y, int *__quo) throw ();
extern long int lrint (double __x) throw (); extern long int __lrint (double __x) throw ();
extern long long int llrint (double __x) throw (); extern long long int __llrint (double __x) throw ();
extern long int lround (double __x) throw (); extern long int __lround (double __x) throw ();
extern long long int llround (double __x) throw (); extern long long int __llround (double __x) throw ();
extern double fdim (double __x, double __y) throw (); extern double __fdim (double __x, double __y) throw ();
extern double fmax (double __x, double __y) throw (); extern double __fmax (double __x, double __y) throw ();
extern double fmin (double __x, double __y) throw (); extern double __fmin (double __x, double __y) throw ();
extern int __fpclassify (double __value) throw ()
__attribute__ ((__const__));
extern int __signbit (double __value) throw ()
__attribute__ ((__const__));
extern double fma (double __x, double __y, double __z) throw (); extern double __fma (double __x, double __y, double __z) throw ();
extern double scalb (double __x, double __n) throw (); extern double __scalb (double __x, double __n) throw ();
extern float acosf (float __x) throw (); extern float __acosf (float __x) throw ();
extern float asinf (float __x) throw (); extern float __asinf (float __x) throw ();
extern float atanf (float __x) throw (); extern float __atanf (float __x) throw ();
extern float atan2f (float __y, float __x) throw (); extern float __atan2f (float __y, float __x) throw ();
extern float cosf (float __x) throw (); extern float __cosf (float __x) throw ();
extern float sinf (float __x) throw (); extern float __sinf (float __x) throw ();
extern float tanf (float __x) throw (); extern float __tanf (float __x) throw ();
extern float coshf (float __x) throw (); extern float __coshf (float __x) throw ();
extern float sinhf (float __x) throw (); extern float __sinhf (float __x) throw ();
extern float tanhf (float __x) throw (); extern float __tanhf (float __x) throw ();
extern void sincosf (float __x, float *__sinx, float *__cosx) throw (); extern void __sincosf (float __x, float *__sinx, float *__cosx) throw ();
extern float acoshf (float __x) throw (); extern float __acoshf (float __x) throw ();
extern float asinhf (float __x) throw (); extern float __asinhf (float __x) throw ();
extern float atanhf (float __x) throw (); extern float __atanhf (float __x) throw ();
extern float expf (float __x) throw (); extern float __expf (float __x) throw ();
extern float frexpf (float __x, int *__exponent) throw (); extern float __frexpf (float __x, int *__exponent) throw ();
extern float ldexpf (float __x, int __exponent) throw (); extern float __ldexpf (float __x, int __exponent) throw ();
extern float logf (float __x) throw (); extern float __logf (float __x) throw ();
extern float log10f (float __x) throw (); extern float __log10f (float __x) throw ();
extern float modff (float __x, float *__iptr) throw (); extern float __modff (float __x, float *__iptr) throw ();
extern float exp10f (float __x) throw (); extern float __exp10f (float __x) throw ();
extern float pow10f (float __x) throw (); extern float __pow10f (float __x) throw ();
extern float expm1f (float __x) throw (); extern float __expm1f (float __x) throw ();
extern float log1pf (float __x) throw (); extern float __log1pf (float __x) throw ();
extern float logbf (float __x) throw (); extern float __logbf (float __x) throw ();
extern float exp2f (float __x) throw (); extern float __exp2f (float __x) throw ();
extern float log2f (float __x) throw (); extern float __log2f (float __x) throw ();
extern float powf (float __x, float __y) throw (); extern float __powf (float __x, float __y) throw ();
extern float sqrtf (float __x) throw (); extern float __sqrtf (float __x) throw ();
extern float hypotf (float __x, float __y) throw (); extern float __hypotf (float __x, float __y) throw ();
extern float cbrtf (float __x) throw (); extern float __cbrtf (float __x) throw ();
extern float ceilf (float __x) throw () __attribute__ ((__const__)); extern float __ceilf (float __x) throw () __attribute__ ((__const__));
extern float fabsf (float __x) throw () __attribute__ ((__const__)); extern float __fabsf (float __x) throw () __attribute__ ((__const__));
extern float floorf (float __x) throw () __attribute__ ((__const__)); extern float __floorf (float __x) throw () __attribute__ ((__const__));
extern float fmodf (float __x, float __y) throw (); extern float __fmodf (float __x, float __y) throw ();
extern int __isinff (float __value) throw () __attribute__ ((__const__));
extern int __finitef (float __value) throw () __attribute__ ((__const__));
extern int isinff (float __value) throw () __attribute__ ((__const__));
extern int finitef (float __value) throw () __attribute__ ((__const__));
extern float dremf (float __x, float __y) throw (); extern float __dremf (float __x, float __y) throw ();
extern float significandf (float __x) throw (); extern float __significandf (float __x) throw ();
extern float copysignf (float __x, float __y) throw () __attribute__ ((__const__)); extern float __copysignf (float __x, float __y) throw () __attribute__ ((__const__));
extern float nanf (__const char *__tagb) throw () __attribute__ ((__const__)); extern float __nanf (__const char *__tagb) throw () __attribute__ ((__const__));
extern int __isnanf (float __value) throw () __attribute__ ((__const__));
extern int isnanf (float __value) throw () __attribute__ ((__const__));
extern float j0f (float) throw (); extern float __j0f (float) throw ();
extern float j1f (float) throw (); extern float __j1f (float) throw ();
extern float jnf (int, float) throw (); extern float __jnf (int, float) throw ();
extern float y0f (float) throw (); extern float __y0f (float) throw ();
extern float y1f (float) throw (); extern float __y1f (float) throw ();
extern float ynf (int, float) throw (); extern float __ynf (int, float) throw ();
extern float erff (float) throw (); extern float __erff (float) throw ();
extern float erfcf (float) throw (); extern float __erfcf (float) throw ();
extern float lgammaf (float) throw (); extern float __lgammaf (float) throw ();
extern float tgammaf (float) throw (); extern float __tgammaf (float) throw ();
extern float gammaf (float) throw (); extern float __gammaf (float) throw ();
extern float lgammaf_r (float, int *__signgamp) throw (); extern float __lgammaf_r (float, int *__signgamp) throw ();
extern float rintf (float __x) throw (); extern float __rintf (float __x) throw ();
extern float nextafterf (float __x, float __y) throw () __attribute__ ((__const__)); extern float __nextafterf (float __x, float __y) throw () __attribute__ ((__const__));
extern float nexttowardf (float __x, long double __y) throw () __attribute__ ((__const__)); extern float __nexttowardf (float __x, long double __y) throw () __attribute__ ((__const__));
extern float remainderf (float __x, float __y) throw (); extern float __remainderf (float __x, float __y) throw ();
extern float scalbnf (float __x, int __n) throw (); extern float __scalbnf (float __x, int __n) throw ();
extern int ilogbf (float __x) throw (); extern int __ilogbf (float __x) throw ();
extern float scalblnf (float __x, long int __n) throw (); extern float __scalblnf (float __x, long int __n) throw ();
extern float nearbyintf (float __x) throw (); extern float __nearbyintf (float __x) throw ();
extern float roundf (float __x) throw () __attribute__ ((__const__)); extern float __roundf (float __x) throw () __attribute__ ((__const__));
extern float truncf (float __x) throw () __attribute__ ((__const__)); extern float __truncf (float __x) throw () __attribute__ ((__const__));
extern float remquof (float __x, float __y, int *__quo) throw (); extern float __remquof (float __x, float __y, int *__quo) throw ();
extern long int lrintf (float __x) throw (); extern long int __lrintf (float __x) throw ();
extern long long int llrintf (float __x) throw (); extern long long int __llrintf (float __x) throw ();
extern long int lroundf (float __x) throw (); extern long int __lroundf (float __x) throw ();
extern long long int llroundf (float __x) throw (); extern long long int __llroundf (float __x) throw ();
extern float fdimf (float __x, float __y) throw (); extern float __fdimf (float __x, float __y) throw ();
extern float fmaxf (float __x, float __y) throw (); extern float __fmaxf (float __x, float __y) throw ();
extern float fminf (float __x, float __y) throw (); extern float __fminf (float __x, float __y) throw ();
extern int __fpclassifyf (float __value) throw ()
__attribute__ ((__const__));
extern int __signbitf (float __value) throw ()
__attribute__ ((__const__));
extern float fmaf (float __x, float __y, float __z) throw (); extern float __fmaf (float __x, float __y, float __z) throw ();
extern float scalbf (float __x, float __n) throw (); extern float __scalbf (float __x, float __n) throw ();
extern long double acosl (long double __x) throw (); extern long double __acosl (long double __x) throw ();
extern long double asinl (long double __x) throw (); extern long double __asinl (long double __x) throw ();
extern long double atanl (long double __x) throw (); extern long double __atanl (long double __x) throw ();
extern long double atan2l (long double __y, long double __x) throw (); extern long double __atan2l (long double __y, long double __x) throw ();
extern long double cosl (long double __x) throw (); extern long double __cosl (long double __x) throw ();
extern long double sinl (long double __x) throw (); extern long double __sinl (long double __x) throw ();
extern long double tanl (long double __x) throw (); extern long double __tanl (long double __x) throw ();
extern long double coshl (long double __x) throw (); extern long double __coshl (long double __x) throw ();
extern long double sinhl (long double __x) throw (); extern long double __sinhl (long double __x) throw ();
extern long double tanhl (long double __x) throw (); extern long double __tanhl (long double __x) throw ();
extern void sincosl (long double __x, long double *__sinx, long double *__cosx) throw (); extern void __sincosl (long double __x, long double *__sinx, long double *__cosx) throw ();
extern long double acoshl (long double __x) throw (); extern long double __acoshl (long double __x) throw ();
extern long double asinhl (long double __x) throw (); extern long double __asinhl (long double __x) throw ();
extern long double atanhl (long double __x) throw (); extern long double __atanhl (long double __x) throw ();
extern long double expl (long double __x) throw (); extern long double __expl (long double __x) throw ();
extern long double frexpl (long double __x, int *__exponent) throw (); extern long double __frexpl (long double __x, int *__exponent) throw ();
extern long double ldexpl (long double __x, int __exponent) throw (); extern long double __ldexpl (long double __x, int __exponent) throw ();
extern long double logl (long double __x) throw (); extern long double __logl (long double __x) throw ();
extern long double log10l (long double __x) throw (); extern long double __log10l (long double __x) throw ();
extern long double modfl (long double __x, long double *__iptr) throw (); extern long double __modfl (long double __x, long double *__iptr) throw ();
extern long double exp10l (long double __x) throw (); extern long double __exp10l (long double __x) throw ();
extern long double pow10l (long double __x) throw (); extern long double __pow10l (long double __x) throw ();
extern long double expm1l (long double __x) throw (); extern long double __expm1l (long double __x) throw ();
extern long double log1pl (long double __x) throw (); extern long double __log1pl (long double __x) throw ();
extern long double logbl (long double __x) throw (); extern long double __logbl (long double __x) throw ();
extern long double exp2l (long double __x) throw (); extern long double __exp2l (long double __x) throw ();
extern long double log2l (long double __x) throw (); extern long double __log2l (long double __x) throw ();
extern long double powl (long double __x, long double __y) throw (); extern long double __powl (long double __x, long double __y) throw ();
extern long double sqrtl (long double __x) throw (); extern long double __sqrtl (long double __x) throw ();
extern long double hypotl (long double __x, long double __y) throw (); extern long double __hypotl (long double __x, long double __y) throw ();
extern long double cbrtl (long double __x) throw (); extern long double __cbrtl (long double __x) throw ();
extern long double ceill (long double __x) throw () __attribute__ ((__const__)); extern long double __ceill (long double __x) throw () __attribute__ ((__const__));
extern long double fabsl (long double __x) throw () __attribute__ ((__const__)); extern long double __fabsl (long double __x) throw () __attribute__ ((__const__));
extern long double floorl (long double __x) throw () __attribute__ ((__const__)); extern long double __floorl (long double __x) throw () __attribute__ ((__const__));
extern long double fmodl (long double __x, long double __y) throw (); extern long double __fmodl (long double __x, long double __y) throw ();
extern int __isinfl (long double __value) throw () __attribute__ ((__const__));
extern int __finitel (long double __value) throw () __attribute__ ((__const__));
extern int isinfl (long double __value) throw () __attribute__ ((__const__));
extern int finitel (long double __value) throw () __attribute__ ((__const__));
extern long double dreml (long double __x, long double __y) throw (); extern long double __dreml (long double __x, long double __y) throw ();
extern long double significandl (long double __x) throw (); extern long double __significandl (long double __x) throw ();
extern long double copysignl (long double __x, long double __y) throw () __attribute__ ((__const__)); extern long double __copysignl (long double __x, long double __y) throw () __attribute__ ((__const__));
extern long double nanl (__const char *__tagb) throw () __attribute__ ((__const__)); extern long double __nanl (__const char *__tagb) throw () __attribute__ ((__const__));
extern int __isnanl (long double __value) throw () __attribute__ ((__const__));
extern int isnanl (long double __value) throw () __attribute__ ((__const__));
extern long double j0l (long double) throw (); extern long double __j0l (long double) throw ();
extern long double j1l (long double) throw (); extern long double __j1l (long double) throw ();
extern long double jnl (int, long double) throw (); extern long double __jnl (int, long double) throw ();
extern long double y0l (long double) throw (); extern long double __y0l (long double) throw ();
extern long double y1l (long double) throw (); extern long double __y1l (long double) throw ();
extern long double ynl (int, long double) throw (); extern long double __ynl (int, long double) throw ();
extern long double erfl (long double) throw (); extern long double __erfl (long double) throw ();
extern long double erfcl (long double) throw (); extern long double __erfcl (long double) throw ();
extern long double lgammal (long double) throw (); extern long double __lgammal (long double) throw ();
extern long double tgammal (long double) throw (); extern long double __tgammal (long double) throw ();
extern long double gammal (long double) throw (); extern long double __gammal (long double) throw ();
extern long double lgammal_r (long double, int *__signgamp) throw (); extern long double __lgammal_r (long double, int *__signgamp) throw ();
extern long double rintl (long double __x) throw (); extern long double __rintl (long double __x) throw ();
extern long double nextafterl (long double __x, long double __y) throw () __attribute__ ((__const__)); extern long double __nextafterl (long double __x, long double __y) throw () __attribute__ ((__const__));
extern long double nexttowardl (long double __x, long double __y) throw () __attribute__ ((__const__)); extern long double __nexttowardl (long double __x, long double __y) throw () __attribute__ ((__const__));
extern long double remainderl (long double __x, long double __y) throw (); extern long double __remainderl (long double __x, long double __y) throw ();
extern long double scalbnl (long double __x, int __n) throw (); extern long double __scalbnl (long double __x, int __n) throw ();
extern int ilogbl (long double __x) throw (); extern int __ilogbl (long double __x) throw ();
extern long double scalblnl (long double __x, long int __n) throw (); extern long double __scalblnl (long double __x, long int __n) throw ();
extern long double nearbyintl (long double __x) throw (); extern long double __nearbyintl (long double __x) throw ();
extern long double roundl (long double __x) throw () __attribute__ ((__const__)); extern long double __roundl (long double __x) throw () __attribute__ ((__const__));
extern long double truncl (long double __x) throw () __attribute__ ((__const__)); extern long double __truncl (long double __x) throw () __attribute__ ((__const__));
extern long double remquol (long double __x, long double __y, int *__quo) throw (); extern long double __remquol (long double __x, long double __y, int *__quo) throw ();
extern long int lrintl (long double __x) throw (); extern long int __lrintl (long double __x) throw ();
extern long long int llrintl (long double __x) throw (); extern long long int __llrintl (long double __x) throw ();
extern long int lroundl (long double __x) throw (); extern long int __lroundl (long double __x) throw ();
extern long long int llroundl (long double __x) throw (); extern long long int __llroundl (long double __x) throw ();
extern long double fdiml (long double __x, long double __y) throw (); extern long double __fdiml (long double __x, long double __y) throw ();
extern long double fmaxl (long double __x, long double __y) throw (); extern long double __fmaxl (long double __x, long double __y) throw ();
extern long double fminl (long double __x, long double __y) throw (); extern long double __fminl (long double __x, long double __y) throw ();
extern int __fpclassifyl (long double __value) throw ()
__attribute__ ((__const__));
extern int __signbitl (long double __value) throw ()
__attribute__ ((__const__));
extern long double fmal (long double __x, long double __y, long double __z) throw (); extern long double __fmal (long double __x, long double __y, long double __z) throw ();
extern long double scalbl (long double __x, long double __n) throw (); extern long double __scalbl (long double __x, long double __n) throw ();
extern int signgam;
enum
{
FP_NAN,
FP_INFINITE,
FP_ZERO,
FP_SUBNORMAL,
FP_NORMAL
};
typedef enum
{
_IEEE_ = -1,
_SVID_,
_XOPEN_,
_POSIX_,
_ISOC_
} _LIB_VERSION_TYPE;
extern _LIB_VERSION_TYPE _LIB_VERSION;
struct __exception
{
int type;
char *name;
double arg1;
double arg2;
double retval;
};
extern int matherr (struct __exception *__exc) throw ();
}
namespace std __attribute__ ((__visibility__ ("default"))) {
template<typename _Tp>
_Tp __cmath_power(_Tp, unsigned int);
template<typename _Tp>
inline _Tp
__pow_helper(_Tp __x, int __n)
{
return __n < 0
? _Tp(1)/__cmath_power(__x, -__n)
: __cmath_power(__x, __n);
}
inline double
abs(double __x)
{ return __builtin_fabs(__x); }
inline float
abs(float __x)
{ return __builtin_fabsf(__x); }
inline long double
abs(long double __x)
{ return __builtin_fabsl(__x); }
using ::acos;
inline float
acos(float __x)
{ return __builtin_acosf(__x); }
inline long double
acos(long double __x)
{ return __builtin_acosl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
acos(_Tp __x)
{ return __builtin_acos(__x); }
using ::asin;
inline float
asin(float __x)
{ return __builtin_asinf(__x); }
inline long double
asin(long double __x)
{ return __builtin_asinl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
asin(_Tp __x)
{ return __builtin_asin(__x); }
using ::atan;
inline float
atan(float __x)
{ return __builtin_atanf(__x); }
inline long double
atan(long double __x)
{ return __builtin_atanl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
atan(_Tp __x)
{ return __builtin_atan(__x); }
using ::atan2;
inline float
atan2(float __y, float __x)
{ return __builtin_atan2f(__y, __x); }
inline long double
atan2(long double __y, long double __x)
{ return __builtin_atan2l(__y, __x); }
template<typename _Tp, typename _Up>
inline
typename __gnu_cxx::__promote_2<
typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value
&& __is_arithmetic<_Up>::__value,
_Tp>::__type, _Up>::__type
atan2(_Tp __y, _Up __x)
{
typedef typename __gnu_cxx::__promote_2<_Tp, _Up>::__type __type;
return atan2(__type(__y), __type(__x));
}
using ::ceil;
inline float
ceil(float __x)
{ return __builtin_ceilf(__x); }
inline long double
ceil(long double __x)
{ return __builtin_ceill(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
ceil(_Tp __x)
{ return __builtin_ceil(__x); }
using ::cos;
inline float
cos(float __x)
{ return __builtin_cosf(__x); }
inline long double
cos(long double __x)
{ return __builtin_cosl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
cos(_Tp __x)
{ return __builtin_cos(__x); }
using ::cosh;
inline float
cosh(float __x)
{ return __builtin_coshf(__x); }
inline long double
cosh(long double __x)
{ return __builtin_coshl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
cosh(_Tp __x)
{ return __builtin_cosh(__x); }
using ::exp;
inline float
exp(float __x)
{ return __builtin_expf(__x); }
inline long double
exp(long double __x)
{ return __builtin_expl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
exp(_Tp __x)
{ return __builtin_exp(__x); }
using ::fabs;
inline float
fabs(float __x)
{ return __builtin_fabsf(__x); }
inline long double
fabs(long double __x)
{ return __builtin_fabsl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
fabs(_Tp __x)
{ return __builtin_fabs(__x); }
using ::floor;
inline float
floor(float __x)
{ return __builtin_floorf(__x); }
inline long double
floor(long double __x)
{ return __builtin_floorl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
floor(_Tp __x)
{ return __builtin_floor(__x); }
using ::fmod;
inline float
fmod(float __x, float __y)
{ return __builtin_fmodf(__x, __y); }
inline long double
fmod(long double __x, long double __y)
{ return __builtin_fmodl(__x, __y); }
using ::frexp;
inline float
frexp(float __x, int* __exp)
{ return __builtin_frexpf(__x, __exp); }
inline long double
frexp(long double __x, int* __exp)
{ return __builtin_frexpl(__x, __exp); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
frexp(_Tp __x, int* __exp)
{ return __builtin_frexp(__x, __exp); }
using ::ldexp;
inline float
ldexp(float __x, int __exp)
{ return __builtin_ldexpf(__x, __exp); }
inline long double
ldexp(long double __x, int __exp)
{ return __builtin_ldexpl(__x, __exp); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
ldexp(_Tp __x, int __exp)
{ return __builtin_ldexp(__x, __exp); }
using ::log;
inline float
log(float __x)
{ return __builtin_logf(__x); }
inline long double
log(long double __x)
{ return __builtin_logl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
log(_Tp __x)
{ return __builtin_log(__x); }
using ::log10;
inline float
log10(float __x)
{ return __builtin_log10f(__x); }
inline long double
log10(long double __x)
{ return __builtin_log10l(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
log10(_Tp __x)
{ return __builtin_log10(__x); }
using ::modf;
inline float
modf(float __x, float* __iptr)
{ return __builtin_modff(__x, __iptr); }
inline long double
modf(long double __x, long double* __iptr)
{ return __builtin_modfl(__x, __iptr); }
using ::pow;
inline float
pow(float __x, float __y)
{ return __builtin_powf(__x, __y); }
inline long double
pow(long double __x, long double __y)
{ return __builtin_powl(__x, __y); }
inline double
pow(double __x, int __i)
{ return __builtin_powi(__x, __i); }
inline float
pow(float __x, int __n)
{ return __builtin_powif(__x, __n); }
inline long double
pow(long double __x, int __n)
{ return __builtin_powil(__x, __n); }
template<typename _Tp, typename _Up>
inline
typename __gnu_cxx::__promote_2<
typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value
&& __is_arithmetic<_Up>::__value,
_Tp>::__type, _Up>::__type
pow(_Tp __x, _Up __y)
{
typedef typename __gnu_cxx::__promote_2<_Tp, _Up>::__type __type;
return pow(__type(__x), __type(__y));
}
using ::sin;
inline float
sin(float __x)
{ return __builtin_sinf(__x); }
inline long double
sin(long double __x)
{ return __builtin_sinl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
sin(_Tp __x)
{ return __builtin_sin(__x); }
using ::sinh;
inline float
sinh(float __x)
{ return __builtin_sinhf(__x); }
inline long double
sinh(long double __x)
{ return __builtin_sinhl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
sinh(_Tp __x)
{ return __builtin_sinh(__x); }
using ::sqrt;
inline float
sqrt(float __x)
{ return __builtin_sqrtf(__x); }
inline long double
sqrt(long double __x)
{ return __builtin_sqrtl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
sqrt(_Tp __x)
{ return __builtin_sqrt(__x); }
using ::tan;
inline float
tan(float __x)
{ return __builtin_tanf(__x); }
inline long double
tan(long double __x)
{ return __builtin_tanl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
tan(_Tp __x)
{ return __builtin_tan(__x); }
using ::tanh;
inline float
tanh(float __x)
{ return __builtin_tanhf(__x); }
inline long double
tanh(long double __x)
{ return __builtin_tanhl(__x); }
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value,
double>::__type
tanh(_Tp __x)
{ return __builtin_tanh(__x); }
}
namespace std __attribute__ ((__visibility__ ("default"))) {
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
fpclassify(_Tp __f)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_fpclassify(FP_NAN, FP_INFINITE, FP_NORMAL,
FP_SUBNORMAL, FP_ZERO, __type(__f));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
isfinite(_Tp __f)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_isfinite(__type(__f));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
isinf(_Tp __f)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_isinf(__type(__f));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
isnan(_Tp __f)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_isnan(__type(__f));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
isnormal(_Tp __f)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_isnormal(__type(__f));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
signbit(_Tp __f)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_signbit(__type(__f));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
isgreater(_Tp __f1, _Tp __f2)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_isgreater(__type(__f1), __type(__f2));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
isgreaterequal(_Tp __f1, _Tp __f2)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_isgreaterequal(__type(__f1), __type(__f2));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
isless(_Tp __f1, _Tp __f2)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_isless(__type(__f1), __type(__f2));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
islessequal(_Tp __f1, _Tp __f2)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_islessequal(__type(__f1), __type(__f2));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
islessgreater(_Tp __f1, _Tp __f2)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_islessgreater(__type(__f1), __type(__f2));
}
template<typename _Tp>
inline typename __gnu_cxx::__enable_if<__is_arithmetic<_Tp>::__value,
int>::__type
isunordered(_Tp __f1, _Tp __f2)
{
typedef typename __gnu_cxx::__promote<_Tp>::__type __type;
return __builtin_isunordered(__type(__f1), __type(__f2));
}
}
namespace std __attribute__ ((__visibility__ ("default"))) {
template<typename _Tp>
inline _Tp
__cmath_power(_Tp __x, unsigned int __n)
{
_Tp __y = __n % 2 ? __x : _Tp(1);
while (__n >>= 1)
{
__x = __x * __x;
if (__n % 2)
__y = __y * __x;
}
return __y;
}
}
inline double abs(double __x)
{ return ::fabs(__x); }
inline float abs (float x) { return ::fabsf(x); } inline long double abs (long double x) { return ::fabsl(x); }
inline float acos (float x) { return ::acosf(x); } inline long double acos (long double x) { return ::acosl(x); }
inline float asin (float x) { return ::asinf(x); } inline long double asin (long double x) { return ::asinl(x); }
inline float atan (float x) { return ::atanf(x); } inline long double atan (long double x) { return ::atanl(x); }
inline float atan2 (float x, float y) { return ::atan2f(x, y); } inline long double atan2 (long double x, long double y) { return ::atan2l(x, y); }
inline float ceil (float x) { return ::ceilf(x); } inline long double ceil (long double x) { return ::ceill(x); }
inline float cos (float x) { return ::cosf(x); } inline long double cos (long double x) { return ::cosl(x); }
inline float cosh (float x) { return ::coshf(x); } inline long double cosh (long double x) { return ::coshl(x); }
inline float exp (float x) { return ::expf(x); } inline long double exp (long double x) { return ::expl(x); }
inline float fabs (float x) { return ::fabsf(x); } inline long double fabs (long double x) { return ::fabsl(x); }
inline float floor (float x) { return ::floorf(x); } inline long double floor (long double x) { return ::floorl(x); }
inline float fmod (float x, float y) { return ::fmodf(x, y); } inline long double fmod (long double x, long double y) { return ::fmodl(x, y); }
inline float frexp (float x, int * y) { return ::frexpf(x, y); } inline long double frexp (long double x, int * y) { return ::frexpl(x, y); }
inline float ldexp (float x, int y) { return ::ldexpf(x, y); } inline long double ldexp (long double x, int y) { return ::ldexpl(x, y); }
inline float log (float x) { return ::logf(x); } inline long double log (long double x) { return ::logl(x); }
inline float log10 (float x) { return ::log10f(x); } inline long double log10 (long double x) { return ::log10l(x); }
inline float modf (float x, float * y) { return ::modff(x, y); } inline long double modf (long double x, long double * y) { return ::modfl(x, y); }
inline float sin (float x) { return ::sinf(x); } inline long double sin (long double x) { return ::sinl(x); }
inline float sinh (float x) { return ::sinhf(x); } inline long double sinh (long double x) { return ::sinhl(x); }
inline float sqrt (float x) { return ::sqrtf(x); } inline long double sqrt (long double x) { return ::sqrtl(x); }
inline float tan (float x) { return ::tanf(x); } inline long double tan (long double x) { return ::tanl(x); }
inline float tanh (float x) { return ::tanhf(x); } inline long double tanh (long double x) { return ::tanhl(x); }
inline float pow (float x, float y) { return ::powf(x, y); } inline long double pow (long double x, long double y) { return ::powl(x, y); }
inline float pow(float __x, int __y) { return ::powf(__x, static_cast<float>(__y)); }
inline double pow(double __x, int __y) { return ::pow(__x, static_cast<double>(__y)); }
inline long double pow(long double __x, int __y) { return ::powl(__x, static_cast<long double>(__y)); }
namespace NStl {
using ::abs;
using ::acos;
using ::asin;
using ::atan;
using ::atan2;
using ::ceil;
using ::cos;
using ::cosh;
using ::exp;
using ::fabs;
using ::floor;
using ::fmod;
using ::frexp;
using ::hypot;
using ::ldexp;
using ::log;
using ::log10;
using ::modf;
using ::pow;
using ::sin;
using ::sinh;
using ::sqrt;
using ::tan;
using ::tanh;
}
namespace NStl {
using ::abs;
using ::div;
}
namespace NStl {
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
template <class _Category, class _Tp, class _Distance = ptrdiff_t,
class _Pointer = _Tp*, class _Reference = _Tp& >
struct iterator {
typedef _Category iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Pointer pointer;
typedef _Reference reference;
};
template<>
struct iterator<output_iterator_tag, void, void, void, void> {
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
};
template <class _Iterator>
struct iterator_traits {
typedef typename _Iterator::iterator_category iterator_category;
typedef typename _Iterator::value_type value_type;
typedef typename _Iterator::difference_type difference_type;
typedef typename _Iterator::pointer pointer;
typedef typename _Iterator::reference reference;
};
template <class _Tp>
struct iterator_traits<const _Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef const _Tp* pointer;
typedef const _Tp& reference;
};
template <class _Tp>
struct iterator_traits<_Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category __iterator_category(const _Iter&) {
typedef typename iterator_traits<_Iter>::iterator_category _Category;
return _Category();
}
template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type* __distance_type(const _Iter&) {
typedef typename iterator_traits<_Iter>::difference_type _diff_type;
return static_cast<_diff_type*>(0);
}
template <class _Iter>
inline typename iterator_traits<_Iter>::value_type* __value_type(const _Iter&) {
typedef typename iterator_traits<_Iter>::value_type _value_type;
return static_cast<_value_type*>(0);
}
template <class _Tp, class _Distance> struct input_iterator :
public iterator <input_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
struct output_iterator : public iterator <output_iterator_tag, void, void, void, void> {};
template <class _Tp, class _Distance> struct forward_iterator :
public iterator<forward_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
template <class _Tp, class _Distance> struct bidirectional_iterator :
public iterator<bidirectional_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
template <class _Tp, class _Distance> struct random_access_iterator :
public iterator<random_access_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
template <class _InputIterator, class _Distance>
inline void __distance(const _InputIterator& __first, const _InputIterator& __last,
_Distance& __n, const input_iterator_tag &) {
_InputIterator __it(__first);
while (__it != __last) { ++__it; ++__n; }
}
template <class _RandomAccessIterator, class _Distance>
inline void __distance(const _RandomAccessIterator& __first,
const _RandomAccessIterator& __last,
_Distance& __n, const random_access_iterator_tag &) {
__n += __last - __first;
}
template <class _InputIterator, class _Distance>
inline void distance(const _InputIterator& __first,
const _InputIterator& __last, _Distance& __n) {
__distance(__first, __last, __n, typename iterator_traits< _InputIterator >::iterator_category());
}
template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(const _InputIterator& __first, const _InputIterator& __last, const input_iterator_tag &) {
typename iterator_traits<_InputIterator>::difference_type __n = 0;
_InputIterator __it(__first);
while (__it != __last) {
++__it; ++__n;
}
return __n;
}
template <class _RandomAccessIterator>
inline typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(const _RandomAccessIterator& __first, const _RandomAccessIterator& __last,
const random_access_iterator_tag &) {
return __last - __first;
}
template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last) {
return __distance(__first, __last, typename iterator_traits< _InputIterator >::iterator_category());
}
template <class _Tp>
struct _Nonconst_traits;
template <class _Tp>
struct _Const_traits {
typedef _Tp value_type;
typedef const _Tp& reference;
typedef const _Tp* pointer;
typedef _Const_traits<_Tp> _ConstTraits;
typedef _Nonconst_traits<_Tp> _NonConstTraits;
};
template <class _Tp>
struct _Nonconst_traits {
typedef _Tp value_type;
typedef _Tp& reference;
typedef _Tp* pointer;
typedef _Const_traits<_Tp> _ConstTraits;
typedef _Nonconst_traits<_Tp> _NonConstTraits;
};
template <class _Tp>
struct _Nonconst_Const_traits;
template <class _Tp>
struct _Const_Const_traits {
typedef _Tp value_type;
typedef const _Tp& reference;
typedef const _Tp* pointer;
typedef _Const_Const_traits<_Tp> _ConstTraits;
typedef _Nonconst_Const_traits<_Tp> _NonConstTraits;
};
template <class _Tp>
struct _Nonconst_Const_traits {
typedef _Tp value_type;
typedef const _Tp& reference;
typedef const _Tp* pointer;
typedef _Const_Const_traits<_Tp> _ConstTraits;
typedef _Nonconst_Const_traits<_Tp> _NonConstTraits;
};
template <class _InputIter, class _Distance>
inline void
__advance(_InputIter& __i, _Distance __n, const input_iterator_tag &) {
while (__n--) ++__i;
}
template <class _InputIter, class _Distance>
inline void
__advance(_InputIter& __i, _Distance __n, const output_iterator_tag &) {
while (__n--) ++__i;
}
template <class _BidirectionalIterator, class _Distance>
inline void
__advance(_BidirectionalIterator& __i, _Distance __n,
const bidirectional_iterator_tag &) {
if (__n > 0)
while (__n--) ++__i;
else
while (__n++) --__i;
}
template <class _RandomAccessIterator, class _Distance>
inline void
__advance(_RandomAccessIterator& __i, _Distance __n,
const random_access_iterator_tag &) {
__i += __n;
}
template <class _InputIterator, class _Distance>
inline void advance(_InputIterator& __i, _Distance __n) {
__advance(__i, __n, typename iterator_traits< _InputIterator >::iterator_category());
}
}
namespace NStl {
template <class _Tp>
inline void swap(_Tp& __a, _Tp& __b) {
_Tp __tmp = __a;
__a = __b;
__b = __tmp;
}
} namespace NStlPriv {
template <class _ForwardIter1, class _ForwardIter2, class _Value>
inline void __iter_swap_aux_aux(_ForwardIter1& __i1, _ForwardIter2& __i2, _Value *) {
_Value tmp = *__i1;
*__i1 = *__i2;
*__i2 = tmp;
}
template <class _ForwardIter1, class _ForwardIter2>
inline void __iter_swap_aux(_ForwardIter1& __i1, _ForwardIter2& __i2, const __true_type& ) {
::NStl::swap(*__i1, *__i2);
}
template <class _ForwardIter1, class _ForwardIter2>
inline void __iter_swap_aux(_ForwardIter1& __i1, _ForwardIter2& __i2, const __false_type& ) {
::NStlPriv:: __iter_swap_aux_aux( __i1, __i2, (typename iterator_traits< _ForwardIter1 >::value_type*)0 );
}
} namespace NStl {
template <class _ForwardIter1, class _ForwardIter2>
inline void iter_swap(_ForwardIter1 __i1, _ForwardIter2 __i2) {
::NStlPriv:: __iter_swap_aux( __i1, __i2, _IsOKToSwap((typename iterator_traits< _ForwardIter1 >::value_type*)0, (typename iterator_traits< _ForwardIter2 >::value_type*)0,
_IsRefType< typename iterator_traits< _ForwardIter1 >::reference >::_Ret(),
_IsRefType< typename iterator_traits< _ForwardIter2 >::reference >::_Ret())._Answer());
}
template <class _Tp>
inline const _Tp& (min)(const _Tp& __a, const _Tp& __b) { return __b < __a ? __b : __a; }
template <class _Tp>
inline const _Tp& (max)(const _Tp& __a, const _Tp& __b) { return __a < __b ? __b : __a; }
template <class _Tp, class _Compare>
inline const _Tp& (min)(const _Tp& __a, const _Tp& __b, _Compare __comp) {
return __comp(__b, __a) ? __b : __a;
}
template <class _Tp, class _Compare>
inline const _Tp& (max)(const _Tp& __a, const _Tp& __b, _Compare __comp) {
return __comp(__a, __b) ? __b : __a;
}
} namespace NStlPriv {
template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __copy(_InputIter __first, _InputIter __last,
_OutputIter __result, const input_iterator_tag &, _Distance*) {
for ( ; __first != __last; ++__result, ++__first)
*__result = *__first;
return __result;
}
template <class _RandomAccessIter, class _OutputIter, class _Distance>
inline _OutputIter
__copy(_RandomAccessIter __first, _RandomAccessIter __last,
_OutputIter __result, const random_access_iterator_tag &, _Distance*) {
for (_Distance __n = __last - __first; __n > 0; --__n) {
*__result = *__first;
++__first;
++__result;
}
return __result;
}
inline void*
__copy_trivial(const void* __first, const void* __last, void* __result) {
size_t __n = (const char*)__last - (const char*)__first;
return __n ? (void *)((char*)memmove(__result, __first, __n) + __n) : __result;
}
template <class _BidirectionalIter1, class _BidirectionalIter2,
class _Distance>
inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,
_BidirectionalIter1 __last,
_BidirectionalIter2 __result,
const bidirectional_iterator_tag &,
_Distance*) {
while (__first != __last)
*--__result = *--__last;
return __result;
}
template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
inline _BidirectionalIter __copy_backward(_RandomAccessIter __first,
_RandomAccessIter __last,
_BidirectionalIter __result,
const random_access_iterator_tag &,
_Distance*) {
for (_Distance __n = __last - __first; __n > 0; --__n)
*--__result = *--__last;
return __result;
}
inline void*
__copy_trivial_backward(const void* __first, const void* __last, void* __result) {
const ptrdiff_t _Num = (const char*)__last - (const char*)__first;
return (_Num > 0) ? memmove((char*)__result - _Num, __first, _Num) : __result ;
}
template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
const __false_type& ) {
return ::NStlPriv:: __copy(__first, __last, __result, random_access_iterator_tag(), (ptrdiff_t*)0);
}
template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
const __true_type& ) {
return (_OutputIter)::NStlPriv:: __copy_trivial(__first, __last, __result);
}
template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
const __true_type& ) {
return ::NStlPriv:: __copy_ptrs(__first, __last, __result,
_UseTrivialCopy((typename iterator_traits< _InputIter >::value_type*)0,
(typename iterator_traits< _OutputIter >::value_type*)0)._Answer());
}
template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
const __false_type& ) {
return ::NStlPriv:: __copy(__first, __last, __result,
typename iterator_traits< _InputIter >::iterator_category(),
(typename iterator_traits< _InputIter >::difference_type*)0);
}
} namespace NStl {
template <class _InputIter, class _OutputIter>
inline _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
return ::NStlPriv:: __copy_aux(__first, __last, __result, _BothPtrType< _InputIter, _OutputIter>::_Answer());
}
} namespace NStlPriv {
template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last,
_OutputIter __result, const __false_type& ) {
return ::NStlPriv:: __copy_backward(__first, __last, __result, typename iterator_traits< _InputIter >::iterator_category(), (typename iterator_traits< _InputIter >::difference_type*)0);
}
template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last,
_OutputIter __result, const __true_type& ) {
return (_OutputIter)::NStlPriv:: __copy_trivial_backward(__first, __last, __result);
}
template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
return ::NStlPriv:: __copy_backward(__first, __last, __result, typename iterator_traits< _InputIter >::iterator_category(), (typename iterator_traits< _InputIter >::difference_type*)0);
}
template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
return ::NStlPriv:: __copy_backward_ptrs(__first, __last, __result,
_UseTrivialCopy((typename iterator_traits< _InputIter >::value_type*)0,
(typename iterator_traits< _OutputIter >::value_type*)0)._Answer());
}
} namespace NStl {
template <class _InputIter, class _OutputIter>
inline _OutputIter copy_backward(_InputIter __first, _InputIter __last, _OutputIter __result) {
return ::NStlPriv:: __copy_backward_aux(__first, __last, __result, _BothPtrType< _InputIter, _OutputIter>::_Answer() );
}
} namespace NStlPriv {
template <class _InputIter, class _Size, class _OutputIter>
inline pair<_InputIter, _OutputIter>
__copy_n(_InputIter __first, _Size __count,
_OutputIter __result,
const input_iterator_tag &) {
for ( ; __count > 0; --__count) {
*__result = *__first;
++__first;
++__result;
}
return pair<_InputIter, _OutputIter>(__first, __result);
}
template <class _RAIter, class _Size, class _OutputIter>
inline pair<_RAIter, _OutputIter>
__copy_n(_RAIter __first, _Size __count,
_OutputIter __result,
const random_access_iterator_tag &) {
_RAIter __last = __first + __count;
return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
}
} namespace NStl {
template <class _InputIter, class _Size, class _OutputIter>
inline pair<_InputIter, _OutputIter>
copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
return ::NStlPriv:: __copy_n(__first, __count, __result, typename iterator_traits< _InputIter >::iterator_category());
}
template <class _ForwardIter, class _Tp>
inline
void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
for ( ; __first != __last; ++__first)
*__first = __val;
}
} namespace NStlPriv {
template <class _OutputIter, class _Size, class _Tp>
inline
_OutputIter __fill_n(_OutputIter __first, _Size __n, const _Tp& __val) {
for ( ; __n > 0; --__n, ++__first)
*__first = __val;
return __first;
}
} namespace NStl {
template <class _OutputIter, class _Size, class _Tp>
inline
void fill_n(_OutputIter __first, _Size __n, const _Tp& __val) {
::NStlPriv:: __fill_n(__first, __n, __val);
}
inline void fill(unsigned char* __first, unsigned char* __last,
const unsigned char& __val) {
unsigned char __tmp = __val;
memset(__first, __tmp, __last - __first);
}
inline void fill(signed char* __first, signed char* __last,
const signed char& __val) {
signed char __tmp = __val;
memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
}
inline void fill(char* __first, char* __last, const char& __val) {
char __tmp = __val;
memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
}
} namespace NStlPriv {
template <class _Size>
inline unsigned char* __fill_n(unsigned char* __first, _Size __n,
const unsigned char& __val) {
fill(__first, __first + __n, __val);
return __first + __n;
}
template <class _Size>
inline signed char* __fill_n(char* __first, _Size __n,
const signed char& __val) {
fill(__first, __first + __n, __val);
return __first + __n;
}
template <class _Size>
inline char* __fill_n(char* __first, _Size __n, const char& __val) {
fill(__first, __first + __n, __val);
return __first + __n;
}
} namespace NStl {
template <class _InputIter1, class _InputIter2>
inline
pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
_InputIter1 __last1,
_InputIter2 __first2) {
while (__first1 != __last1 && *__first1 == *__first2) {
++__first1;
++__first2;
}
return pair<_InputIter1, _InputIter2>(__first1, __first2);
}
template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
inline
pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
_InputIter1 __last1,
_InputIter2 __first2,
_BinaryPredicate __binary_pred) {
while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
++__first1;
++__first2;
}
return pair<_InputIter1, _InputIter2>(__first1, __first2);
}
template <class _InputIter1, class _InputIter2>
inline
bool equal(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2) {
for ( ; __first1 != __last1; ++__first1, ++__first2)
if (!(*__first1 == *__first2))
return false;
return true;
}
template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
inline
bool equal(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _BinaryPredicate __binary_pred) {
for ( ; __first1 != __last1; ++__first1, ++__first2)
if (!__binary_pred(*__first1, *__first2))
return false;
return true;
}
template <class _InputIter1, class _InputIter2>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2);
template <class _InputIter1, class _InputIter2, class _Compare>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_Compare __comp);
inline bool
lexicographical_compare(const unsigned char* __first1,
const unsigned char* __last1,
const unsigned char* __first2,
const unsigned char* __last2) {
const size_t __len1 = __last1 - __first1;
const size_t __len2 = __last2 - __first2;
const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
return __result != 0 ? (__result < 0) : (__len1 < __len2);
}
} namespace NStlPriv {
template <class _InputIter1, class _InputIter2>
int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2);
inline int
__lexicographical_compare_3way(const unsigned char* __first1,
const unsigned char* __last1,
const unsigned char* __first2,
const unsigned char* __last2) {
const ptrdiff_t __len1 = __last1 - __first1;
const ptrdiff_t __len2 = __last2 - __first2;
const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
return __result != 0 ? __result
: (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
}
} namespace NStl {
template <class _InputIter1, class _InputIter2>
int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2);
template <class _InputIter, class _Tp>
inline typename iterator_traits<_InputIter>::difference_type
count(_InputIter __first, _InputIter __last, const _Tp& __val) {
typename iterator_traits<_InputIter>::difference_type __n = 0;
for ( ; __first != __last; ++__first)
if (*__first == __val)
++__n;
return __n;
}
template <class _InputIter, class _Tp>
_InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val);
template <class _InputIter, class _Predicate>
_InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred);
template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPred __predicate);
} namespace NStlPriv {
template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
_InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
_ForwardIter __first2, _ForwardIter __last2,
_BinaryPredicate __comp);
} namespace NStl {
template <class _ForwardIter1, class _ForwardIter2,
class _BinaryPredicate>
_ForwardIter1
find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2,
_BinaryPredicate __comp);
template <class _ForwardIter, class _Tp>
inline void
replace(_ForwardIter __first, _ForwardIter __last,
const _Tp& __old_value, const _Tp& __new_value) {
for ( ; __first != __last; ++__first)
if (*__first == __old_value)
*__first = __new_value;
}
} namespace NStlPriv {
template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val, _Compare1 __comp1, _Compare2 __comp2, _Distance*);
} namespace NStl {
}
namespace NStl {
template <class _InputIter1, class _InputIter2>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2) {
for ( ; __first1 != __last1 && __first2 != __last2
; ++__first1, ++__first2) {
if (*__first1 < *__first2) {
return true;
}
if (*__first2 < *__first1)
return false;
}
return __first1 == __last1 && __first2 != __last2;
}
template <class _InputIter1, class _InputIter2, class _Compare>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_Compare __comp) {
for ( ; __first1 != __last1 && __first2 != __last2
; ++__first1, ++__first2) {
if (__comp(*__first1, *__first2)) {
return true;
}
if (__comp(*__first2, *__first1))
return false;
}
return __first1 == __last1 && __first2 != __last2;
}
} namespace NStlPriv {
template <class _InputIter1, class _InputIter2>
int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2) {
while (__first1 != __last1 && __first2 != __last2) {
if (*__first1 < *__first2) {
return -1;
}
if (*__first2 < *__first1)
return 1;
++__first1;
++__first2;
}
if (__first2 == __last2) {
return !(__first1 == __last1);
}
else {
return -1;
}
}
} namespace NStl {
template <class _InputIter1, class _InputIter2>
int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2) {
return ::NStlPriv:: __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
}
} namespace NStlPriv {
template <class _RandomAccessIter, class _Tp>
inline _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
const _Tp& __val,
const random_access_iterator_tag &) {
typename iterator_traits<_RandomAccessIter>::difference_type __trip_count = (__last - __first) >> 2;
for ( ; __trip_count > 0 ; --__trip_count) {
if (*__first == __val) return __first;
++__first;
if (*__first == __val) return __first;
++__first;
if (*__first == __val) return __first;
++__first;
if (*__first == __val) return __first;
++__first;
}
switch (__last - __first) {
case 3:
if (*__first == __val) return __first;
++__first;
case 2:
if (*__first == __val) return __first;
++__first;
case 1:
if (*__first == __val) return __first;
case 0:
default:
return __last;
}
}
inline char*
__find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {
void *res = memchr(__first, __val, __last - __first);
return res != 0 ? static_cast<char*>(res) : __last;
}
inline const char*
__find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {
const void *res = memchr(__first, __val, __last - __first);
return res != 0 ? static_cast<const char*>(res) : __last;
}
template <class _RandomAccessIter, class _Predicate>
inline _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
_Predicate __pred,
const random_access_iterator_tag &) {
typename iterator_traits<_RandomAccessIter>::difference_type __trip_count = (__last - __first) >> 2;
for ( ; __trip_count > 0 ; --__trip_count) {
if (__pred(*__first)) return __first;
++__first;
if (__pred(*__first)) return __first;
++__first;
if (__pred(*__first)) return __first;
++__first;
if (__pred(*__first)) return __first;
++__first;
}
switch(__last - __first) {
case 3:
if (__pred(*__first)) return __first;
++__first;
case 2:
if (__pred(*__first)) return __first;
++__first;
case 1:
if (__pred(*__first)) return __first;
case 0:
default:
return __last;
}
}
template <class _InputIter, class _Tp>
inline _InputIter __find(_InputIter __first, _InputIter __last,
const _Tp& __val,
const input_iterator_tag &) {
while (__first != __last && !(*__first == __val)) ++__first;
return __first;
}
template <class _InputIter, class _Predicate>
inline _InputIter __find_if(_InputIter __first, _InputIter __last,
_Predicate __pred,
const input_iterator_tag &) {
while (__first != __last && !__pred(*__first))
++__first;
return __first;
}
} namespace NStl {
template <class _InputIter, class _Predicate>
_InputIter find_if(_InputIter __first, _InputIter __last,
_Predicate __pred) {
return ::NStlPriv:: __find_if(__first, __last, __pred, typename iterator_traits< _InputIter >::iterator_category());
}
template <class _InputIter, class _Tp>
_InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {
return ::NStlPriv:: __find(__first, __last, __val, typename iterator_traits< _InputIter >::iterator_category());
}
template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2,
_BinaryPred __pred) {
if (__first1 == __last1 || __first2 == __last2)
return __first1;
_ForwardIter2 __p1(__first2);
if ( ++__p1 == __last2 ) {
while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
++__first1;
}
return __first1;
}
for ( ; ; ) {
while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
++__first1;
}
if (__first1 == __last1) {
return __last1;
}
_ForwardIter2 __p = __p1;
_ForwardIter1 __current = __first1;
if (++__current == __last1) return __last1;
while (__pred(*__current, *__p)) {
if (++__p == __last2)
return __first1;
if (++__current == __last1)
return __last1;
}
++__first1;
}
return __first1;
}
} namespace NStlPriv {
template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
_InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
_ForwardIter __first2, _ForwardIter __last2,
_BinaryPredicate __comp) {
for ( ; __first1 != __last1; ++__first1) {
for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) {
if (__comp(*__first1, *__iter)) {
return __first1;
}
}
}
return __last1;
}
template <class _ForwardIter1, class _ForwardIter2,
class _BinaryPredicate>
_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2,
const forward_iterator_tag &, const forward_iterator_tag &,
_BinaryPredicate __comp) {
if (__first2 == __last2)
return __last1;
else {
_ForwardIter1 __result = __last1;
for (;;) {
_ForwardIter1 __new_result = search(__first1, __last1, __first2, __last2, __comp);
if (__new_result == __last1)
return __result;
else {
__result = __new_result;
__first1 = __new_result;
++__first1;
}
}
}
}
} namespace NStl {
}
namespace NStl {
template <class _Iterator>
class reverse_iterator :
public iterator<typename iterator_traits<_Iterator>::iterator_category,
typename iterator_traits<_Iterator>::value_type,
typename iterator_traits<_Iterator>::difference_type,
typename iterator_traits<_Iterator>::pointer,
typename iterator_traits<_Iterator>::reference> {
protected:
_Iterator current;
typedef reverse_iterator<_Iterator> _Self;
public:
typedef typename iterator_traits<_Iterator>::iterator_category iterator_category;
typedef typename iterator_traits<_Iterator>::value_type value_type;
typedef typename iterator_traits<_Iterator>::difference_type difference_type;
typedef typename iterator_traits<_Iterator>::pointer pointer;
typedef typename iterator_traits<_Iterator>::reference reference;
typedef _Iterator iterator_type;
public:
reverse_iterator() {}
explicit reverse_iterator(iterator_type __x) : current(__x) {}
reverse_iterator(const _Self& __x) : current(__x.current) {}
_Self& operator = (const _Self& __x) { current = __x.base(); return *this; }
template <class _Iter>
reverse_iterator(const reverse_iterator<_Iter>& __x) : current(__x.base()) {}
template <class _Iter>
_Self& operator = (const reverse_iterator<_Iter>& __x) { current = __x.base(); return *this; }
iterator_type base() const { return current; }
reference operator*() const {
_Iterator __tmp = current;
return *--__tmp;
}
pointer operator->() const { return &(operator*()); }
_Self& operator++() {
--current;
return *this;
}
_Self operator++(int) {
_Self __tmp = *this;
--current;
return __tmp;
}
_Self& operator--() {
++current;
return *this;
}
_Self operator--(int) {
_Self __tmp = *this;
++current;
return __tmp;
}
_Self operator+(difference_type __n) const { return _Self(current - __n); }
_Self& operator+=(difference_type __n) {
current -= __n;
return *this;
}
_Self operator-(difference_type __n) const { return _Self(current + __n); }
_Self& operator-=(difference_type __n) {
current += __n;
return *this;
}
reference operator[](difference_type __n) const { return *(*this + __n); }
};
template <class _Iterator>
inline bool operator==(const reverse_iterator<_Iterator>& __x,
const reverse_iterator<_Iterator>& __y)
{ return __x.base() == __y.base(); }
template <class _Iterator>
inline bool operator<(const reverse_iterator<_Iterator>& __x,
const reverse_iterator<_Iterator>& __y)
{ return __y.base() < __x.base(); }
template <class _Iterator>
inline bool operator!=(const reverse_iterator<_Iterator>& __x,
const reverse_iterator<_Iterator>& __y)
{ return !(__x == __y); }
template <class _Iterator>
inline bool operator>(const reverse_iterator<_Iterator>& __x,
const reverse_iterator<_Iterator>& __y)
{ return __y < __x; }
template <class _Iterator>
inline bool operator<=(const reverse_iterator<_Iterator>& __x,
const reverse_iterator<_Iterator>& __y)
{ return !(__y < __x); }
template <class _Iterator>
inline bool operator>=(const reverse_iterator<_Iterator>& __x,
const reverse_iterator<_Iterator>& __y)
{ return !(__x < __y); }
template <class _Iterator>
inline typename reverse_iterator<_Iterator>::difference_type
operator-(const reverse_iterator<_Iterator>& __x,
const reverse_iterator<_Iterator>& __y)
{ return __y.base() - __x.base(); }
template <class _Iterator, class _DifferenceType>
inline reverse_iterator<_Iterator>
operator+(_DifferenceType n,const reverse_iterator<_Iterator>& x)
{ return x.operator+(n); }
template <class _Container>
class back_insert_iterator
: public iterator<output_iterator_tag, void, void, void, void> {
typedef back_insert_iterator<_Container> _Self;
protected:
_Container *container;
public:
typedef _Container container_type;
typedef output_iterator_tag iterator_category;
explicit back_insert_iterator(_Container& __x) : container(&__x) {}
_Self& operator=(const _Self& __other) {
container = __other.container;
return *this;
}
_Self& operator=(const typename _Container::value_type& __val) {
container->push_back(__val);
return *this;
}
_Self& operator*() { return *this; }
_Self& operator++() { return *this; }
_Self operator++(int) { return *this; }
};
template <class _Container>
inline back_insert_iterator<_Container> back_inserter(_Container& __x)
{ return back_insert_iterator<_Container>(__x); }
template <class _Container>
class front_insert_iterator
: public iterator<output_iterator_tag, void, void, void, void> {
typedef front_insert_iterator<_Container> _Self;
protected:
_Container *container;
public:
typedef _Container container_type;
typedef output_iterator_tag iterator_category;
explicit front_insert_iterator(_Container& __x) : container(&__x) {}
_Self& operator=(const _Self& __other) {
container = __other.container;
return *this;
}
_Self& operator=(const typename _Container::value_type& __val) {
container->push_front(__val);
return *this;
}
_Self& operator*() { return *this; }
_Self& operator++() { return *this; }
_Self operator++(int) { return *this; }
};
template <class _Container>
inline front_insert_iterator<_Container> front_inserter(_Container& __x)
{ return front_insert_iterator<_Container>(__x); }
template <class _Container>
class insert_iterator
: public iterator<output_iterator_tag, void, void, void, void> {
typedef insert_iterator<_Container> _Self;
protected:
_Container *container;
typename _Container::iterator _M_iter;
public:
typedef _Container container_type;
typedef output_iterator_tag iterator_category;
insert_iterator(_Container& __x, typename _Container::iterator __i)
: container(&__x), _M_iter(__i) {}
_Self& operator=(_Self const& __other) {
container = __other.container;
_M_iter = __other._M_iter;
return *this;
}
_Self& operator=(const typename _Container::value_type& __val) {
_M_iter = container->insert(_M_iter, __val);
++_M_iter;
return *this;
}
_Self& operator*() { return *this; }
_Self& operator++() { return *this; }
_Self& operator++(int) { return *this; }
};
template <class _Container, class _Iterator>
inline insert_iterator<_Container>
inserter(_Container& __x, _Iterator __i) {
typedef typename _Container::iterator __iter;
return insert_iterator<_Container>(__x, __iter(__i));
}
}
namespace NStl {
} namespace NStlPriv {
template <class _BidirectionalIter1, class _BidirectionalIter2,
class _BinaryPredicate>
_BidirectionalIter1
__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
_BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,
_BinaryPredicate __comp) {
typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
_RevIter1 __rlast1(__first1);
_RevIter2 __rlast2(__first2);
_RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
_RevIter2(__last2), __rlast2,
__comp);
if (__rresult == __rlast1)
return __last1;
else {
_BidirectionalIter1 __result = __rresult.base();
advance(__result, -distance(__first2, __last2));
return __result;
}
}
} namespace NStl {
template <class _ForwardIter1, class _ForwardIter2,
class _BinaryPredicate>
_ForwardIter1
find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2,
_BinaryPredicate __comp) {
return ::NStlPriv:: __find_end(__first1, __last1, __first2, __last2,
typename iterator_traits< _ForwardIter1 >::iterator_category(),
typename iterator_traits< _ForwardIter2 >::iterator_category(),
__comp);
}
} namespace NStlPriv {
template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
_Compare1 __comp1, _Compare2 __comp2, _Distance*) {
(void)__comp2;
_Distance __len = distance(__first, __last);
_Distance __half;
_ForwardIter __middle;
while (__len > 0) {
__half = __len >> 1;
__middle = __first;
advance(__middle, __half);
if (__comp1(*__middle, __val)) {
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}
} namespace NStl {
}
namespace NStl {
template <class _RandomAccessIterator>
void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last);
template <class _RandomAccessIterator, class _Compare>
void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp);
template <class _RandomAccessIterator, class _Distance, class _Tp>
void
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __len, _Tp __val);
template <class _RandomAccessIterator, class _Tp, class _Distance>
inline void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_RandomAccessIterator __result, _Tp __val, _Distance*)
{
*__result = *__first;
__adjust_heap(__first, _Distance(0), _Distance(__last - __first), __val);
}
template <class _RandomAccessIterator>
void pop_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last);
template <class _RandomAccessIterator, class _Distance,
class _Tp, class _Compare>
void
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __len, _Tp __val, _Compare __comp);
template <class _RandomAccessIterator, class _Tp, class _Compare,
class _Distance>
inline void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_RandomAccessIterator __result, _Tp __val, _Compare __comp,
_Distance*)
{
*__result = *__first;
__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
__val, __comp);
}
template <class _RandomAccessIterator, class _Compare>
void
pop_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp);
template <class _RandomAccessIterator>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last);
template <class _RandomAccessIterator, class _Compare>
void
make_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp);
template <class _RandomAccessIterator>
inline
void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
while (__last - __first > 1)
pop_heap(__first, __last--);
}
template <class _RandomAccessIterator, class _Compare>
inline
void
sort_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
while (__last - __first > 1)
pop_heap(__first, __last--, __comp);
}
}
namespace NStl {
template <class _RandomAccessIterator, class _Distance, class _Tp>
inline
void
__push_heap(_RandomAccessIterator __first,
_Distance __holeIndex, _Distance __topIndex, _Tp __val)
{
_Distance __parent = (__holeIndex - 1) / 2;
while (__holeIndex > __topIndex && *(__first + __parent) < __val) {
*(__first + __holeIndex) = *(__first + __parent);
__holeIndex = __parent;
__parent = (__holeIndex - 1) / 2;
}
*(__first + __holeIndex) = __val;
}
template <class _RandomAccessIterator, class _Distance, class _Tp>
inline void
__push_heap_aux(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Distance*, _Tp*)
{
__push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
_Tp(*(__last - 1)));
}
template <class _RandomAccessIterator>
void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
__push_heap_aux(__first, __last,
(typename iterator_traits< _RandomAccessIterator >::difference_type*)0, (typename iterator_traits< _RandomAccessIterator >::value_type*)0);
}
template <class _RandomAccessIterator, class _Distance, class _Tp,
class _Compare>
inline
void
__push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __topIndex, _Tp __val, _Compare __comp)
{
_Distance __parent = (__holeIndex - 1) / 2;
while (__holeIndex > __topIndex && __comp(*(__first + __parent), __val)) {
*(__first + __holeIndex) = *(__first + __parent);
__holeIndex = __parent;
__parent = (__holeIndex - 1) / 2;
}
*(__first + __holeIndex) = __val;
}
template <class _RandomAccessIterator, class _Compare,
class _Distance, class _Tp>
inline void
__push_heap_aux(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp,
_Distance*, _Tp*)
{
__push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
_Tp(*(__last - 1)), __comp);
}
template <class _RandomAccessIterator, class _Compare>
void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
__push_heap_aux(__first, __last, __comp,
(typename iterator_traits< _RandomAccessIterator >::difference_type*)0, (typename iterator_traits< _RandomAccessIterator >::value_type*)0);
}
template <class _RandomAccessIterator, class _Distance, class _Tp>
void
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __len, _Tp __val) {
_Distance __topIndex = __holeIndex;
_Distance __secondChild = 2 * __holeIndex + 2;
while (__secondChild < __len) {
if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
__secondChild--;
*(__first + __holeIndex) = *(__first + __secondChild);
__holeIndex = __secondChild;
__secondChild = 2 * (__secondChild + 1);
}
if (__secondChild == __len) {
*(__first + __holeIndex) = *(__first + (__secondChild - 1));
__holeIndex = __secondChild - 1;
}
__push_heap(__first, __holeIndex, __topIndex, __val);
}
template <class _RandomAccessIterator, class _Tp>
inline void
__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) {
__pop_heap(__first, __last - 1, __last - 1,
_Tp(*(__last - 1)), (typename iterator_traits< _RandomAccessIterator >::difference_type*)0);
}
template <class _RandomAccessIterator>
void pop_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last) {
__pop_heap_aux(__first, __last, (typename iterator_traits< _RandomAccessIterator >::value_type*)0);
}
template <class _RandomAccessIterator, class _Distance,
class _Tp, class _Compare>
void
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __len, _Tp __val, _Compare __comp)
{
_Distance __topIndex = __holeIndex;
_Distance __secondChild = 2 * __holeIndex + 2;
while (__secondChild < __len) {
if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) {
__secondChild--;
}
*(__first + __holeIndex) = *(__first + __secondChild);
__holeIndex = __secondChild;
__secondChild = 2 * (__secondChild + 1);
}
if (__secondChild == __len) {
*(__first + __holeIndex) = *(__first + (__secondChild - 1));
__holeIndex = __secondChild - 1;
}
__push_heap(__first, __holeIndex, __topIndex, __val, __comp);
}
template <class _RandomAccessIterator, class _Tp, class _Compare>
inline void
__pop_heap_aux(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Tp*, _Compare __comp)
{
__pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
(typename iterator_traits< _RandomAccessIterator >::difference_type*)0);
}
template <class _RandomAccessIterator, class _Compare>
void
pop_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
__pop_heap_aux(__first, __last, (typename iterator_traits< _RandomAccessIterator >::value_type*)0, __comp);
}
template <class _RandomAccessIterator, class _Tp, class _Distance>
inline
void
__make_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Tp*, _Distance*)
{
if (__last - __first < 2) return;
_Distance __len = __last - __first;
_Distance __parent = (__len - 2)/2;
for (;;) {
__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
if (__parent == 0) return;
__parent--;
}
}
template <class _RandomAccessIterator>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
__make_heap(__first, __last,
(typename iterator_traits< _RandomAccessIterator >::value_type*)0, (typename iterator_traits< _RandomAccessIterator >::difference_type*)0);
}
template <class _RandomAccessIterator, class _Compare,
class _Tp, class _Distance>
inline
void
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp, _Tp*, _Distance*)
{
if (__last - __first < 2) return;
_Distance __len = __last - __first;
_Distance __parent = (__len - 2)/2;
for (;;) {
__adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
__comp);
if (__parent == 0) return;
__parent--;
}
}
template <class _RandomAccessIterator, class _Compare>
void
make_heap(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
__make_heap(__first, __last, __comp,
(typename iterator_traits< _RandomAccessIterator >::value_type*)0, (typename iterator_traits< _RandomAccessIterator >::difference_type*)0);
}
}
namespace NStl {
template <class _Arg, class _Result>
struct unary_function {
typedef _Arg argument_type;
typedef _Result result_type;
};
template <class _Arg1, class _Arg2, class _Result>
struct binary_function {
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
};
template <class _Tp>
struct equal_to : public binary_function<_Tp, _Tp, bool> {
bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
};
template <class _Tp>
struct less : public binary_function<_Tp,_Tp,bool>
, public __stlport_class<less<_Tp> >
{
bool operator()(const _Tp& __x, const _Tp& __y) const { return __x < __y; }
};
template <class _Tp>
struct __type_traits<less<_Tp> > {
typedef typename _IsSTLportClass<less<_Tp> >::_Ret _STLportLess;
typedef _STLportLess has_trivial_default_constructor;
typedef _STLportLess has_trivial_copy_constructor;
typedef _STLportLess has_trivial_assignment_operator;
typedef _STLportLess has_trivial_destructor;
typedef _STLportLess is_POD_type;
};
} namespace NStlPriv {
template <class _Tp>
less<_Tp> __less(_Tp* ) { return less<_Tp>(); }
template <class _Tp>
equal_to<_Tp> __equal_to(_Tp* ) { return equal_to<_Tp>(); }
} namespace NStl {
template <class _Tp>
struct plus : public binary_function<_Tp, _Tp, _Tp> {
_Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x + __y; }
};
template <class _Tp>
struct minus : public binary_function<_Tp, _Tp, _Tp> {
_Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x - __y; }
};
} namespace NStlPriv {
template <class _Tp>
plus<_Tp> __plus(_Tp* ) { return plus<_Tp>(); }
template <class _Tp>
minus<_Tp> __minus(_Tp* ) { return minus<_Tp>(); }
} namespace NStl {
template <class _Tp>
struct multiplies : public binary_function<_Tp, _Tp, _Tp> {
_Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x * __y; }
};
} namespace NStlPriv {
template <class _Pair>
struct _Select1st : public unary_function<_Pair, typename _Pair::first_type> {
const typename _Pair::first_type& operator()(const _Pair& __x) const {
return __x.first;
}
};
template <class _Pair>
struct _Select2nd : public unary_function<_Pair, typename _Pair::second_type> {
const typename _Pair::second_type& operator()(const _Pair& __x) const {
return __x.second;
}
};
template <class _Arg1, class _Arg2>
struct _Project1st : public binary_function<_Arg1, _Arg2, _Arg1> {
_Arg1 operator()(const _Arg1& __x, const _Arg2&) const { return __x; }
};
template <class _Arg1, class _Arg2>
struct _Project2nd : public binary_function<_Arg1, _Arg2, _Arg2> {
_Arg2 operator()(const _Arg1&, const _Arg2& __y) const { return __y; }
};
template <class _Tp>
struct _Identity : public unary_function<_Tp,_Tp> {
const _Tp& operator()(const _Tp& __x) const { return __x; }
};
template <class _Result, class _Argument>
struct _Constant_unary_fun {
typedef _Argument argument_type;
typedef _Result result_type;
result_type _M_val;
_Constant_unary_fun(const result_type& __v) : _M_val(__v) {}
const result_type& operator()(const _Argument&) const { return _M_val; }
};
template <class _Result, class _Arg1, class _Arg2>
struct _Constant_binary_fun {
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
_Result _M_val;
_Constant_binary_fun(const _Result& __v) : _M_val(__v) {}
const result_type& operator()(const _Arg1&, const _Arg2&) const {
return _M_val;
}
};
template <class _Tp> inline _Tp __identity_element(plus<_Tp>) { return _Tp(0); }
template <class _Tp> inline _Tp __identity_element(multiplies<_Tp>) { return _Tp(1); }
} namespace NStl {
}
namespace NStl {
template <class _InputIter, class _Function>
inline _Function
for_each(_InputIter __first, _InputIter __last, _Function __f) {
for ( ; __first != __last; ++__first)
__f(*__first);
return __f;
}
template <class _InputIter, class _Predicate>
inline typename iterator_traits<_InputIter>::difference_type
count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
typename iterator_traits<_InputIter>::difference_type __n = 0;
for ( ; __first != __last; ++__first) {
if (__pred(*__first))
++__n;
}
return __n;
}
template <class _ForwardIter, class _BinaryPredicate>
inline _ForwardIter
adjacent_find(_ForwardIter __first, _ForwardIter __last,
_BinaryPredicate __binary_pred) {
if (__first == __last)
return __last;
_ForwardIter __next = __first;
while(++__next != __last) {
if (__binary_pred(*__first, *__next))
return __first;
__first = __next;
}
return __last;
}
template <class _ForwardIter>
inline _ForwardIter
adjacent_find(_ForwardIter __first, _ForwardIter __last) {
return adjacent_find(__first, __last,
::NStlPriv:: __equal_to((typename iterator_traits< _ForwardIter >::value_type*)0));
}
template <class _InputIter, class _Tp, class _Size>
inline void
count(_InputIter __first, _InputIter __last, const _Tp& __val, _Size& __n) {
for ( ; __first != __last; ++__first)
if (*__first == __val)
++__n;
}
template <class _InputIter, class _Predicate, class _Size>
inline void
count_if(_InputIter __first, _InputIter __last, _Predicate __pred, _Size& __n) {
for ( ; __first != __last; ++__first)
if (__pred(*__first))
++__n;
}
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2);
template <class _ForwardIter, class _Integer, class _Tp>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val);
template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val, _BinaryPred __binary_pred);
template <class _InputIter, class _ForwardIter>
inline _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
_ForwardIter __first2, _ForwardIter __last2) {
return ::NStlPriv:: __find_first_of(__first1, __last1, __first2, __last2,
::NStlPriv:: __equal_to((typename iterator_traits< _InputIter >::value_type*)0));
}
template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
inline _InputIter
find_first_of(_InputIter __first1, _InputIter __last1,
_ForwardIter __first2, _ForwardIter __last2, _BinaryPredicate __comp) {
return ::NStlPriv:: __find_first_of(__first1, __last1, __first2, __last2, __comp);
}
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1
find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2);
template <class _ForwardIter1, class _ForwardIter2>
inline _ForwardIter2
swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2) {
for ( ; __first1 != __last1; ++__first1, ++__first2)
iter_swap(__first1, __first2);
return __first2;
}
template <class _InputIter, class _OutputIter, class _UnaryOperation>
inline _OutputIter
transform(_InputIter __first, _InputIter __last, _OutputIter __result, _UnaryOperation __opr) {
for ( ; __first != __last; ++__first, ++__result)
*__result = __opr(*__first);
return __result;
}
template <class _InputIter1, class _InputIter2, class _OutputIter, class _BinaryOperation>
inline _OutputIter
transform(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _OutputIter __result,_BinaryOperation __binary_op) {
for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
*__result = __binary_op(*__first1, *__first2);
return __result;
}
template <class _ForwardIter, class _Predicate, class _Tp>
inline void
replace_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, const _Tp& __new_value) {
for ( ; __first != __last; ++__first)
if (__pred(*__first))
*__first = __new_value;
}
template <class _InputIter, class _OutputIter, class _Tp>
inline _OutputIter
replace_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
const _Tp& __old_value, const _Tp& __new_value) {
for ( ; __first != __last; ++__first, ++__result)
*__result = *__first == __old_value ? __new_value : *__first;
return __result;
}
template <class _Iterator, class _OutputIter, class _Predicate, class _Tp>
inline _OutputIter
replace_copy_if(_Iterator __first, _Iterator __last,
_OutputIter __result,
_Predicate __pred, const _Tp& __new_value) {
for ( ; __first != __last; ++__first, ++__result)
*__result = __pred(*__first) ? __new_value : *__first;
return __result;
}
template <class _ForwardIter, class _Generator>
inline void
generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
for ( ; __first != __last; ++__first)
*__first = __gen();
}
template <class _OutputIter, class _Size, class _Generator>
inline void
generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
for ( ; __n > 0; --__n, ++__first)
*__first = __gen();
}
template <class _InputIter, class _OutputIter, class _Tp>
inline _OutputIter
remove_copy(_InputIter __first, _InputIter __last,_OutputIter __result, const _Tp& __val) {
for ( ; __first != __last; ++__first) {
if (!(*__first == __val)) {
*__result = *__first;
++__result;
}
}
return __result;
}
template <class _InputIter, class _OutputIter, class _Predicate>
inline _OutputIter
remove_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, _Predicate __pred) {
for ( ; __first != __last; ++__first) {
if (!__pred(*__first)) {
*__result = *__first;
++__result;
}
}
return __result;
}
template <class _ForwardIter, class _Tp>
inline _ForwardIter
remove(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
__first = find(__first, __last, __val);
if (__first == __last)
return __first;
else {
_ForwardIter __next = __first;
return remove_copy(++__next, __last, __first, __val);
}
}
template <class _ForwardIter, class _Predicate>
inline _ForwardIter
remove_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
__first = find_if(__first, __last, __pred);
if ( __first == __last )
return __first;
else {
_ForwardIter __next = __first;
return remove_copy_if(++__next, __last, __first, __pred);
}
}
template <class _InputIter, class _OutputIter>
_OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result);
template <class _InputIter, class _OutputIter, class _BinaryPredicate>
_OutputIter unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
_BinaryPredicate __binary_pred);
template <class _ForwardIter>
inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
__first = adjacent_find(__first, __last);
return unique_copy(__first, __last, __first);
}
template <class _ForwardIter, class _BinaryPredicate>
inline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
_BinaryPredicate __binary_pred) {
__first = adjacent_find(__first, __last, __binary_pred);
return unique_copy(__first, __last, __first, __binary_pred);
}
template <class _BidirectionalIter>
inline void
__reverse(_BidirectionalIter __first, _BidirectionalIter __last, const bidirectional_iterator_tag &) {
for (; __first != __last && __first != --__last; ++__first)
iter_swap(__first,__last);
}
template <class _RandomAccessIter>
inline void
__reverse(_RandomAccessIter __first, _RandomAccessIter __last, const random_access_iterator_tag &) {
for (; __first < __last; ++__first)
iter_swap(__first, --__last);
}
template <class _BidirectionalIter>
inline void
reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
__reverse(__first, __last, typename iterator_traits< _BidirectionalIter >::iterator_category());
}
template <class _BidirectionalIter, class _OutputIter>
inline
_OutputIter reverse_copy(_BidirectionalIter __first,
_BidirectionalIter __last,
_OutputIter __result) {
while (__first != __last) {
--__last;
*__result = *__last;
++__result;
}
return __result;
}
} namespace NStlPriv {
template <class _EuclideanRingElement>
inline
_EuclideanRingElement __gcd(_EuclideanRingElement __m,
_EuclideanRingElement __n) {
while (__n != 0) {
_EuclideanRingElement __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
} namespace NStl {
template <class _ForwardIter>
void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last);
template <class _ForwardIter, class _OutputIter>
inline _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
_ForwardIter __last, _OutputIter __result) {
return copy(__first, __middle, copy(__middle, __last, __result));
}
template <class _RandomAccessIter>
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last);
template <class _RandomAccessIter, class _RandomNumberGenerator>
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
_RandomNumberGenerator& __rand);
template <class _ForwardIter, class _OutputIter, class _Distance>
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
_OutputIter __out_ite, const _Distance __n);
template <class _ForwardIter, class _OutputIter, class _Distance,
class _RandomNumberGenerator>
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
_OutputIter __out_ite, const _Distance __n,
_RandomNumberGenerator& __rand);
template <class _InputIter, class _RandomAccessIter>
_RandomAccessIter
random_sample(_InputIter __first, _InputIter __last,
_RandomAccessIter __out_first, _RandomAccessIter __out_last);
template <class _InputIter, class _RandomAccessIter,
class _RandomNumberGenerator>
_RandomAccessIter
random_sample(_InputIter __first, _InputIter __last,
_RandomAccessIter __out_first, _RandomAccessIter __out_last,
_RandomNumberGenerator& __rand);
template <class _ForwardIter, class _Predicate>
_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred);
template <class _ForwardIter, class _Predicate>
_ForwardIter
stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred);
} namespace NStlPriv {
template <class _Size>
inline _Size __lg(_Size __n) {
_Size __k;
for (__k = 0; __n != 1; __n >>= 1) ++__k;
return __k;
}
} namespace NStl {
template <class _RandomAccessIter>
void sort(_RandomAccessIter __first, _RandomAccessIter __last);
template <class _RandomAccessIter, class _Compare>
void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp);
template <class _RandomAccessIter>
void stable_sort(_RandomAccessIter __first,
_RandomAccessIter __last);
template <class _RandomAccessIter, class _Compare>
void stable_sort(_RandomAccessIter __first,
_RandomAccessIter __last, _Compare __comp);
template <class _RandomAccessIter>
void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
_RandomAccessIter __last);
template <class _RandomAccessIter, class _Compare>
void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
_RandomAccessIter __last, _Compare __comp);
template <class _InputIter, class _RandomAccessIter>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
_RandomAccessIter __result_first, _RandomAccessIter __result_last);
template <class _InputIter, class _RandomAccessIter, class _Compare>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
_RandomAccessIter __result_first,
_RandomAccessIter __result_last, _Compare __comp);
template <class _RandomAccessIter>
void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
_RandomAccessIter __last);
template <class _RandomAccessIter, class _Compare>
void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
_RandomAccessIter __last, _Compare __comp);
} namespace NStlPriv {
template <class _T1, class _T2>
struct __less_2 {
bool operator() (const _T1& __x, const _T2& __y) const { return __x < __y ; }
};
template <class _T1, class _T2>
__less_2<_T1,_T2> __less2(_T1*, _T2* ) { return __less_2<_T1, _T2>(); }
} namespace NStl {
template <class _ForwardIter, class _Tp>
inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val) {
return ::NStlPriv:: __lower_bound(__first, __last, __val,
::NStlPriv:: __less2((typename iterator_traits< _ForwardIter >::value_type*)0, (_Tp*)0),
::NStlPriv:: __less2((_Tp*)0, (typename iterator_traits< _ForwardIter >::value_type*)0),
(typename iterator_traits< _ForwardIter >::difference_type*)0);
}
template <class _ForwardIter, class _Tp, class _Compare>
inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val, _Compare __comp) {
return ::NStlPriv:: __lower_bound(__first, __last, __val, __comp, __comp,
(typename iterator_traits< _ForwardIter >::difference_type*)0);
}
} namespace NStlPriv {
template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
_Compare1 __comp1, _Compare2 __comp2, _Distance*);
} namespace NStl {
template <class _ForwardIter, class _Tp>
inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val) {
return ::NStlPriv:: __upper_bound(__first, __last, __val,
::NStlPriv:: __less2((typename iterator_traits< _ForwardIter >::value_type*)0, (_Tp*)0),
::NStlPriv:: __less2((_Tp*)0, (typename iterator_traits< _ForwardIter >::value_type*)0),
(typename iterator_traits< _ForwardIter >::difference_type*)0);
}
template <class _ForwardIter, class _Tp, class _Compare>
inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val, _Compare __comp) {
return ::NStlPriv:: __upper_bound(__first, __last, __val, __comp, __comp,
(typename iterator_traits< _ForwardIter >::difference_type*)0);
}
} namespace NStlPriv {
template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
pair<_ForwardIter, _ForwardIter>
__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
_Compare1 __comp1, _Compare2 __comp2, _Distance*);
} namespace NStl {
template <class _ForwardIter, class _Tp>
inline pair<_ForwardIter, _ForwardIter>
equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
return ::NStlPriv:: __equal_range(__first, __last, __val,
::NStlPriv:: __less2((typename iterator_traits< _ForwardIter >::value_type*)0, (_Tp*)0),
::NStlPriv:: __less2((_Tp*)0, (typename iterator_traits< _ForwardIter >::value_type*)0),
(typename iterator_traits< _ForwardIter >::difference_type*)0);
}
template <class _ForwardIter, class _Tp, class _Compare>
inline pair<_ForwardIter, _ForwardIter>
equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
_Compare __comp) {
return ::NStlPriv:: __equal_range(__first, __last, __val, __comp, __comp,
(typename iterator_traits< _ForwardIter >::difference_type*)0);
}
template <class _ForwardIter, class _Tp>
inline bool binary_search(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val) {
_ForwardIter __i = ::NStlPriv:: __lower_bound(__first, __last, __val,
::NStlPriv:: __less2((typename iterator_traits< _ForwardIter >::value_type*)0, (_Tp*)0),
::NStlPriv:: __less2((_Tp*)0, (typename iterator_traits< _ForwardIter >::value_type*)0),
(typename iterator_traits< _ForwardIter >::difference_type*)0);
return __i != __last && !(__val < *__i);
}
template <class _ForwardIter, class _Tp, class _Compare>
inline bool binary_search(_ForwardIter __first, _ForwardIter __last,
const _Tp& __val,
_Compare __comp) {
_ForwardIter __i = ::NStlPriv:: __lower_bound(__first, __last, __val, __comp, __comp,
(typename iterator_traits< _ForwardIter >::difference_type*)0);
return __i != __last && !__comp(__val, *__i);
}
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result);
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp);
template <class _BidirectionalIter>
void inplace_merge(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last) ;
template <class _BidirectionalIter, class _Compare>
void inplace_merge(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last, _Compare __comp);
template <class _InputIter1, class _InputIter2>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2);
template <class _InputIter1, class _InputIter2, class _Compare>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2, _Compare __comp);
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result);
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp);
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result);
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp);
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result);
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp);
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result);
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result,
_Compare __comp);
template <class _ForwardIter>
_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last);
template <class _ForwardIter, class _Compare>
_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
_Compare __comp);
template <class _ForwardIter>
_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last);
template <class _ForwardIter, class _Compare>
_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
_Compare __comp);
template <class _BidirectionalIter>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last);
template <class _BidirectionalIter, class _Compare>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
_Compare __comp);
template <class _BidirectionalIter>
bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last);
template <class _BidirectionalIter, class _Compare>
bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
_Compare __comp);
template <class _RandomAccessIter>
bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last);
template <class _RandomAccessIter, class _StrictWeakOrdering>
bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
_StrictWeakOrdering __comp);
} namespace NStlPriv {
template <class _ForwardIter, class _StrictWeakOrdering>
bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
_StrictWeakOrdering __comp);
} namespace NStl {
template <class _ForwardIter>
inline bool is_sorted(_ForwardIter __first, _ForwardIter __last) {
return ::NStlPriv:: __is_sorted(__first, __last,
::NStlPriv:: __less((typename iterator_traits< _ForwardIter >::value_type*)0));
}
template <class _ForwardIter, class _StrictWeakOrdering>
inline bool is_sorted(_ForwardIter __first, _ForwardIter __last,
_StrictWeakOrdering __comp) {
return ::NStlPriv:: __is_sorted(__first, __last, __comp);
}
}
extern "C++" {
namespace std
{
class exception
{
public:
exception() throw() { }
virtual ~exception() throw();
virtual const char* what() const throw();
};
class bad_exception : public exception
{
public:
bad_exception() throw() { }
virtual ~bad_exception() throw();
virtual const char* what() const throw();
};
typedef void (*terminate_handler) ();
typedef void (*unexpected_handler) ();
terminate_handler set_terminate(terminate_handler) throw();
void terminate() __attribute__ ((__noreturn__));
unexpected_handler set_unexpected(unexpected_handler) throw();
void unexpected() __attribute__ ((__noreturn__));
bool uncaught_exception() throw();
}
namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
void __verbose_terminate_handler();
}
}
extern "C++" {
namespace std
{
class bad_alloc : public exception
{
public:
bad_alloc() throw() { }
virtual ~bad_alloc() throw();
virtual const char* what() const throw();
};
struct nothrow_t { };
extern const nothrow_t nothrow;
typedef void (*new_handler)();
new_handler set_new_handler(new_handler) throw();
}
void* operator new(std::size_t) throw (std::bad_alloc);
void* operator new[](std::size_t) throw (std::bad_alloc);
void operator delete(void*) throw();
void operator delete[](void*) throw();
void* operator new(std::size_t, const std::nothrow_t&) throw();
void* operator new[](std::size_t, const std::nothrow_t&) throw();
void operator delete(void*, const std::nothrow_t&) throw();
void operator delete[](void*, const std::nothrow_t&) throw();
inline void* operator new(std::size_t, void* __p) throw() { return __p; }
inline void* operator new[](std::size_t, void* __p) throw() { return __p; }
inline void operator delete (void*, void*) throw() { }
inline void operator delete[](void*, void*) throw() { }
}
namespace NStl {
using __std_alias::bad_alloc;
using __std_alias::nothrow_t;
using __std_alias::nothrow;
using __std_alias::new_handler;
using __std_alias::set_new_handler;
}
namespace NStl {
inline void* __stl_new(size_t __n) { return ::operator new(__n); }
inline void __stl_delete(void* __p) { ::operator delete(__p); }
}
namespace NStl {
template <class _Tp>
inline void __destroy_aux(_Tp* __pointer, const __false_type& )
{ __pointer->~_Tp(); }
template <class _Tp>
inline void __destroy_aux(_Tp*, const __true_type& ) {}
template <class _Tp>
inline void _Destroy(_Tp* __pointer) {
typedef typename __type_traits<_Tp>::has_trivial_destructor _Trivial_destructor;
__destroy_aux(__pointer, _Trivial_destructor());
}
template <class _Tp>
inline void _Destroy_Moved(_Tp* __pointer) {
typedef typename __move_traits<_Tp>::complete _Trivial_destructor;
__destroy_aux(__pointer, _Trivial_destructor());
}
template <class _T1>
inline void _Construct(_T1* __p) {
new (__p) _T1();
}
template <class _T1>
inline void _ConstructNoFill(_T1* __p) {
new (__p) _T1;
}
template <class _Tp, class _Targ>
inline void _Copy_Construct(_Tp* __p, const _Targ& __val) {
new (__p) _Tp(__val);
}
template <class _T1, class _T2>
inline void _Param_Construct(_T1* __p, const _T2& __val) {
new (__p) _T1(__val);
}
template <class _T1, class _T2>
inline void _Move_Construct_Aux(_T1* __p, _T2& __val, const __false_type& ) {
new (__p) _T1(::NStlPriv:: _AsMoveSource(__val));
}
template <class _T1, class _T2>
inline void _Move_Construct_Aux(_T1* __p, _T2& __val, const __true_type& ) {
new (__p) _T1(__val);
}
template <class _T1, class _T2>
inline void _Move_Construct(_T1* __p, _T2& __val) {
_Move_Construct_Aux(__p, __val, _Is_POD(__p)._Answer());
}
template <class _ForwardIterator, class _Tp>
inline void
__destroy_range_aux(_ForwardIterator __first, _ForwardIterator __last, _Tp*, const __false_type& ) {
for ( ; __first != __last; ++__first) {
__destroy_aux(&(*__first), __false_type());
}
}
template <class _ForwardIterator, class _Tp>
inline void
__destroy_range_aux(_ForwardIterator, _ForwardIterator, _Tp*, const __true_type& ) {}
template <class _ForwardIterator, class _Tp>
inline void
__destroy_range(_ForwardIterator __first, _ForwardIterator __last, _Tp *__ptr) {
typedef typename __type_traits<_Tp>::has_trivial_destructor _Trivial_destructor;
__destroy_range_aux(__first, __last, __ptr, _Trivial_destructor());
}
template <class _ForwardIterator>
inline void _Destroy_Range(_ForwardIterator __first, _ForwardIterator __last) {
__destroy_range(__first, __last, (typename iterator_traits< _ForwardIterator >::value_type*)0);
}
inline void _Destroy_Range(char*, char*) {}
inline void _Destroy_Range(wchar_t*, wchar_t*) {}
inline void _Destroy_Range(const wchar_t*, const wchar_t*) {}
template <class _ForwardIterator, class _Tp>
inline void
__destroy_mv_srcs(_ForwardIterator __first, _ForwardIterator __last, _Tp *__ptr) {
typedef typename __move_traits<_Tp>::complete _CompleteMove;
__destroy_range_aux(__first, __last, __ptr, _CompleteMove());
}
template <class _ForwardIterator>
inline void _Destroy_Moved_Range(_ForwardIterator __first, _ForwardIterator __last) {
__destroy_mv_srcs(__first, __last, (typename iterator_traits< _ForwardIterator >::value_type*)0);
}
template <class _T1, class _T2>
inline void construct(_T1* __p, const _T2& __val) {_Param_Construct(__p, __val); }
template <class _T1>
inline void construct(_T1* __p) { ::NStl::_Construct(__p); }
template <class _Tp>
inline void destroy(_Tp* __pointer) { ::NStl::_Destroy(__pointer); }
template <class _ForwardIterator>
inline void destroy(_ForwardIterator __first, _ForwardIterator __last) { ::NStl::_Destroy_Range(__first, __last); }
}
namespace NStl {
} namespace NStlPriv {
template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __ucopy(_InputIter __first, _InputIter __last,
_OutputIter __result, _Distance*) {
_OutputIter __cur = __result;
try {
for ( ; __first != __last; ++__first, ++__cur)
_Param_Construct(&*__cur, *__first);
return __cur;
}
catch(...) { ::NStl::_Destroy_Range(__result, __cur); throw; }
}
template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __ucopy(_InputIter __first, _InputIter __last,
_OutputIter __result, const input_iterator_tag &, _Distance* __d)
{ return __ucopy(__first, __last, __result, __d); }
template <class _RandomAccessIter, class _OutputIter, class _Distance>
inline _OutputIter __ucopy(_RandomAccessIter __first, _RandomAccessIter __last,
_OutputIter __result, const random_access_iterator_tag &, _Distance*) {
_OutputIter __cur = __result;
try {
for (_Distance __n = __last - __first; __n > 0; --__n) {
_Param_Construct(&*__cur, *__first);
++__first;
++__cur;
}
return __cur;
}
catch(...) { ::NStl::_Destroy_Range(__result, __cur); throw; }
}
template <class _RandomAccessIter, class _OutputIter>
inline _OutputIter __ucopy(_RandomAccessIter __first, _RandomAccessIter __last, _OutputIter __result)
{ return __ucopy(__first, __last, __result, random_access_iterator_tag(), (ptrdiff_t*)0); }
inline void*
__ucopy_trivial(const void* __first, const void* __last, void* __result) {
return (__last == __first) ? __result :
((char*)memcpy(__result, __first, ((const char*)__last - (const char*)__first))) +
((const char*)__last - (const char*)__first);
}
template <class _InputIter, class _OutputIter>
inline _OutputIter __ucopy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
const __false_type& )
{ return __ucopy(__first, __last, __result, random_access_iterator_tag(), (ptrdiff_t*)0); }
template <class _InputIter, class _OutputIter>
inline _OutputIter __ucopy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result,
const __true_type& ) {
return (_OutputIter)__ucopy_trivial(__first, __last, __result);
}
template <class _InputIter, class _OutputIter>
inline _OutputIter __ucopy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
const __true_type& ) {
return __ucopy_ptrs(__first, __last, __result,
_UseTrivialUCopy((typename iterator_traits< _InputIter >::value_type*)0,
(typename iterator_traits< _OutputIter >::value_type*)0)._Answer());
}
template <class _InputIter, class _OutputIter>
inline _OutputIter __ucopy_aux(_InputIter __first, _InputIter __last, _OutputIter __result,
const __false_type& ) {
return __ucopy(__first, __last, __result,
typename iterator_traits< _InputIter >::iterator_category(),
(typename iterator_traits< _InputIter >::difference_type*)0);
}
} namespace NStl {
template <class _InputIter, class _ForwardIter>
inline _ForwardIter
uninitialized_copy(_InputIter __first, _InputIter __last, _ForwardIter __result)
{ return ::NStlPriv:: __ucopy_aux(__first, __last, __result, _BothPtrType< _InputIter, _ForwardIter>::_Answer()); }
inline char*
uninitialized_copy(const char* __first, const char* __last, char* __result)
{ return (char*)::NStlPriv:: __ucopy_trivial(__first, __last, __result); }
inline wchar_t*
uninitialized_copy(const wchar_t* __first, const wchar_t* __last, wchar_t* __result)
{ return (wchar_t*)::NStlPriv:: __ucopy_trivial (__first, __last, __result); }
} namespace NStlPriv {
template <class _InputIter, class _Size, class _ForwardIter>
inline
pair<_InputIter, _ForwardIter>
__ucopy_n(_InputIter __first, _Size __count, _ForwardIter __result,
const input_iterator_tag &) {
_ForwardIter __cur = __result;
try {
for ( ; __count > 0 ; --__count, ++__first, ++__cur)
_Param_Construct(&*__cur, *__first);
return pair<_InputIter, _ForwardIter>(__first, __cur);
}
catch(...) { ::NStl::_Destroy_Range(__result, __cur); throw; }
}
template <class _RandomAccessIter, class _Size, class _ForwardIter>
inline pair<_RandomAccessIter, _ForwardIter>
__ucopy_n(_RandomAccessIter __first, _Size __count, _ForwardIter __result,
const random_access_iterator_tag &) {
_RandomAccessIter __last = __first + __count;
return pair<_RandomAccessIter, _ForwardIter>(__last, uninitialized_copy(__first, __last, __result));
}
template <class _InputIter, class _Size, class _ForwardIter>
inline pair<_InputIter, _ForwardIter>
__ucopy_n(_InputIter __first, _Size __count, _ForwardIter __result)
{ return ::NStlPriv:: __ucopy_n(__first, __count, __result, typename iterator_traits< _InputIter >::iterator_category()); }
} namespace NStl {
template <class _InputIter, class _Size, class _ForwardIter>
inline pair<_InputIter, _ForwardIter>
uninitialized_copy_n(_InputIter __first, _Size __count, _ForwardIter __result)
{ return ::NStlPriv:: __ucopy_n(__first, __count, __result); }
} namespace NStlPriv {
template <class _ForwardIter, class _Tp, class _Distance>
inline void __ufill(_ForwardIter __first, _ForwardIter __last, const _Tp& __x, _Distance*) {
_ForwardIter __cur = __first;
try {
for ( ; __cur != __last; ++__cur)
_Param_Construct(&*__cur, __x);
}
catch(...) { ::NStl::_Destroy_Range(__first, __cur); throw; }
}
template <class _ForwardIter, class _Tp, class _Distance>
inline void __ufill(_ForwardIter __first, _ForwardIter __last,
const _Tp& __x, const input_iterator_tag &, _Distance* __d)
{ __ufill(__first, __last, __x, __d); }
template <class _ForwardIter, class _Tp, class _Distance>
inline void __ufill(_ForwardIter __first, _ForwardIter __last,
const _Tp& __x, const random_access_iterator_tag &, _Distance*) {
_ForwardIter __cur = __first;
try {
for (_Distance __n = __last - __first; __n > 0; --__n, ++__cur)
_Param_Construct(&*__cur, __x);
}
catch(...) { ::NStl::_Destroy_Range(__first, __cur); throw; }
}
} namespace NStl {
template <class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __x) {
::NStlPriv:: __ufill(__first, __last, __x,
typename iterator_traits< _ForwardIter >::iterator_category(),
(typename iterator_traits< _ForwardIter >::difference_type*)0);
}
inline void uninitialized_fill(unsigned char* __first, unsigned char* __last,
const unsigned char& __val) {
unsigned char __tmp = __val;
memset(__first, __tmp, __last - __first);
}
inline void uninitialized_fill(signed char* __first, signed char* __last,
const signed char& __val) {
signed char __tmp = __val;
memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
}
inline void uninitialized_fill(char* __first, char* __last, const char& __val) {
char __tmp = __val;
memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
}
} namespace NStlPriv {
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __ufill_n(_ForwardIter __first, _Size __n, const _Tp& __x) {
_ForwardIter __cur = __first;
try {
for ( ; __n > 0; --__n, ++__cur)
_Param_Construct(&*__cur, __x);
}
catch(...) { ::NStl::_Destroy_Range(__first, __cur); throw; }
return __cur;
}
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __ufill_n(_ForwardIter __first, _Size __n, const _Tp& __x,
const input_iterator_tag &)
{ return __ufill_n(__first, __n, __x); }
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x) {
_ForwardIter __last = __first + __n;
__ufill(__first, __last, __x, random_access_iterator_tag(), (ptrdiff_t*)0);
return __last;
}
template <class _ForwardIter, class _Size>
inline _ForwardIter uninitialized_fill_n_nofill(_ForwardIter __first, _Size __n) {
_ForwardIter __cur = __first;
for ( ; __n > 0; --__n, ++__cur)
_ConstructNoFill(&*__cur);
return __cur;
}
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __ufill_n(_ForwardIter __first, _Size __n, const _Tp& __x,
const random_access_iterator_tag &)
{ return __uninitialized_fill_n(__first, __n, __x); }
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uinit_aux_aux(_ForwardIter __first, _Size __n, const _Tp& __val,
const __false_type& )
{ return __uninitialized_fill_n(__first, __n, __val); }
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uinit_aux_aux(_ForwardIter __first, _Size __n, const _Tp& __val,
const __true_type& ) {
(void)__val;
if (!(__builtin_constant_p(__n) && __n == 0))
memset((unsigned char*)__first, 0, __n * sizeof(_Tp));
return __first + __n;
}
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uinit_aux(_ForwardIter __first, _Size __n, const _Tp&,
const __true_type& )
{ return __first + __n; }
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uinit_aux(_ForwardIter __first, _Size __n, const _Tp& __val,
const __false_type& )
{ return __uinit_aux_aux(__first, __n, __val, _HasDefaultZeroValue(__first)._Answer()); }
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter __uninitialized_init(_ForwardIter __first, _Size __n, const _Tp& __val)
{ return __uinit_aux(__first, __n, __val, _UseTrivialInit(__first)._Answer()); }
} namespace NStl {
template <class _ForwardIter, class _Size, class _Tp>
inline void
uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
{ ::NStlPriv:: __ufill_n(__first, __n, __x, typename iterator_traits< _ForwardIter >::iterator_category()); }
} namespace NStlPriv {
template <class _InputIter1, class _InputIter2, class _ForwardIter>
inline _ForwardIter
__uninitialized_copy_copy(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_ForwardIter __result)
{ return uninitialized_copy(__first2, __last2, uninitialized_copy(__first1, __last1, __result)); }
template <class _ForwardIter, class _Tp, class _InputIter>
inline _ForwardIter
__uninitialized_fill_copy(_ForwardIter __result, _ForwardIter __mid, const _Tp& __x,
_InputIter __first, _InputIter __last) {
uninitialized_fill(__result, __mid, __x);
try {
return uninitialized_copy(__first, __last, __mid);
}
catch(...) { ::NStl::_Destroy_Range(__result, __mid); throw; }
}
template <class _Iter, class _Tp>
inline void
__uninitialized_copy_fill(_Iter __first1, _Iter __last1, _Iter __first2, _Iter __last2,
const _Tp& __x) {
_Iter __mid2 = uninitialized_copy(__first1, __last1, __first2);
try {
uninitialized_fill(__mid2, __last2, __x);
}
catch(...) { ::NStl::_Destroy_Range(__first2, __mid2); throw; }
}
template <class _InputIter, class _ForwardIter, class _TrivialUCpy>
inline _ForwardIter
__uninitialized_move(_InputIter __first, _InputIter __last, _ForwardIter __result,
_TrivialUCpy __trivial_ucpy, const __false_type& )
{ return __ucopy_ptrs(__first, __last, __result, __trivial_ucpy); }
template <class _InputIter, class _ForwardIter, class _TrivialUCpy>
inline
_ForwardIter
__uninitialized_move(_InputIter __first, _InputIter __last, _ForwardIter __result,
_TrivialUCpy , const __true_type& ) {
for (ptrdiff_t __n = __last - __first ; __n > 0; --__n) {
_Move_Construct(&*__result, *__first);
++__first; ++__result;
}
return __result;
}
} namespace NStl {
}
namespace NStl {
template <class _Tp>
pair<_Tp*, ptrdiff_t>
__get_temporary_buffer(ptrdiff_t __len, _Tp*);
template <class _Tp>
inline pair<_Tp*, ptrdiff_t> get_temporary_buffer(ptrdiff_t __len) {
return __get_temporary_buffer(__len, (_Tp*) 0);
}
template <class _Tp>
inline pair<_Tp*, ptrdiff_t>
get_temporary_buffer(ptrdiff_t __len, _Tp*) {
return __get_temporary_buffer(__len, (_Tp*) 0);
}
template <class _Tp>
inline void return_temporary_buffer(_Tp* __p) {
free((char*)__p);
}
template <class _ForwardIterator, class _Tp>
class _Temporary_buffer {
private:
ptrdiff_t _M_original_len;
ptrdiff_t _M_len;
_Tp* _M_buffer;
void _M_allocate_buffer() {
_M_original_len = _M_len;
_M_buffer = 0;
if (_M_len > (ptrdiff_t)(2147483647 / sizeof(_Tp)))
_M_len = 2147483647 / sizeof(_Tp);
while (_M_len > 0) {
_M_buffer = (_Tp*) malloc(_M_len * sizeof(_Tp));
if (_M_buffer)
break;
_M_len /= 2;
}
}
void _M_initialize_buffer(const _Tp&, const __true_type&) {}
void _M_initialize_buffer(const _Tp& val, const __false_type&) {
uninitialized_fill_n(_M_buffer, _M_len, val);
}
public:
ptrdiff_t size() const { return _M_len; }
ptrdiff_t requested_size() const { return _M_original_len; }
_Tp* begin() { return _M_buffer; }
_Tp* end() { return _M_buffer + _M_len; }
_Temporary_buffer(_ForwardIterator __first, _ForwardIterator __last) {
typedef typename __type_traits<_Tp>::has_trivial_default_constructor _Trivial;
try {
_M_len = distance(__first, __last);
_M_allocate_buffer();
if (_M_len > 0)
_M_initialize_buffer(*__first, _Trivial());
}
catch(...) { free(_M_buffer); _M_buffer = 0; _M_len = 0; throw; }
}
~_Temporary_buffer() {
::NStl::_Destroy_Range(_M_buffer, _M_buffer + _M_len);
free(_M_buffer);
}
private:
_Temporary_buffer(const _Temporary_buffer<_ForwardIterator, _Tp>&) {}
void operator=(const _Temporary_buffer<_ForwardIterator, _Tp>&) {}
};
template <class _ForwardIterator,
class _Tp
= typename iterator_traits<_ForwardIterator>::value_type
>
struct temporary_buffer : public _Temporary_buffer<_ForwardIterator, _Tp>
{
temporary_buffer(_ForwardIterator __first, _ForwardIterator __last)
: _Temporary_buffer<_ForwardIterator, _Tp>(__first, __last) {}
~temporary_buffer() {}
};
}
namespace NStl {
template <class _Tp>
pair<_Tp*, ptrdiff_t>
__get_temporary_buffer(ptrdiff_t __len, _Tp*)
{
if (__len > ptrdiff_t(2147483647 / sizeof(_Tp)))
__len = 2147483647 / sizeof(_Tp);
while (__len > 0) {
_Tp* __tmp = (_Tp*) malloc((size_t)__len * sizeof(_Tp));
if (__tmp != 0)
return pair<_Tp*, ptrdiff_t>(__tmp, __len);
__len /= 2;
}
return pair<_Tp*, ptrdiff_t>((_Tp*)0, 0);
}
}
namespace NStl {
} namespace NStlPriv {
template <class _BidirectionalIter, class _Distance, class _Compare>
void __merge_without_buffer(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last,
_Distance __len1, _Distance __len2,
_Compare __comp);
template <class _BidirectionalIter1, class _BidirectionalIter2,
class _BidirectionalIter3, class _Compare>
_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
_BidirectionalIter1 __last1,
_BidirectionalIter2 __first2,
_BidirectionalIter2 __last2,
_BidirectionalIter3 __result,
_Compare __comp);
template <class _Tp>
inline
const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
if (__a < __b)
if (__b < __c)
return __b;
else if (__a < __c)
return __c;
else
return __a;
else if (__a < __c)
return __a;
else if (__b < __c)
return __c;
else
return __b;
}
template <class _Tp, class _Compare>
inline
const _Tp&
__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
if (__comp(__a, __b)) {
if (__comp(__b, __c)) {
return __b;
}
else if (__comp(__a, __c)) {
return __c;
}
else
return __a;
}
else if (__comp(__a, __c)) {
return __a;
}
else if (__comp(__b, __c)) {
return __c;
}
else
return __b;
}
} namespace NStl {
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2) {
if (__first1 == __last1 || __first2 == __last2)
return __first1;
_ForwardIter2 __p1(__first2);
if ( ++__p1 == __last2 )
return find(__first1, __last1, *__first2);
for ( ; ; ) {
__first1 = find(__first1, __last1, *__first2);
if (__first1 == __last1)
return __last1;
_ForwardIter2 __p = __p1;
_ForwardIter1 __current = __first1;
if (++__current == __last1)
return __last1;
while (*__current == *__p) {
if (++__p == __last2)
return __first1;
if (++__current == __last1)
return __last1;
}
++__first1;
}
return __first1;
}
} namespace NStlPriv {
template <class _RandomAccessIter, class _Integer, class _Tp,
class _BinaryPred, class _Distance>
_RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
_Integer __count, const _Tp& __val, _BinaryPred __pred,
_Distance*, const random_access_iterator_tag &)
{
_Distance __tailSize = __last - __first;
const _Distance __pattSize = __count;
const _Distance __skipOffset = __pattSize - 1;
_RandomAccessIter __backTrack;
_Distance __remainder, __prevRemainder;
for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) {
__tailSize -= __pattSize;
while ( !__pred(*__lookAhead, __val) ) {
if (__tailSize < __pattSize)
return __last;
__lookAhead += __pattSize;
__tailSize -= __pattSize;
}
if ( __skipOffset == 0 ) {
return (__lookAhead - __skipOffset);
}
__remainder = __skipOffset;
for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) {
if (--__remainder == 0)
return (__lookAhead - __skipOffset);
}
if (__remainder > __tailSize)
return __last;
__lookAhead += __remainder;
__tailSize -= __remainder;
while ( __pred(*__lookAhead, __val) ) {
__prevRemainder = __remainder;
__backTrack = __lookAhead;
do {
if (--__remainder == 0)
return (__lookAhead - __skipOffset);
} while (__pred(*--__backTrack, __val));
__remainder += __pattSize - __prevRemainder;
if (__remainder > __tailSize)
return __last;
__lookAhead += __remainder;
__tailSize -= __remainder;
}
}
return __last;
}
template <class _ForwardIter, class _Integer, class _Tp,
class _Distance, class _BinaryPred>
_ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val, _BinaryPred __pred,
_Distance*, const forward_iterator_tag &) {
for (; (__first != __last) && !__pred(*__first, __val); ++__first) {}
while (__first != __last) {
_Integer __n = __count - 1;
_ForwardIter __i = __first;
++__i;
while (__i != __last && __n != 0 && __pred(*__i, __val)) {
++__i;
--__n;
}
if (__n == 0)
return __first;
else if (__i != __last)
for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {}
else
break;
}
return __last;
}
} namespace NStl {
template <class _ForwardIter, class _Integer, class _Tp>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val) {
if (__count <= 0)
return __first;
if (__count == 1)
return find(__first, __last, __val);
return ::NStlPriv:: __search_n(__first, __last, __count, __val, equal_to<_Tp>(),
(typename iterator_traits< _ForwardIter >::difference_type*)0,
typename iterator_traits< _ForwardIter >::iterator_category());
}
template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
_Integer __count, const _Tp& __val,
_BinaryPred __binary_pred) {
if (__count <= 0)
return __first;
return ::NStlPriv:: __search_n(__first, __last, __count, __val, __binary_pred,
(typename iterator_traits< _ForwardIter >::difference_type*)0,
typename iterator_traits< _ForwardIter >::iterator_category());
}
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1
find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2) {
return ::NStlPriv:: __find_end(__first1, __last1, __first2, __last2,
typename iterator_traits< _ForwardIter1 >::iterator_category(),
typename iterator_traits< _ForwardIter2 >::iterator_category(),
::NStlPriv:: __equal_to((typename iterator_traits< _ForwardIter1 >::value_type*)0)
);
}
} namespace NStlPriv {
template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,
class _Tp>
inline _OutputIterator
__unique_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result,
_BinaryPredicate __binary_pred, _Tp*) {
_Tp __val = *__first;
*__result = __val;
while (++__first != __last)
if (!__binary_pred(__val, *__first)) {
__val = *__first;
*++__result = __val;
}
return ++__result;
}
template <class _InputIter, class _OutputIter, class _BinaryPredicate>
inline _OutputIter
__unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
_BinaryPredicate __binary_pred, const output_iterator_tag &) {
return __unique_copy(__first, __last, __result, __binary_pred, (typename iterator_traits< _InputIter >::value_type*)0);
}
template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
inline _ForwardIter
__unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result,
_BinaryPredicate __binary_pred, const forward_iterator_tag &) {
*__result = *__first;
while (++__first != __last)
if (!__binary_pred(*__result, *__first)) *++__result = *__first;
return ++__result;
}
} namespace NStl {
template <class _InputIter, class _OutputIter>
_OutputIter
unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
if (__first == __last) return __result;
return ::NStlPriv:: __unique_copy(__first, __last, __result,
::NStlPriv:: __equal_to((typename iterator_traits< _InputIter >::value_type*)0),
typename iterator_traits< _OutputIter >::iterator_category());
}
template <class _InputIter, class _OutputIter, class _BinaryPredicate>
_OutputIter
unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
_BinaryPredicate __binary_pred) {
if (__first == __last) return __result;
return ::NStlPriv:: __unique_copy(__first, __last, __result, __binary_pred,
typename iterator_traits< _OutputIter >::iterator_category());
}
} namespace NStlPriv {
template <class _ForwardIter, class _Distance>
_ForwardIter __rotate_aux(_ForwardIter __first,
_ForwardIter __middle,
_ForwardIter __last,
_Distance*,
const forward_iterator_tag &) {
if (__first == __middle)
return __last;
if (__last == __middle)
return __first;
_ForwardIter __first2 = __middle;
do {
swap(*__first++, *__first2++);
if (__first == __middle)
__middle = __first2;
} while (__first2 != __last);
_ForwardIter __new_middle = __first;
__first2 = __middle;
while (__first2 != __last) {
swap (*__first++, *__first2++);
if (__first == __middle)
__middle = __first2;
else if (__first2 == __last)
__first2 = __middle;
}
return __new_middle;
}
template <class _BidirectionalIter, class _Distance>
_BidirectionalIter __rotate_aux(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last,
_Distance*,
const bidirectional_iterator_tag &) {
if (__first == __middle)
return __last;
if (__last == __middle)
return __first;
__reverse(__first, __middle, bidirectional_iterator_tag());
__reverse(__middle, __last, bidirectional_iterator_tag());
while (__first != __middle && __middle != __last)
swap (*__first++, *--__last);
if (__first == __middle) {
__reverse(__middle, __last, bidirectional_iterator_tag());
return __last;
}
else {
__reverse(__first, __middle, bidirectional_iterator_tag());
return __first;
}
}
template <class _RandomAccessIter, class _Distance, class _Tp>
_RandomAccessIter __rotate_aux(_RandomAccessIter __first,
_RandomAccessIter __middle,
_RandomAccessIter __last,
_Distance *, _Tp *) {
_Distance __n = __last - __first;
_Distance __k = __middle - __first;
_Distance __l = __n - __k;
_RandomAccessIter __result = __first + (__last - __middle);
if (__k == 0)
return __last;
if (__k == __l) {
swap_ranges(__first, __middle, __middle);
return __result;
}
_Distance __d = __gcd(__n, __k);
for (_Distance __i = 0; __i < __d; __i++) {
_Tp __tmp = *__first;
_RandomAccessIter __p = __first;
if (__k < __l) {
for (_Distance __j = 0; __j < __l/__d; __j++) {
if (__p > __first + __l) {
*__p = *(__p - __l);
__p -= __l;
}
*__p = *(__p + __k);
__p += __k;
}
}
else {
for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
if (__p < __last - __k) {
*__p = *(__p + __k);
__p += __k;
}
*__p = * (__p - __l);
__p -= __l;
}
}
*__p = __tmp;
++__first;
}
return __result;
}
template <class _RandomAccessIter, class _Distance>
inline _RandomAccessIter
__rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
_Distance * __dis, const random_access_iterator_tag &) {
return __rotate_aux(__first, __middle, __last,
__dis, (typename iterator_traits< _RandomAccessIter >::value_type*)0);
}
template <class _ForwardIter>
_ForwardIter
__rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
return __rotate_aux(__first, __middle, __last,
(typename iterator_traits< _ForwardIter >::difference_type*)0,
typename iterator_traits< _ForwardIter >::iterator_category());
}
} namespace NStl {
template <class _ForwardIter>
void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
::NStlPriv:: __rotate(__first, __middle, __last);
}
} namespace NStlPriv {
template <class _Distance>
inline _Distance __random_number(_Distance __n) {
return rand() % __n;
}
} namespace NStl {
template <class _RandomAccessIter>
void random_shuffle(_RandomAccessIter __first,
_RandomAccessIter __last) {
if (__first == __last) return;
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
iter_swap(__i, __first + ::NStlPriv:: __random_number((__i - __first) + 1));
}
template <class _RandomAccessIter, class _RandomNumberGenerator>
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
_RandomNumberGenerator &__rand) {
if (__first == __last) return;
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
iter_swap(__i, __first + __rand((__i - __first) + 1));
}
template <class _ForwardIter, class _OutputIter, class _Distance>
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
_OutputIter __out_ite, const _Distance __n) {
_Distance __remaining = distance(__first, __last);
_Distance __m = (min) (__n, __remaining);
while (__m > 0) {
if (::NStlPriv:: __random_number(__remaining) < __m) {
*__out_ite = *__first;
++__out_ite;
--__m;
}
--__remaining;
++__first;
}
return __out_ite;
}
template <class _ForwardIter, class _OutputIter, class _Distance,
class _RandomNumberGenerator>
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
_OutputIter __out_ite, const _Distance __n,
_RandomNumberGenerator& __rand) {
_Distance __remaining = distance(__first, __last);
_Distance __m = (min) (__n, __remaining);
while (__m > 0) {
if (__rand(__remaining) < __m) {
*__out_ite = *__first;
++__out_ite;
--__m;
}
--__remaining;
++__first;
}
return __out_ite;
}
} namespace NStlPriv {
template <class _InputIter, class _RandomAccessIter, class _Distance>
_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
_RandomAccessIter __out_ite,
const _Distance __n) {
_Distance __m = 0;
_Distance __t = __n;
for ( ; __first != __last && __m < __n; ++__m, ++__first)
__out_ite[__m] = *__first;
while (__first != __last) {
++__t;
_Distance __M = __random_number(__t);
if (__M < __n)
__out_ite[__M] = *__first;
++__first;
}
return __out_ite + __m;
}
template <class _InputIter, class _RandomAccessIter,
class _RandomNumberGenerator, class _Distance>
_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
_RandomAccessIter __out_ite,
_RandomNumberGenerator& __rand,
const _Distance __n) {
_Distance __m = 0;
_Distance __t = __n;
for ( ; __first != __last && __m < __n; ++__m, ++__first)
__out_ite[__m] = *__first;
while (__first != __last) {
++__t;
_Distance __M = __rand(__t);
if (__M < __n)
__out_ite[__M] = *__first;
++__first;
}
return __out_ite + __m;
}
} namespace NStl {
template <class _InputIter, class _RandomAccessIter>
_RandomAccessIter
random_sample(_InputIter __first, _InputIter __last,
_RandomAccessIter __out_first, _RandomAccessIter __out_last) {
return ::NStlPriv:: __random_sample(__first, __last,
__out_first, __out_last - __out_first);
}
template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
_RandomAccessIter
random_sample(_InputIter __first, _InputIter __last,
_RandomAccessIter __out_first, _RandomAccessIter __out_last,
_RandomNumberGenerator& __rand) {
return ::NStlPriv:: __random_sample(__first, __last,
__out_first, __rand,
__out_last - __out_first);
}
} namespace NStlPriv {
template <class _ForwardIter, class _Predicate>
inline _ForwardIter __partition(_ForwardIter __first,
_ForwardIter __last,
_Predicate __pred,
const forward_iterator_tag &) {
if (__first == __last) return __first;
while (__pred(*__first))
if (++__first == __last) return __first;
_ForwardIter __next = __first;
while (++__next != __last) {
if (__pred(*__next)) {
swap(*__first, *__next);
++__first;
}
}
return __first;
}
template <class _BidirectionalIter, class _Predicate>
inline _BidirectionalIter __partition(_BidirectionalIter __first,
_BidirectionalIter __last,
_Predicate __pred,
const bidirectional_iterator_tag &) {
for (;;) {
for (;;) {
if (__first == __last)
return __first;
else if (__pred(*__first))
++__first;
else
break;
}
--__last;
for (;;) {
if (__first == __last)
return __first;
else if (!__pred(*__last))
--__last;
else
break;
}
iter_swap(__first, __last);
++__first;
}
}
} namespace NStl {
template <class _ForwardIter, class _Predicate>
_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
return ::NStlPriv:: __partition(__first, __last, __pred, typename iterator_traits< _ForwardIter >::iterator_category());
}
} namespace NStlPriv {
template <class _ForwardIter, class _Predicate, class _Distance>
_ForwardIter __inplace_stable_partition(_ForwardIter __first,
_ForwardIter __last,
_Predicate __pred, _Distance __len,
bool __pred_of_first, bool __pred_of_before_last) {
if (__len == 1)
return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;
_ForwardIter __middle = __first;
_Distance __half_len = __len / 2;
advance(__middle, __half_len);
return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),
__middle,
__inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));
}
template <class _ForwardIter, class _Pointer, class _Predicate,
class _Distance>
_ForwardIter __stable_partition_adaptive(_ForwardIter __first,
_ForwardIter __last,
_Predicate __pred, _Distance __len,
_Pointer __buffer, _Distance __buffer_size,
bool __pred_of_first, bool __pred_of_before_last) {
if (__len <= __buffer_size) {
_ForwardIter __result1 = __first;
_Pointer __result2 = __buffer;
if ((__first != __last) && (!__pred_of_first || __pred(*__first))) {
*__result2 = *__first;
++__result2; ++__first; --__len;
}
for (; __first != __last ; ++__first, --__len) {
if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) ||
((__len != 1) && __pred(*__first))){
*__result1 = *__first;
++__result1;
}
else {
*__result2 = *__first;
++__result2;
}
}
copy(__buffer, __result2, __result1);
return __result1;
}
else {
_ForwardIter __middle = __first;
_Distance __half_len = __len / 2;
advance(__middle, __half_len);
return __rotate(__stable_partition_adaptive(
__first, __middle, __pred,
__half_len, __buffer, __buffer_size,
__pred_of_first, false),
__middle,
__stable_partition_adaptive(
__middle, __last, __pred,
__len - __half_len, __buffer, __buffer_size,
true, __pred_of_before_last));
}
}
template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
inline _ForwardIter
__stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) {
_Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
return (__buf.size() > 0) ?
__stable_partition_adaptive(__first, __last, __pred,
_Distance(__buf.requested_size()),
__buf.begin(), __buf.size(),
false, __pred_of_before_last) :
__inplace_stable_partition(__first, __last, __pred,
_Distance(__buf.requested_size()),
false, __pred_of_before_last);
}
template <class _ForwardIter, class _Predicate>
_ForwardIter
__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,
const forward_iterator_tag &) {
return __stable_partition_aux_aux(__first, __last, __pred,
(typename iterator_traits< _ForwardIter >::value_type*)0,
(typename iterator_traits< _ForwardIter >::difference_type*)0);
}
template <class _BidirectIter, class _Predicate>
_BidirectIter
__stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
const bidirectional_iterator_tag &) {
for (--__last;;) {
if (__first == __last)
return __first;
else if (!__pred(*__last))
--__last;
else
break;
}
++__last;
return __stable_partition_aux_aux(__first, __last, __pred,
(typename iterator_traits< _BidirectIter >::value_type*)0,
(typename iterator_traits< _BidirectIter >::difference_type*)0, true);
}
} namespace NStl {
template <class _ForwardIter, class _Predicate>
_ForwardIter
stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
for (;;) {
if (__first == __last)
return __first;
else if (__pred(*__first))
++__first;
else
break;
}
return ::NStlPriv:: __stable_partition_aux(__first, __last, __pred,
typename iterator_traits< _ForwardIter >::iterator_category());
}
} namespace NStlPriv {
template <class _RandomAccessIter, class _Tp, class _Compare>
_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
_RandomAccessIter __last,
_Tp __pivot, _Compare __comp) {
for (;;) {
while (__comp(*__first, __pivot)) {
++__first;
}
--__last;
while (__comp(__pivot, *__last)) {
--__last;
}
if (!(__first < __last))
return __first;
iter_swap(__first, __last);
++__first;
}
}
template <class _RandomAccessIter, class _Tp, class _Compare>
void __unguarded_linear_insert(_RandomAccessIter __last, const _Tp& __val_in,
_Compare __comp) {
const _Tp __val(__val_in);
_RandomAccessIter __next = __last;
--__next;
while (__comp(__val, *__next)) {
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
template <class _RandomAccessIter, class _Tp, class _Compare>
inline void __linear_insert(_RandomAccessIter __first,
_RandomAccessIter __last, const _Tp& __val_in, _Compare __comp) {
const _Tp __val(__val_in);
if (__comp(__val, *__first)) {
copy_backward(__first, __last, __last + 1);
*__first = __val;
}
else
__unguarded_linear_insert(__last, __val, __comp);
}
template <class _RandomAccessIter, class _Tp, class _Compare>
void __insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last,
_Tp *, _Compare __comp) {
if (__first == __last) return;
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
__linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp);
}
template <class _RandomAccessIter, class _Tp, class _Compare>
void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
_RandomAccessIter __last,
_Tp*, _Compare __comp) {
for (_RandomAccessIter __i = __first; __i != __last; ++__i)
__unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp);
}
template <class _RandomAccessIter, class _Compare>
inline void __unguarded_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last,
_Compare __comp) {
__unguarded_insertion_sort_aux(__first, __last, (typename iterator_traits< _RandomAccessIter >::value_type*)0, __comp);
}
template <class _RandomAccessIter, class _Compare>
void __final_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last, _Compare __comp) {
if (__last - __first > (16 * 4)) {
__insertion_sort(__first, __first + (16 * 4), (typename iterator_traits< _RandomAccessIter >::value_type*)0, __comp);
__unguarded_insertion_sort(__first + (16 * 4), __last, __comp);
}
else
__insertion_sort(__first, __last, (typename iterator_traits< _RandomAccessIter >::value_type*)0, __comp);
}
template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
void __introsort_loop(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*,
_Size __depth_limit, _Compare __comp) {
while (__last - __first > (16 * 4)) {
if (__depth_limit == 0) {
partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_RandomAccessIter __cut =
__unguarded_partition(__first, __last,
_Tp(__median(*__first,
*(__first + (__last - __first)/2),
*(__last - 1), __comp)),
__comp);
__introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
__last = __cut;
}
}
} namespace NStl {
template <class _RandomAccessIter>
void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
if (__first != __last) {
::NStlPriv:: __introsort_loop(__first, __last,
(typename iterator_traits< _RandomAccessIter >::value_type*)0,
::NStlPriv:: __lg(__last - __first) * 2,
::NStlPriv:: __less((typename iterator_traits< _RandomAccessIter >::value_type*)0));
::NStlPriv:: __final_insertion_sort(__first, __last,
::NStlPriv:: __less((typename iterator_traits< _RandomAccessIter >::value_type*)0));
}
}
template <class _RandomAccessIter, class _Compare>
void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
if (__first != __last) {
::NStlPriv:: __introsort_loop(__first, __last,
(typename iterator_traits< _RandomAccessIter >::value_type*)0,
::NStlPriv:: __lg(__last - __first) * 2, __comp);
::NStlPriv:: __final_insertion_sort(__first, __last, __comp);
}
}
} namespace NStlPriv {
template <class _RandomAccessIter, class _Compare>
void __inplace_stable_sort(_RandomAccessIter __first,
_RandomAccessIter __last, _Compare __comp) {
if (__last - __first < 15) {
__insertion_sort(__first, __last, (typename iterator_traits< _RandomAccessIter >::value_type*)0, __comp);
return;
}
_RandomAccessIter __middle = __first + (__last - __first) / 2;
__inplace_stable_sort(__first, __middle, __comp);
__inplace_stable_sort(__middle, __last, __comp);
__merge_without_buffer(__first, __middle, __last,
__middle - __first,
__last - __middle,
__comp);
}
template <class _RandomAccessIter1, class _RandomAccessIter2,
class _Distance, class _Compare>
void __merge_sort_loop(_RandomAccessIter1 __first,
_RandomAccessIter1 __last,
_RandomAccessIter2 __result, _Distance __step_size,
_Compare __comp) {
_Distance __two_step = 2 * __step_size;
while (__last - __first >= __two_step) {
__result = merge(__first, __first + __step_size,
__first + __step_size, __first + __two_step,
__result,
__comp);
__first += __two_step;
}
__step_size = (min) (_Distance(__last - __first), __step_size);
merge(__first, __first + __step_size,
__first + __step_size, __last,
__result,
__comp);
}
const int __stl_chunk_size = 7;
template <class _RandomAccessIter, class _Distance, class _Compare>
void __chunk_insertion_sort(_RandomAccessIter __first,
_RandomAccessIter __last,
_Distance __chunk_size, _Compare __comp) {
while (__last - __first >= __chunk_size) {
__insertion_sort(__first, __first + __chunk_size,
(typename iterator_traits< _RandomAccessIter >::value_type*)0, __comp);
__first += __chunk_size;
}
__insertion_sort(__first, __last, (typename iterator_traits< _RandomAccessIter >::value_type*)0, __comp);
}
template <class _RandomAccessIter, class _Pointer, class _Distance,
class _Compare>
void __merge_sort_with_buffer(_RandomAccessIter __first,
_RandomAccessIter __last, _Pointer __buffer,
_Distance*, _Compare __comp) {
_Distance __len = __last - __first;
_Pointer __buffer_last = __buffer + __len;
_Distance __step_size = __stl_chunk_size;
__chunk_insertion_sort(__first, __last, __step_size, __comp);
while (__step_size < __len) {
__merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
__step_size *= 2;
__merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
__step_size *= 2;
}
}
template <class _BidirectionalIter1, class _BidirectionalIter2,
class _Distance>
_BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
_BidirectionalIter1 __middle,
_BidirectionalIter1 __last,
_Distance __len1, _Distance __len2,
_BidirectionalIter2 __buffer,
_Distance __buffer_size) {
if (__len1 > __len2 && __len2 <= __buffer_size) {
_BidirectionalIter2 __buffer_end = copy(__middle, __last, __buffer);
copy_backward(__first, __middle, __last);
return copy(__buffer, __buffer_end, __first);
}
else if (__len1 <= __buffer_size) {
_BidirectionalIter2 __buffer_end = copy(__first, __middle, __buffer);
copy(__middle, __last, __first);
return copy_backward(__buffer, __buffer_end, __last);
}
else
return __rotate(__first, __middle, __last);
}
template <class _BidirectionalIter, class _Distance, class _Pointer,
class _Compare>
void __merge_adaptive(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last,
_Distance __len1, _Distance __len2,
_Pointer __buffer, _Distance __buffer_size,
_Compare __comp) {
if (__len1 <= __len2 && __len1 <= __buffer_size) {
_Pointer __buffer_end = copy(__first, __middle, __buffer);
merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
}
else if (__len2 <= __buffer_size) {
_Pointer __buffer_end = copy(__middle, __last, __buffer);
__merge_backward(__first, __middle, __buffer, __buffer_end, __last,
__comp);
}
else {
_BidirectionalIter __first_cut = __first;
_BidirectionalIter __second_cut = __middle;
_Distance __len11 = 0;
_Distance __len22 = 0;
if (__len1 > __len2) {
__len11 = __len1 / 2;
advance(__first_cut, __len11);
__second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
__len22 += distance(__middle, __second_cut);
}
else {
__len22 = __len2 / 2;
advance(__second_cut, __len22);
__first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
__len11 += distance(__first, __first_cut);
}
_BidirectionalIter __new_middle =
__rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
__len22, __buffer, __buffer_size);
__merge_adaptive(__first, __first_cut, __new_middle, __len11,
__len22, __buffer, __buffer_size, __comp);
__merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
__len2 - __len22, __buffer, __buffer_size, __comp);
}
}
template <class _RandomAccessIter, class _Pointer, class _Distance,
class _Compare>
void __stable_sort_adaptive(_RandomAccessIter __first,
_RandomAccessIter __last, _Pointer __buffer,
_Distance __buffer_size, _Compare __comp) {
_Distance __len = (__last - __first + 1) / 2;
_RandomAccessIter __middle = __first + __len;
if (__len > __buffer_size) {
__stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
__comp);
__stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
__comp);
}
else {
__merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
__comp);
__merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
__comp);
}
__merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
_Distance(__last - __middle), __buffer, __buffer_size,
__comp);
}
template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
void __stable_sort_aux(_RandomAccessIter __first,
_RandomAccessIter __last, _Tp*, _Distance*,
_Compare __comp) {
_Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
if (buf.begin() == 0)
__inplace_stable_sort(__first, __last, __comp);
else
__stable_sort_adaptive(__first, __last, buf.begin(),
_Distance(buf.size()),
__comp);
}
} namespace NStl {
template <class _RandomAccessIter>
void stable_sort(_RandomAccessIter __first,
_RandomAccessIter __last) {
::NStlPriv:: __stable_sort_aux(__first, __last,
(typename iterator_traits< _RandomAccessIter >::value_type*)0,
(typename iterator_traits< _RandomAccessIter >::difference_type*)0,
::NStlPriv:: __less((typename iterator_traits< _RandomAccessIter >::value_type*)0));
}
template <class _RandomAccessIter, class _Compare>
void stable_sort(_RandomAccessIter __first,
_RandomAccessIter __last, _Compare __comp) {
::NStlPriv:: __stable_sort_aux(__first, __last,
(typename iterator_traits< _RandomAccessIter >::value_type*)0,
(typename iterator_traits< _RandomAccessIter >::difference_type*)0,
__comp);
}
} namespace NStlPriv {
template <class _RandomAccessIter, class _Tp, class _Compare>
void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
_RandomAccessIter __last, _Tp*, _Compare __comp) {
make_heap(__first, __middle, __comp);
for (_RandomAccessIter __i = __middle; __i < __last; ++__i) {
if (__comp(*__i, *__first)) {
__pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
(typename iterator_traits< _RandomAccessIter >::difference_type*)0);
}
}
sort_heap(__first, __middle, __comp);
}
} namespace NStl {
template <class _RandomAccessIter>
void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
_RandomAccessIter __last) {
::NStlPriv:: __partial_sort(__first, __middle, __last, (typename iterator_traits< _RandomAccessIter >::value_type*)0,
::NStlPriv:: __less((typename iterator_traits< _RandomAccessIter >::value_type*)0));
}
template <class _RandomAccessIter, class _Compare>
void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
_RandomAccessIter __last, _Compare __comp) {
::NStlPriv:: __partial_sort(__first, __middle, __last, (typename iterator_traits< _RandomAccessIter >::value_type*)0, __comp);
}
} namespace NStlPriv {
template <class _InputIter, class _RandomAccessIter, class _Compare,
class _Distance, class _Tp>
_RandomAccessIter __partial_sort_copy(_InputIter __first,
_InputIter __last,
_RandomAccessIter __result_first,
_RandomAccessIter __result_last,
_Compare __comp, _Distance*, _Tp*) {
if (__result_first == __result_last) return __result_last;
_RandomAccessIter __result_real_last = __result_first;
while(__first != __last && __result_real_last != __result_last) {
*__result_real_last = *__first;
++__result_real_last;
++__first;
}
make_heap(__result_first, __result_real_last, __comp);
while (__first != __last) {
if (__comp(*__first, *__result_first)) {
__adjust_heap(__result_first, _Distance(0),
_Distance(__result_real_last - __result_first),
_Tp(*__first),
__comp);
}
++__first;
}
sort_heap(__result_first, __result_real_last, __comp);
return __result_real_last;
}
} namespace NStl {
template <class _InputIter, class _RandomAccessIter>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
_RandomAccessIter __result_first, _RandomAccessIter __result_last) {
return ::NStlPriv:: __partial_sort_copy(__first, __last, __result_first, __result_last,
::NStlPriv:: __less((typename iterator_traits< _InputIter >::value_type*)0),
(typename iterator_traits< _RandomAccessIter >::difference_type*)0,
(typename iterator_traits< _InputIter >::value_type*)0);
}
template <class _InputIter, class _RandomAccessIter, class _Compare>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
_RandomAccessIter __result_first,
_RandomAccessIter __result_last, _Compare __comp) {
return ::NStlPriv:: __partial_sort_copy(__first, __last, __result_first, __result_last,
__comp,
(typename iterator_traits< _RandomAccessIter >::difference_type*)0,
(typename iterator_traits< _InputIter >::value_type*)0);
}
} namespace NStlPriv {
template <class _RandomAccessIter, class _Tp, class _Compare>
void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
_RandomAccessIter __last, _Tp*, _Compare __comp) {
while (__last - __first > 3) {
_RandomAccessIter __cut =
__unguarded_partition(__first, __last,
_Tp(__median(*__first,
*(__first + (__last - __first)/2),
*(__last - 1),
__comp)),
__comp);
if (__cut <= __nth)
__first = __cut;
else
__last = __cut;
}
__insertion_sort(__first, __last, (typename iterator_traits< _RandomAccessIter >::value_type*)0, __comp);
}
} namespace NStl {
template <class _RandomAccessIter>
void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
_RandomAccessIter __last) {
::NStlPriv:: __nth_element(__first, __nth, __last, (typename iterator_traits< _RandomAccessIter >::value_type*)0,
::NStlPriv:: __less((typename iterator_traits< _RandomAccessIter >::value_type*)0));
}
template <class _RandomAccessIter, class _Compare>
void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
_RandomAccessIter __last, _Compare __comp) {
::NStlPriv:: __nth_element(__first, __nth, __last, (typename iterator_traits< _RandomAccessIter >::value_type*)0, __comp);
}
} namespace NStlPriv {
template <class _ForwardIter, class _Tp,
class _Compare1, class _Compare2, class _Distance>
_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
_Compare1 __comp1, _Compare2 __comp2, _Distance*) {
(void)__comp2;
(void)__comp1;
_Distance __len = distance(__first, __last);
_Distance __half;
while (__len > 0) {
__half = __len >> 1;
_ForwardIter __middle = __first;
advance(__middle, __half);
if (__comp2(__val, *__middle)) {
__len = __half;
}
else {
__first = __middle;
++__first;
__len = __len - __half - 1;
}
}
return __first;
}
template <class _ForwardIter, class _Tp,
class _Compare1, class _Compare2, class _Distance>
pair<_ForwardIter, _ForwardIter>
__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
_Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) {
_Distance __len = distance(__first, __last);
_Distance __half;
while (__len > 0) {
__half = __len >> 1;
_ForwardIter __middle = __first;
advance(__middle, __half);
if (__comp1(*__middle, __val)) {
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else if (__comp2(__val, *__middle)) {
__len = __half;
}
else {
_ForwardIter __left = __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist);
if (__comp1(*__left, __val)) {
return pair<_ForwardIter, _ForwardIter>(__left, __left);
}
advance(__first, __len);
_ForwardIter __right = __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist);
return pair<_ForwardIter, _ForwardIter>(__left, __right);
}
}
return pair<_ForwardIter, _ForwardIter>(__first, __first);
}
} namespace NStl {
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result) {
while (__first1 != __last1 && __first2 != __last2) {
if (*__first2 < *__first1) {
*__result = *__first2;
++__first2;
}
else {
*__result = *__first1;
++__first1;
}
++__result;
}
return copy(__first2, __last2, copy(__first1, __last1, __result));
}
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
while (__first1 != __last1 && __first2 != __last2) {
if (__comp(*__first2, *__first1)) {
*__result = *__first2;
++__first2;
}
else {
*__result = *__first1;
++__first1;
}
++__result;
}
return copy(__first2, __last2, copy(__first1, __last1, __result));
}
} namespace NStlPriv {
template <class _BidirectionalIter, class _Distance, class _Compare>
void __merge_without_buffer(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last,
_Distance __len1, _Distance __len2,
_Compare __comp) {
if (__len1 == 0 || __len2 == 0)
return;
if (__len1 + __len2 == 2) {
if (__comp(*__middle, *__first)) {
iter_swap(__first, __middle);
}
return;
}
_BidirectionalIter __first_cut = __first;
_BidirectionalIter __second_cut = __middle;
_Distance __len11 = 0;
_Distance __len22 = 0;
if (__len1 > __len2) {
__len11 = __len1 / 2;
advance(__first_cut, __len11);
__second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
__len22 += distance(__middle, __second_cut);
}
else {
__len22 = __len2 / 2;
advance(__second_cut, __len22);
__first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
__len11 +=distance(__first, __first_cut);
}
_BidirectionalIter __new_middle
= __rotate(__first_cut, __middle, __second_cut);
__merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
__comp);
__merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
__len2 - __len22, __comp);
}
template <class _BidirectionalIter1, class _BidirectionalIter2,
class _BidirectionalIter3, class _Compare>
_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
_BidirectionalIter1 __last1,
_BidirectionalIter2 __first2,
_BidirectionalIter2 __last2,
_BidirectionalIter3 __result,
_Compare __comp) {
if (__first1 == __last1)
return copy_backward(__first2, __last2, __result);
if (__first2 == __last2)
return copy_backward(__first1, __last1, __result);
--__last1;
--__last2;
for (;;) {
if (__comp(*__last2, *__last1)) {
*--__result = *__last1;
if (__first1 == __last1)
return copy_backward(__first2, ++__last2, __result);
--__last1;
}
else {
*--__result = *__last2;
if (__first2 == __last2)
return copy_backward(__first1, ++__last1, __result);
--__last2;
}
}
}
template <class _BidirectionalIter, class _Tp,
class _Distance, class _Compare>
inline void __inplace_merge_aux(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last, _Tp*, _Distance*,
_Compare __comp) {
_Distance __len1 = distance(__first, __middle);
_Distance __len2 = distance(__middle, __last);
_Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
if (__buf.begin() == 0)
__merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
else
__merge_adaptive(__first, __middle, __last, __len1, __len2,
__buf.begin(), _Distance(__buf.size()),
__comp);
}
} namespace NStl {
template <class _BidirectionalIter>
void inplace_merge(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last) {
if (__first == __middle || __middle == __last)
return;
::NStlPriv:: __inplace_merge_aux(__first, __middle, __last,
(typename iterator_traits< _BidirectionalIter >::value_type*)0, (typename iterator_traits< _BidirectionalIter >::difference_type*)0,
::NStlPriv:: __less((typename iterator_traits< _BidirectionalIter >::value_type*)0));
}
template <class _BidirectionalIter, class _Compare>
void inplace_merge(_BidirectionalIter __first,
_BidirectionalIter __middle,
_BidirectionalIter __last, _Compare __comp) {
if (__first == __middle || __middle == __last)
return;
::NStlPriv:: __inplace_merge_aux(__first, __middle, __last,
(typename iterator_traits< _BidirectionalIter >::value_type*)0, (typename iterator_traits< _BidirectionalIter >::difference_type*)0,
__comp);
}
} namespace NStlPriv {
template <class _InputIter1, class _InputIter2, class _Compare>
bool __includes(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first2, *__first1)) {
return false;
}
else if (__comp(*__first1, *__first2))
++__first1;
else
++__first1, ++__first2;
return __first2 == __last2;
}
} namespace NStl {
template <class _InputIter1, class _InputIter2, class _Compare>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
return ::NStlPriv:: __includes(__first1, __last1, __first2, __last2, __comp);
}
template <class _InputIter1, class _InputIter2>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2) {
return ::NStlPriv:: __includes(__first1, __last1, __first2, __last2,
::NStlPriv:: __less((typename iterator_traits< _InputIter1 >::value_type*)0));
}
} namespace NStlPriv {
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
while (__first1 != __last1 && __first2 != __last2) {
if (__comp(*__first1, *__first2)) {
*__result = *__first1;
++__first1;
}
else if (__comp(*__first2, *__first1)) {
*__result = *__first2;
++__first2;
}
else {
*__result = *__first1;
++__first1;
++__first2;
}
++__result;
}
return copy(__first2, __last2, copy(__first1, __last1, __result));
}
} namespace NStl {
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result) {
return ::NStlPriv:: __set_union(__first1, __last1, __first2, __last2, __result,
::NStlPriv:: __less((typename iterator_traits< _InputIter1 >::value_type*)0));
}
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
return ::NStlPriv:: __set_union(__first1, __last1, __first2, __last2, __result, __comp);
}
} namespace NStlPriv {
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first1, *__first2)) {
++__first1;
}
else if (__comp(*__first2, *__first1))
++__first2;
else {
*__result = *__first1;
++__first1;
++__first2;
++__result;
}
return __result;
}
} namespace NStl {
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result) {
return ::NStlPriv:: __set_intersection(__first1, __last1, __first2, __last2, __result,
::NStlPriv:: __less((typename iterator_traits< _InputIter1 >::value_type*)0));
}
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
return ::NStlPriv:: __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
}
} namespace NStlPriv {
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first1, *__first2)) {
*__result = *__first1;
++__first1;
++__result;
}
else if (__comp(*__first2, *__first1))
++__first2;
else {
++__first1;
++__first2;
}
return copy(__first1, __last1, __result);
}
} namespace NStl {
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result) {
return ::NStlPriv:: __set_difference(__first1, __last1, __first2, __last2, __result,
::NStlPriv:: __less((typename iterator_traits< _InputIter1 >::value_type*)0));
}
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
return ::NStlPriv:: __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
}
} namespace NStlPriv {
template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
_OutputIter
__set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
while (__first1 != __last1 && __first2 != __last2) {
if (__comp(*__first1, *__first2)) {
*__result = *__first1;
++__first1;
++__result;
}
else if (__comp(*__first2, *__first1)) {
*__result = *__first2;
++__first2;
++__result;
}
else {
++__first1;
++__first2;
}
}
return copy(__first2, __last2, copy(__first1, __last1, __result));
}
} namespace NStl {
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result) {
return ::NStlPriv:: __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
::NStlPriv:: __less((typename iterator_traits< _InputIter1 >::value_type*)0));
}
template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
_OutputIter
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result,
_Compare __comp) {
return ::NStlPriv:: __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
}
template <class _ForwardIter>
_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
if (__first == __last) return __first;
_ForwardIter __result = __first;
while (++__first != __last)
if (*__result < *__first)
__result = __first;
return __result;
}
template <class _ForwardIter, class _Compare>
_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
_Compare __comp) {
if (__first == __last) return __first;
_ForwardIter __result = __first;
while (++__first != __last) {
if (__comp(*__result, *__first)) {
__result = __first;
}
}
return __result;
}
template <class _ForwardIter>
_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
if (__first == __last) return __first;
_ForwardIter __result = __first;
while (++__first != __last)
if (*__first < *__result)
__result = __first;
return __result;
}
template <class _ForwardIter, class _Compare>
_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
_Compare __comp) {
if (__first == __last) return __first;
_ForwardIter __result = __first;
while (++__first != __last) {
if (__comp(*__first, *__result)) {
__result = __first;
}
}
return __result;
}
} namespace NStlPriv {
template <class _BidirectionalIter, class _Compare>
bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
_Compare __comp) {
if (__first == __last)
return false;
_BidirectionalIter __i = __first;
++__i;
if (__i == __last)
return false;
__i = __last;
--__i;
for(;;) {
_BidirectionalIter __ii = __i;
--__i;
if (__comp(*__i, *__ii)) {
_BidirectionalIter __j = __last;
while (!__comp(*__i, *--__j)) {}
iter_swap(__i, __j);
reverse(__ii, __last);
return true;
}
if (__i == __first) {
reverse(__first, __last);
return false;
}
}
}
} namespace NStl {
template <class _BidirectionalIter>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
return ::NStlPriv:: __next_permutation(__first, __last,
::NStlPriv:: __less((typename iterator_traits< _BidirectionalIter >::value_type*)0));
}
template <class _BidirectionalIter, class _Compare>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
_Compare __comp) {
return ::NStlPriv:: __next_permutation(__first, __last, __comp);
}
} namespace NStlPriv {
template <class _BidirectionalIter, class _Compare>
bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
_Compare __comp) {
if (__first == __last)
return false;
_BidirectionalIter __i = __first;
++__i;
if (__i == __last)
return false;
__i = __last;
--__i;
for(;;) {
_BidirectionalIter __ii = __i;
--__i;
if (__comp(*__ii, *__i)) {
_BidirectionalIter __j = __last;
while (!__comp(*--__j, *__i)) {}
iter_swap(__i, __j);
reverse(__ii, __last);
return true;
}
if (__i == __first) {
reverse(__first, __last);
return false;
}
}
}
} namespace NStl {
template <class _BidirectionalIter>
bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
return ::NStlPriv:: __prev_permutation(__first, __last,
::NStlPriv:: __less((typename iterator_traits< _BidirectionalIter >::value_type*)0));
}
template <class _BidirectionalIter, class _Compare>
bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
_Compare __comp) {
return ::NStlPriv:: __prev_permutation(__first, __last, __comp);
}
} namespace NStlPriv {
template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
_Distance __n) {
_Distance __parent = 0;
for (_Distance __child = 1; __child < __n; ++__child) {
if (__comp(__first[__parent], __first[__child])) {
return false;
}
if ((__child & 1) == 0)
++__parent;
}
return true;
}
} namespace NStl {
template <class _RandomAccessIter>
bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) {
return ::NStlPriv:: __is_heap(__first, ::NStlPriv:: __less((typename iterator_traits< _RandomAccessIter >::value_type*)0), __last - __first);
}
template <class _RandomAccessIter, class _StrictWeakOrdering>
bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
_StrictWeakOrdering __comp) {
return ::NStlPriv:: __is_heap(__first, __comp, __last - __first);
}
} namespace NStlPriv {
template <class _ForwardIter, class _StrictWeakOrdering>
bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
_StrictWeakOrdering __comp) {
if (__first == __last)
return true;
_ForwardIter __next = __first;
for (++__next; __next != __last; __first = __next, ++__next) {
if (__comp(*__next, *__first)) {
return false;
}
}
return true;
}
}
using namespace NStl;
static const uint64 k0 = 0xc3a5c85c97cb3127ULL;
static const uint64 k1 = 0xb492b66fbe98f273ULL;
static const uint64 k2 = 0x9ae16a3b2f90404fULL;
static const uint64 k3 = 0xc949d7c7509e6557ULL;
static uint64 Rotate(uint64 val, int shift) {
return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
}
static uint64 RotateByAtLeast1(uint64 val, int shift) {
return (val >> shift) | (val << (64 - shift));
}
static uint64 ShiftMix(uint64 val) {
return val ^ (val >> 47);
}
static uint64 HashLen16(uint64 u, uint64 v) {
return Hash128to64(uint128(u, v));
}
static uint64 HashLen0to16(const char *s, size_t len) {
if (len > 8) {
uint64 a = (*(const uint64*)(s));
uint64 b = (*(const uint64*)(s + len - 8));
return HashLen16(a, RotateByAtLeast1(b + len, static_cast<int>(len))) ^ b;
}
if (len >= 4) {
uint64 a = (*(const uint32*)(s));
return HashLen16(len + (a << 3), (*(const uint32*)(s + len - 4)));
}
if (len > 0) {
uint8 a = s[0];
uint8 b = s[len >> 1];
uint8 c = s[len - 1];
uint32 y = static_cast<uint32>(a) + (static_cast<uint32>(b) << 8);
uint32 z = static_cast<uint32>(len) + (static_cast<uint32>(c) << 2);
return ShiftMix(y * k2 ^ z * k3) * k2;
}
return k2;
}
static uint64 HashLen17to32(const char *s, size_t len) {
uint64 a = (*(const uint64*)(s)) * k1;
uint64 b = (*(const uint64*)(s + 8));
uint64 c = (*(const uint64*)(s + len - 8)) * k2;
uint64 d = (*(const uint64*)(s + len - 16)) * k0;
return HashLen16(Rotate(a - b, 43) + Rotate(c, 30) + d,
a + Rotate(b ^ k3, 20) - c + len);
}
static pair<uint64, uint64> WeakHashLen32WithSeeds(
uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b) {
a += w;
b = Rotate(b + a + z, 21);
uint64 c = a;
a += x;
a += y;
b += Rotate(a, 44);
return make_pair(a + z, b + c);
}
static pair<uint64, uint64> WeakHashLen32WithSeeds(
const char* s, uint64 a, uint64 b) {
return WeakHashLen32WithSeeds((*(const uint64*)(s)),
(*(const uint64*)(s + 8)),
(*(const uint64*)(s + 16)),
(*(const uint64*)(s + 24)),
a,
b);
}
static uint64 HashLen33to64(const char *s, size_t len) {
uint64 z = (*(const uint64*)(s + 24));
uint64 a = (*(const uint64*)(s)) + (len + (*(const uint64*)(s + len - 16))) * k0;
uint64 b = Rotate(a + z, 52);
uint64 c = Rotate(a, 37);
a += (*(const uint64*)(s + 8));
c += Rotate(a, 7);
a += (*(const uint64*)(s + 16));
uint64 vf = a + z;
uint64 vs = b + Rotate(a, 31) + c;
a = (*(const uint64*)(s + 16)) + (*(const uint64*)(s + len - 32));
z = (*(const uint64*)(s + len - 8));
b = Rotate(a + z, 52);
c = Rotate(a, 37);
a += (*(const uint64*)(s + len - 24));
c += Rotate(a, 7);
a += (*(const uint64*)(s + len - 16));
uint64 wf = a + z;
uint64 ws = b + Rotate(a, 31) + c;
uint64 r = ShiftMix((vf + ws) * k2 + (wf + vs) * k0);
return ShiftMix(r * k0 + vs) * k2;
}
template <class T>
static inline void DoSwap(T& l, T& r) {
const T tmp(l); l = r; r = tmp;
}
uint64 CityHash64(const char *s, size_t len) {
if (len <= 32) {
if (len <= 16) {
return HashLen0to16(s, len);
} else {
return HashLen17to32(s, len);
}
} else if (len <= 64) {
return HashLen33to64(s, len);
}
uint64 x = (*(const uint64*)(s));
uint64 y = (*(const uint64*)(s + len - 16)) ^ k1;
uint64 z = (*(const uint64*)(s + len - 56)) ^ k0;
pair<uint64, uint64> v = WeakHashLen32WithSeeds(s + len - 64, len, y);
pair<uint64, uint64> w = WeakHashLen32WithSeeds(s + len - 32, len * k1, k0);
z += ShiftMix(v.second) * k1;
x = Rotate(z + x, 39) * k1;
y = Rotate(y, 33) * k1;
len = (len - 1) & ~static_cast<size_t>(63);
do {
x = Rotate(x + y + v.first + (*(const uint64*)(s + 16)), 37) * k1;
y = Rotate(y + v.second + (*(const uint64*)(s + 48)), 42) * k1;
x ^= w.second;
y ^= v.first;
z = Rotate(z ^ w.first, 33);
v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);
DoSwap(z, x);
s += 64;
len -= 64;
} while (len != 0);
return HashLen16(HashLen16(v.first, w.first) + ShiftMix(y) * k1 + z,
HashLen16(v.second, w.second) + x);
}
uint64 CityHash64WithSeed(const char *s, size_t len, uint64 seed) {
return CityHash64WithSeeds(s, len, k2, seed);
}
uint64 CityHash64WithSeeds(const char *s, size_t len,
uint64 seed0, uint64 seed1) {
return HashLen16(CityHash64(s, len) - seed0, seed1);
}
static uint128 CityMurmur(const char *s, size_t len, uint128 seed) {
uint64 a = Uint128Low64(seed);
uint64 b = Uint128High64(seed);
uint64 c = 0;
uint64 d = 0;
ssize_t l = len - 16;
if (l <= 0) {
c = b * k1 + HashLen0to16(s, len);
d = Rotate(a + (len >= 8 ? (*(const uint64*)(s)) : c), 32);
} else {
c = HashLen16((*(const uint64*)(s + len - 8)) + k1, a);
d = HashLen16(b + len, c + (*(const uint64*)(s + len - 16)));
a += d;
do {
a ^= ShiftMix((*(const uint64*)(s)) * k1) * k1;
a *= k1;
b ^= a;
c ^= ShiftMix((*(const uint64*)(s + 8)) * k1) * k1;
c *= k1;
d ^= c;
s += 16;
l -= 16;
} while (l > 0);
}
a = HashLen16(a, c);
b = HashLen16(d, b);
return uint128(a ^ b, HashLen16(b, a));
}
uint128 CityHash128WithSeed(const char *s, size_t len, uint128 seed) {
if (len < 128) {
return CityMurmur(s, len, seed);
}
pair<uint64, uint64> v, w;
uint64 x = Uint128Low64(seed);
uint64 y = Uint128High64(seed);
uint64 z = len * k1;
v.first = Rotate(y ^ k1, 49) * k1 + (*(const uint64*)(s));
v.second = Rotate(v.first, 42) * k1 + (*(const uint64*)(s + 8));
w.first = Rotate(y + z, 35) * k1 + x;
w.second = Rotate(x + (*(const uint64*)(s + 88)), 53) * k1;
do {
x = Rotate(x + y + v.first + (*(const uint64*)(s + 16)), 37) * k1;
y = Rotate(y + v.second + (*(const uint64*)(s + 48)), 42) * k1;
x ^= w.second;
y ^= v.first;
z = Rotate(z ^ w.first, 33);
v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);
DoSwap(z, x);
s += 64;
x = Rotate(x + y + v.first + (*(const uint64*)(s + 16)), 37) * k1;
y = Rotate(y + v.second + (*(const uint64*)(s + 48)), 42) * k1;
x ^= w.second;
y ^= v.first;
z = Rotate(z ^ w.first, 33);
v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
w = WeakHashLen32WithSeeds(s + 32, z + w.second, y);
DoSwap(z, x);
s += 64;
len -= 128;
} while (__builtin_expect(!!(len >= 128), 1));
y += Rotate(w.first, 37) * k0 + z;
x += Rotate(v.first + z, 49) * k0;
for (size_t tail_done = 0; tail_done < len; ) {
tail_done += 32;
y = Rotate(y - x, 42) * k0 + v.second;
w.first += (*(const uint64*)(s + len - tail_done + 16));
x = Rotate(x, 49) * k0 + w.first;
w.first += v.first;
v = WeakHashLen32WithSeeds(s + len - tail_done, v.first, v.second);
}
x = HashLen16(x, v.first);
y = HashLen16(y, w.first);
return uint128(HashLen16(x + v.second, w.second) + y,
HashLen16(x + w.second, y + v.second));
}
uint128 CityHash128(const char *s, size_t len) {
if (len >= 16) {
return CityHash128WithSeed(s + 16,
len - 16,
uint128((*(const uint64*)(s)) ^ k3,
(*(const uint64*)(s + 8))));
} else if (len >= 8) {
return CityHash128WithSeed(__null,
0,
uint128((*(const uint64*)(s)) ^ (len * k0),
(*(const uint64*)(s + len - 8)) ^ k1));
} else {
return CityHash128WithSeed(s, len, uint128(k0, k1));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment