template <class _ForwardIter>inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle,                           _ForwardIter __last) {  return __rotate(__first, __middle, __last,                  __DISTANCE_TYPE(__first),                  __ITERATOR_CATEGORY(__first));}template <class _ForwardIter, class _OutputIter>_OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,                            _ForwardIter __last, _OutputIter __result) {  return copy(__first, __middle, copy(__middle, __last, __result));}// Return a random number in the range [0, __n).  This function encapsulates// whether we're using rand (part of the standard C library) or lrand48// (not standard, but a much better choice whenever it's available).template <class _Distance>inline _Distance __random_number(_Distance __n) {#ifdef __STL_NO_DRAND48  return rand() % __n;#else  return lrand48() % __n;#endif}// random_shuffletemplate <class _RandomAccessIter>inline void random_shuffle(_RandomAccessIter __first,                           _RandomAccessIter __last) {  if (__first == __last) return;  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)    iter_swap(__i, __first + __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));}// random_sample and random_sample_n (extensions, not part of the standard).template <class _ForwardIter, class _OutputIter, class _Distance>_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,                            _OutputIter __out, const _Distance __n){  _Distance __remaining = 0;  distance(__first, __last, __remaining);  _Distance __m = min(__n, __remaining);  while (__m > 0) {    if (__random_number(__remaining) < __m) {      *__out = *__first;      ++__out;      --__m;    }    --__remaining;    ++__first;  }  return __out;}template <class _ForwardIter, class _OutputIter, class _Distance,          class _RandomNumberGenerator>_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,                            _OutputIter __out, const _Distance __n,                            _RandomNumberGenerator& __rand){  _Distance __remaining = 0;  distance(__first, __last, __remaining);  _Distance __m = min(__n, __remaining);  while (__m > 0) {    if (__rand(__remaining) < __m) {      *__out = *__first;      ++__out;      --__m;    }    --__remaining;    ++__first;  }  return __out;}template <class _InputIter, class _RandomAccessIter, class _Distance>_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,                                  _RandomAccessIter __out,                                  const _Distance __n){  _Distance __m = 0;  _Distance __t = __n;  for ( ; __first != __last && __m < __n; ++__m, ++__first)     __out[__m] = *__first;  while (__first != __last) {    ++__t;    _Distance __M = __random_number(__t);    if (__M < __n)      __out[__M] = *__first;    ++__first;  }  return __out + __m;}template <class _InputIter, class _RandomAccessIter,          class _RandomNumberGenerator, class _Distance>_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,                                  _RandomAccessIter __out,                                  _RandomNumberGenerator& __rand,                                  const _Distance __n){  _Distance __m = 0;  _Distance __t = __n;  for ( ; __first != __last && __m < __n; ++__m, ++__first)    __out[__m] = *__first;  while (__first != __last) {    ++__t;    _Distance __M = __rand(__t);    if (__M < __n)      __out[__M] = *__first;    ++__first;  }  return __out + __m;}template <class _InputIter, class _RandomAccessIter>inline _RandomAccessIterrandom_sample(_InputIter __first, _InputIter __last,              _RandomAccessIter __out_first, _RandomAccessIter __out_last) {  return __random_sample(__first, __last,                         __out_first, __out_last - __out_first);}template <class _InputIter, class _RandomAccessIter,           class _RandomNumberGenerator>inline _RandomAccessIterrandom_sample(_InputIter __first, _InputIter __last,              _RandomAccessIter __out_first, _RandomAccessIter __out_last,              _RandomNumberGenerator& __rand) {  return __random_sample(__first, __last,                         __out_first, __rand,                         __out_last - __out_first);}// partition, stable_partition, and their auxiliary functionstemplate <class _ForwardIter, class _Predicate>_ForwardIter __partition(_ForwardIter __first,		         _ForwardIter __last,			 _Predicate   __pred,			 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>_BidirectionalIter __partition(_BidirectionalIter __first,                               _BidirectionalIter __last,			       _Predicate __pred,			       bidirectional_iterator_tag) {  while (true) {    while (true)      if (__first == __last)        return __first;      else if (__pred(*__first))        ++__first;      else        break;    --__last;    while (true)      if (__first == __last)        return __first;      else if (!__pred(*__last))        --__last;      else        break;    iter_swap(__first, __last);    ++__first;  }}template <class _ForwardIter, class _Predicate>inline _ForwardIter partition(_ForwardIter __first,   			      _ForwardIter __last,			      _Predicate   __pred) {  return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first));}template <class _ForwardIter, class _Predicate, class _Distance>_ForwardIter __inplace_stable_partition(_ForwardIter __first,                                        _ForwardIter __last,                                        _Predicate __pred, _Distance __len) {  if (__len == 1)    return __pred(*__first) ? __last : __first;  _ForwardIter __middle = __first;  advance(__middle, __len / 2);  return rotate(__inplace_stable_partition(__first, __middle, __pred,                                            __len / 2),                __middle,                __inplace_stable_partition(__middle, __last, __pred,                                           __len - __len / 2));}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) {  if (__len <= __buffer_size) {    _ForwardIter __result1 = __first;    _Pointer __result2 = __buffer;    for ( ; __first != __last ; ++__first)      if (__pred(*__first)) {        *__result1 = *__first;        ++__result1;      }      else {        *__result2 = *__first;        ++__result2;      }    copy(__buffer, __result2, __result1);    return __result1;  }  else {    _ForwardIter __middle = __first;    advance(__middle, __len / 2);    return rotate(__stable_partition_adaptive(                          __first, __middle, __pred,                          __len / 2, __buffer, __buffer_size),                    __middle,                    __stable_partition_adaptive(                          __middle, __last, __pred,                          __len - __len / 2, __buffer, __buffer_size));  }}template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>inline _ForwardIter__stable_partition_aux(_ForwardIter __first, _ForwardIter __last,                        _Predicate __pred, _Tp*, _Distance*){  _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);  if (__buf.size() > 0)    return __stable_partition_adaptive(__first, __last, __pred,                                       _Distance(__buf.requested_size()),                                       __buf.begin(), __buf.size());  else    return __inplace_stable_partition(__first, __last, __pred,                                       _Distance(__buf.requested_size()));}template <class _ForwardIter, class _Predicate>inline _ForwardIter stable_partition(_ForwardIter __first,                                     _ForwardIter __last,                                      _Predicate __pred) {  if (__first == __last)    return __first;  else    return __stable_partition_aux(__first, __last, __pred,                                  __VALUE_TYPE(__first),                                  __DISTANCE_TYPE(__first));}template <class _RandomAccessIter, class _Tp>_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,                                         _RandomAccessIter __last,                                         _Tp __pivot) {  while (true) {    while (*__first < __pivot)      ++__first;    --__last;    while (__pivot < *__last)      --__last;    if (!(__first < __last))      return __first;    iter_swap(__first, __last);    ++__first;  }}    template <class _RandomAccessIter, class _Tp, class _Compare>_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,                                         _RandomAccessIter __last,                                         _Tp __pivot, _Compare __comp) {  while (true) {    while (__comp(*__first, __pivot))      ++__first;    --__last;    while (__comp(__pivot, *__last))      --__last;    if (!(__first < __last))      return __first;    iter_swap(__first, __last);    ++__first;  }}const int __stl_threshold = 16;// sort() and its auxiliary functions. template <class _RandomAccessIter, class _Tp>void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {  _RandomAccessIter __next = __last;  --__next;  while (__val < *__next) {    *__last = *__next;    __last = __next;    --__next;  }  *__last = __val;}template <class _RandomAccessIter, class _Tp, class _Compare>void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,                                _Compare __comp) {  _RandomAccessIter __next = __last;  --__next;    while (__comp(__val, *__next)) {    *__last = *__next;    __last = __next;    --__next;  }  *__last = __val;}template <class _RandomAccessIter, class _Tp>inline void __linear_insert(_RandomAccessIter __first,                             _RandomAccessIter __last, _Tp*) {  _Tp __val = *__last;  if (__val < *__first) {    copy_backward(__first, __last, __last + 1);    *__first = __val;  }  else    __unguarded_linear_insert(__last, __val);}template <class _RandomAccessIter, class _Tp, class _Compare>inline void __linear_insert(_RandomAccessIter __first,                             _RandomAccessIter __last, _Tp*, _Compare __comp) {  _Tp __val = *__last;  if (__comp(__val, *__first)) {    copy_backward(__first, __last, __last + 1);    *__first = __val;  }  else    __unguarded_linear_insert(__last, __val, __comp);}template <class _RandomAccessIter>void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) {  if (__first == __last) return;   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)    __linear_insert(__first, __i, __VALUE_TYPE(__first));}template <class _RandomAccessIter, class _Compare>void __insertion_sort(_RandomAccessIter __first,                      _RandomAccessIter __last, _Compare __comp) {  if (__first == __last) return;  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)    __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp);}template <class _RandomAccessIter, class _Tp>void __unguarded_insertion_sort_aux(_RandomAccessIter __first,                                     _RandomAccessIter __last, _Tp*) {  for (_RandomAccessIter __i = __first; __i != __last; ++__i)    __unguarded_linear_insert(__i, _Tp(*__i));}template <class _RandomAccessIter>inline void __unguarded_insertion_sort(_RandomAccessIter __first,                                 _RandomAccessIter __last) {  __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first));}template <class _RandomAccessIter, class _Tp, class _Compare>