// -*- C++ -*-

//===-------------------------- algorithm ---------------------------------===//

//

// The LLVM Compiler Infrastructure

//

// This file is dual licensed under the MIT and the University of Illinois Open

// Source Licenses. See LICENSE.TXT for details.

//

//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_ALGORITHM

#define _LIBCPP_ALGORITHM

/*

algorithm synopsis

#include <initializer_list>

namespace std

{

template <class InputIterator, class Predicate>

bool

all_of(InputIterator first, InputIterator last, Predicate pred);

template <class InputIterator, class Predicate>

bool

any_of(InputIterator first, InputIterator last, Predicate pred);

template <class InputIterator, class Predicate>

bool

none_of(InputIterator first, InputIterator last, Predicate pred);

template <class InputIterator, class Function>

Function

for_each(InputIterator first, InputIterator last, Function f);

template <class InputIterator, class T>

InputIterator

find(InputIterator first, InputIterator last, const T& value);

template <class InputIterator, class Predicate>

InputIterator

find_if(InputIterator first, InputIterator last, Predicate pred);

template<class InputIterator, class Predicate>

InputIterator

find_if_not(InputIterator first, InputIterator last, Predicate pred);

template <class ForwardIterator1, class ForwardIterator2>

ForwardIterator1

find_end(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, ForwardIterator2 last2);

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

ForwardIterator1

find_end(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

template <class ForwardIterator1, class ForwardIterator2>

ForwardIterator1

find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, ForwardIterator2 last2);

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

ForwardIterator1

find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

template <class ForwardIterator>

ForwardIterator

adjacent_find(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate>

ForwardIterator

adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

template <class InputIterator, class T>

typename iterator_traits<InputIterator>::difference_type

count(InputIterator first, InputIterator last, const T& value);

template <class InputIterator, class Predicate>

typename iterator_traits<InputIterator>::difference_type

count_if(InputIterator first, InputIterator last, Predicate pred);

template <class InputIterator1, class InputIterator2>

pair<InputIterator1, InputIterator2>

mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template <class InputIterator1, class InputIterator2>

pair<InputIterator1, InputIterator2>

mismatch(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2); // **C++14**

template <class InputIterator1, class InputIterator2, class BinaryPredicate>

pair<InputIterator1, InputIterator2>

mismatch(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, BinaryPredicate pred);

template <class InputIterator1, class InputIterator2, class BinaryPredicate>

pair<InputIterator1, InputIterator2>

mismatch(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

BinaryPredicate pred); // **C++14**

template <class InputIterator1, class InputIterator2>

bool

equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template <class InputIterator1, class InputIterator2>

bool

equal(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2); // **C++14**

template <class InputIterator1, class InputIterator2, class BinaryPredicate>

bool

equal(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, BinaryPredicate pred);

template <class InputIterator1, class InputIterator2, class BinaryPredicate>

bool

equal(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

BinaryPredicate pred); // **C++14**

template<class ForwardIterator1, class ForwardIterator2>

bool

is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2);

template<class ForwardIterator1, class ForwardIterator2>

bool

is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

bool

is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, BinaryPredicate pred);

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

bool

is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, ForwardIterator2 last2,

BinaryPredicate pred); // **C++14**

template <class ForwardIterator1, class ForwardIterator2>

ForwardIterator1

search(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, ForwardIterator2 last2);

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>

ForwardIterator1

search(ForwardIterator1 first1, ForwardIterator1 last1,

ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);

template <class ForwardIterator, class Size, class T>

ForwardIterator

search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);

template <class ForwardIterator, class Size, class T, class BinaryPredicate>

ForwardIterator

search_n(ForwardIterator first, ForwardIterator last,

Size count, const T& value, BinaryPredicate pred);

template <class InputIterator, class OutputIterator>

OutputIterator

copy(InputIterator first, InputIterator last, OutputIterator result);

template<class InputIterator, class OutputIterator, class Predicate>

OutputIterator

copy_if(InputIterator first, InputIterator last,

OutputIterator result, Predicate pred);

template<class InputIterator, class Size, class OutputIterator>

OutputIterator

copy_n(InputIterator first, Size n, OutputIterator result);

template <class BidirectionalIterator1, class BidirectionalIterator2>

BidirectionalIterator2

copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,

BidirectionalIterator2 result);

template <class ForwardIterator1, class ForwardIterator2>

ForwardIterator2

swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);

template <class ForwardIterator1, class ForwardIterator2>

void

iter_swap(ForwardIterator1 a, ForwardIterator2 b);

template <class InputIterator, class OutputIterator, class UnaryOperation>

OutputIterator

transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);

template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>

OutputIterator

transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,

OutputIterator result, BinaryOperation binary_op);

template <class ForwardIterator, class T>

void

replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);

template <class ForwardIterator, class Predicate, class T>

void

replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);

template <class InputIterator, class OutputIterator, class T>

OutputIterator

replace_copy(InputIterator first, InputIterator last, OutputIterator result,

const T& old_value, const T& new_value);

template <class InputIterator, class OutputIterator, class Predicate, class T>

OutputIterator

replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);

template <class ForwardIterator, class T>

void

fill(ForwardIterator first, ForwardIterator last, const T& value);

template <class OutputIterator, class Size, class T>

OutputIterator

fill_n(OutputIterator first, Size n, const T& value);

template <class ForwardIterator, class Generator>

void

generate(ForwardIterator first, ForwardIterator last, Generator gen);

template <class OutputIterator, class Size, class Generator>

OutputIterator

generate_n(OutputIterator first, Size n, Generator gen);

template <class ForwardIterator, class T>

ForwardIterator

remove(ForwardIterator first, ForwardIterator last, const T& value);

template <class ForwardIterator, class Predicate>

ForwardIterator

remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);

template <class InputIterator, class OutputIterator, class T>

OutputIterator

remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);

template <class InputIterator, class OutputIterator, class Predicate>

OutputIterator

remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);

template <class ForwardIterator>

ForwardIterator

unique(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate>

ForwardIterator

unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);

template <class InputIterator, class OutputIterator>

OutputIterator

unique_copy(InputIterator first, InputIterator last, OutputIterator result);

template <class InputIterator, class OutputIterator, class BinaryPredicate>

OutputIterator

unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);

template <class BidirectionalIterator>

void

reverse(BidirectionalIterator first, BidirectionalIterator last);

template <class BidirectionalIterator, class OutputIterator>

OutputIterator

reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);

template <class ForwardIterator>

ForwardIterator

rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

template <class ForwardIterator, class OutputIterator>

OutputIterator

rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);

template <class RandomAccessIterator>

void

random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14

template <class RandomAccessIterator, class RandomNumberGenerator>

void

random_shuffle(RandomAccessIterator first, RandomAccessIterator last,

RandomNumberGenerator& rand); // deprecated in C++14

template<class RandomAccessIterator, class UniformRandomNumberGenerator>

void shuffle(RandomAccessIterator first, RandomAccessIterator last,

UniformRandomNumberGenerator&& g);

template <class InputIterator, class Predicate>

bool

is_partitioned(InputIterator first, InputIterator last, Predicate pred);

template <class ForwardIterator, class Predicate>

ForwardIterator

partition(ForwardIterator first, ForwardIterator last, Predicate pred);

template <class InputIterator, class OutputIterator1,

class OutputIterator2, class Predicate>

pair<OutputIterator1, OutputIterator2>

partition_copy(InputIterator first, InputIterator last,

OutputIterator1 out_true, OutputIterator2 out_false,

Predicate pred);

template <class ForwardIterator, class Predicate>

ForwardIterator

stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);

template<class ForwardIterator, class Predicate>

ForwardIterator

partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);

template <class ForwardIterator>

bool

is_sorted(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class Compare>

bool

is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);

template<class ForwardIterator>

ForwardIterator

is_sorted_until(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class Compare>

ForwardIterator

is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);

template <class RandomAccessIterator>

void

sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>

void

sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template <class RandomAccessIterator>

void

stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>

void

stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template <class RandomAccessIterator>

void

partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>

void

partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

template <class InputIterator, class RandomAccessIterator>

RandomAccessIterator

partial_sort_copy(InputIterator first, InputIterator last,

RandomAccessIterator result_first, RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator, class Compare>

RandomAccessIterator

partial_sort_copy(InputIterator first, InputIterator last,

RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

template <class RandomAccessIterator>

void

nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>

void

nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

template <class ForwardIterator, class T>

ForwardIterator

lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

template <class ForwardIterator, class T, class Compare>

ForwardIterator

lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

template <class ForwardIterator, class T>

ForwardIterator

upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

template <class ForwardIterator, class T, class Compare>

ForwardIterator

upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

template <class ForwardIterator, class T>

pair<ForwardIterator, ForwardIterator>

equal_range(ForwardIterator first, ForwardIterator last, const T& value);

template <class ForwardIterator, class T, class Compare>

pair<ForwardIterator, ForwardIterator>

equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

template <class ForwardIterator, class T>

bool

binary_search(ForwardIterator first, ForwardIterator last, const T& value);

template <class ForwardIterator, class T, class Compare>

bool

binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

template <class InputIterator1, class InputIterator2, class OutputIterator>

OutputIterator

merge(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>

OutputIterator

merge(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

template <class BidirectionalIterator>

void

inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>

void

inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);

template <class InputIterator1, class InputIterator2>

bool

includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class Compare>

bool

includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

template <class InputIterator1, class InputIterator2, class OutputIterator>

OutputIterator

set_union(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>

OutputIterator

set_union(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

template <class InputIterator1, class InputIterator2, class OutputIterator>

OutputIterator

set_intersection(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>

OutputIterator

set_intersection(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

template <class InputIterator1, class InputIterator2, class OutputIterator>

OutputIterator

set_difference(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>

OutputIterator

set_difference(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

template <class InputIterator1, class InputIterator2, class OutputIterator>

OutputIterator

set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>

OutputIterator

set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

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>

void

pop_heap(RandomAccessIterator first, RandomAccessIterator last);

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>

void

sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>

void

sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template <class RandomAccessIterator>

bool

is_heap(RandomAccessIterator first, RandomAccessiterator last);

template <class RandomAccessIterator, class Compare>

bool

is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);

template <class RandomAccessIterator>

RandomAccessIterator

is_heap_until(RandomAccessIterator first, RandomAccessiterator last);

template <class RandomAccessIterator, class Compare>

RandomAccessIterator

is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);

template <class ForwardIterator>

ForwardIterator

min_element(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class Compare>

ForwardIterator

min_element(ForwardIterator first, ForwardIterator last, Compare comp);

template <class T>

const T&

min(const T& a, const T& b); // constexpr in C++14

template <class T, class Compare>

const T&

min(const T& a, const T& b, Compare comp); // constexpr in C++14

template<class T>

T

min(initializer_list<T> t); // constexpr in C++14

template<class T, class Compare>

T

min(initializer_list<T> t, Compare comp); // constexpr in C++14

template <class ForwardIterator>

ForwardIterator

max_element(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class Compare>

ForwardIterator

max_element(ForwardIterator first, ForwardIterator last, Compare comp);

template <class T>

const T&

max(const T& a, const T& b); // constexpr in C++14

template <class T, class Compare>

const T&

max(const T& a, const T& b, Compare comp); // constexpr in C++14

template<class T>

T

max(initializer_list<T> t); // constexpr in C++14

template<class T, class Compare>

T

max(initializer_list<T> t, Compare comp); // constexpr in C++14

template<class ForwardIterator>

pair<ForwardIterator, ForwardIterator>

minmax_element(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class Compare>

pair<ForwardIterator, ForwardIterator>

minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);

template<class T>

pair<const T&, const T&>

minmax(const T& a, const T& b); // constexpr in C++14

template<class T, class Compare>

pair<const T&, const T&>

minmax(const T& a, const T& b, Compare comp); // constexpr in C++14

template<class T>

pair<T, T>

minmax(initializer_list<T> t); // constexpr in C++14

template<class T, class Compare>

pair<T, T>

minmax(initializer_list<T> t, Compare comp); // constexpr in C++14

template <class InputIterator1, class InputIterator2>

bool

lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class Compare>

bool

lexicographical_compare(InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2, Compare comp);

template <class BidirectionalIterator>

bool

next_permutation(BidirectionalIterator first, BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>

bool

next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

template <class BidirectionalIterator>

bool

prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>

bool

prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

} // std

*/

#include <__config>

#include <initializer_list>

#include <type_traits>

#include <cstring>

#include <utility>

#include <memory>

#include <iterator>

#include <cstddef>

#if defined(__IBMCPP__)

#include "support/ibm/support.h"

#endif

#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__)

#include "support/win32/support.h"

#endif

#include <__undef_min_max>

#include <__debug>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

#pragma GCC system_header

#endif

_LIBCPP_BEGIN_NAMESPACE_STD

// I'd like to replace these with _VSTD::equal_to<void>, but can't because:

// * That only works with C++14 and later, and

// * We haven't included <functional> here.

template <class _T1, class _T2 = _T1>

struct __equal_to

{

_LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}

_LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;}

_LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;}

_LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}

};

template <class _T1>

struct __equal_to<_T1, _T1>

{

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}

};

template <class _T1>

struct __equal_to<const _T1, _T1>

{

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}

};

template <class _T1>

struct __equal_to<_T1, const _T1>

{

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}

};

template <class _T1, class _T2 = _T1>

struct __less

{

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;}

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;}

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}

};

template <class _T1>

struct __less<_T1, _T1>

{

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}

};

template <class _T1>

struct __less<const _T1, _T1>

{

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}

};

template <class _T1>

struct __less<_T1, const _T1>

{

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11

bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}

};

template <class _Predicate>

class __negate

{

private:

_Predicate __p_;

public:

_LIBCPP_INLINE_VISIBILITY __negate() {}

_LIBCPP_INLINE_VISIBILITY

explicit __negate(_Predicate __p) : __p_(__p) {}

template <class _T1>

_LIBCPP_INLINE_VISIBILITY

bool operator()(const _T1& __x) {return !__p_(__x);}

template <class _T1, class _T2>

_LIBCPP_INLINE_VISIBILITY

bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}

};

#ifdef _LIBCPP_DEBUG

template <class _Compare>

struct __debug_less

{

_Compare __comp_;

__debug_less(_Compare& __c) : __comp_(__c) {}

template <class _Tp, class _Up>

bool operator()(const _Tp& __x, const _Up& __y)

{

bool __r = __comp_(__x, __y);

if (__r)

_LIBCPP_ASSERT(!__comp_(__y, __x), "Comparator does not induce a strict weak ordering");

return __r;

}

};

#endif // _LIBCPP_DEBUG

// Precondition: __x != 0

inline _LIBCPP_INLINE_VISIBILITY

unsigned

__ctz(unsigned __x)

{

return static_cast<unsigned>(__builtin_ctz(__x));

}

inline _LIBCPP_INLINE_VISIBILITY

unsigned long

__ctz(unsigned long __x)

{

return static_cast<unsigned long>(__builtin_ctzl(__x));

}

inline _LIBCPP_INLINE_VISIBILITY

unsigned long long

__ctz(unsigned long long __x)

{

return static_cast<unsigned long long>(__builtin_ctzll(__x));

}

// Precondition: __x != 0

inline _LIBCPP_INLINE_VISIBILITY

unsigned

__clz(unsigned __x)

{

return static_cast<unsigned>(__builtin_clz(__x));

}

inline _LIBCPP_INLINE_VISIBILITY

unsigned long

__clz(unsigned long __x)

{

return static_cast<unsigned long>(__builtin_clzl (__x));

}

inline _LIBCPP_INLINE_VISIBILITY

unsigned long long

__clz(unsigned long long __x)

{

return static_cast<unsigned long long>(__builtin_clzll(__x));

}

inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {return __builtin_popcount (__x);}

inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {return __builtin_popcountl (__x);}

inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {return __builtin_popcountll(__x);}

// all_of

template <class _InputIterator, class _Predicate>

inline _LIBCPP_INLINE_VISIBILITY

bool

all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)

{

for (; __first != __last; ++__first)

if (!__pred(*__first))

return false;

return true;

}

// any_of

template <class _InputIterator, class _Predicate>

inline _LIBCPP_INLINE_VISIBILITY

bool

any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)

{

for (; __first != __last; ++__first)

if (__pred(*__first))

return true;

return false;

}

// none_of

template <class _InputIterator, class _Predicate>

inline _LIBCPP_INLINE_VISIBILITY

bool

none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)

{

for (; __first != __last; ++__first)

if (__pred(*__first))

return false;

return true;

}

// for_each

template <class _InputIterator, class _Function>

inline _LIBCPP_INLINE_VISIBILITY

_Function

for_each(_InputIterator __first, _InputIterator __last, _Function __f)

{

for (; __first != __last; ++__first)

__f(*__first);

return _VSTD::move(__f); // explicitly moved for (emulated) C++03

}

// find

template <class _InputIterator, class _Tp>

inline _LIBCPP_INLINE_VISIBILITY

_InputIterator

find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)

{

for (; __first != __last; ++__first)

if (*__first == __value_)

break;

return __first;

}

// find_if

template <class _InputIterator, class _Predicate>

inline _LIBCPP_INLINE_VISIBILITY

_InputIterator

find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)

{

for (; __first != __last; ++__first)

if (__pred(*__first))

break;

return __first;

}

// find_if_not

template<class _InputIterator, class _Predicate>

inline _LIBCPP_INLINE_VISIBILITY

_InputIterator

find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)

{

for (; __first != __last; ++__first)

if (!__pred(*__first))

break;

return __first;

}

// find_end

template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>

_ForwardIterator1

__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,

_ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,

forward_iterator_tag, forward_iterator_tag)

{

// modeled after search algorithm

_ForwardIterator1 __r = __last1; // __last1 is the "default" answer

if (__first2 == __last2)

return __r;

while (true)

{

while (true)

{

if (__first1 == __last1) // if source exhausted return last correct answer

return __r; // (or __last1 if never found)

if (__pred(*__first1, *__first2))

break;

++__first1;

}

// *__first1 matches *__first2, now match elements after here

_ForwardIterator1 __m1 = __first1;

_ForwardIterator2 __m2 = __first2;

while (true)

{

if (++__m2 == __last2)

{ // Pattern exhaused, record answer and search for another one

__r = __first1;

++__first1;

break;

}

if (++__m1 == __last1) // Source exhausted, return last answer

return __r;

if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first

{

++__first1;

break;

} // else there is a match, check next elements

}

}

}

template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>

_BidirectionalIterator1

__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,

_BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred,

bidirectional_iterator_tag, bidirectional_iterator_tag)

{

// modeled after search algorithm (in reverse)

if (__first2 == __last2)

return __last1; // Everything matches an empty sequence

_BidirectionalIterator1 __l1 = __last1;

_BidirectionalIterator2 __l2 = __last2;

--__l2;

while (true)

{

// Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks

while (true)

{

if (__first1 == __l1) // return __last1 if no element matches *__first2

return __last1;

if (__pred(*--__l1, *__l2))

break;

}

// *__l1 matches *__l2, now match elements before here

_BidirectionalIterator1 __m1 = __l1;

_BidirectionalIterator2 __m2 = __l2;

while (true)

{

if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)

return __m1;

if (__m1 == __first1) // Otherwise if source exhaused, pattern not found

return __last1;

if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1

{

break;

} // else there is a match, check next elements

}

}

}

template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>

_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1

__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,

_RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,

random_access_iterator_tag, random_access_iterator_tag)

{

// Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern

typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;

if (__len2 == 0)

return __last1;

typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;

if (__len1 < __len2)

return __last1;

const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here

_RandomAccessIterator1 __l1 = __last1;

_RandomAccessIterator2 __l2 = __last2;

--__l2;

while (true)

{

while (true)

{

if (__s == __l1)