// algorithm standard header

#if     _MSC_VER > 1000
#pragma once
#endif

#ifndef _ALGORITHM_
#define _ALGORITHM_
#include <iterator>
#include <memory>
#include <xutility>

#ifdef  _MSC_VER
#pragma pack(push,8)
#endif  /* _MSC_VER */
_STD_BEGIN
const int _CHUNK_SIZE = 7;
const int _SORT_MAX = 16;
		// TEMPLATE FUNCTION _Median
template<class _Ty> inline
	_Ty _Median(_Ty _X, _Ty _Y, _Ty _Z)
		{if (_X < _Y)
			return (_Y < _Z ? _Y : _X < _Z ? _Z : _X);
		else
			return (_X < _Z ? _X : _Y < _Z ? _Z : _Y); }
		// TEMPLATE FUNCTION _Median WITH PRED
template<class _Ty, class _Pr> inline
	_Ty _Median(_Ty _X, _Ty _Y, _Ty _Z, _Pr _P)
		{if (_P(_X, _Y))
			return (_P(_Y, _Z) ? _Y : _P(_X, _Z) ? _Z : _X);
		else
			return (_P(_X, _Z) ? _X : _P(_Y, _Z) ? _Z : _Y); }
		// TEMPLATE FUNCTION for_each
template<class _II, class _Fn> inline
	_Fn for_each(_II _F, _II _L, _Fn _Op)
	{for (; _F != _L; ++_F)
		_Op(*_F);
	return (_Op); }
		// TEMPLATE FUNCTION find
template<class _II, class _Ty> inline
	_II find(_II _F, _II _L, const _Ty& _V)
	{for (; _F != _L; ++_F)
		if (*_F == _V)
			break;
	return (_F); }
		// TEMPLATE FUNCTION find_if
template<class _II, class _Pr> inline
	_II find_if(_II _F, _II _L, _Pr _P)
	{for (; _F != _L; ++_F)
		if (_P(*_F))
			break;
	return (_F); }
		// TEMPLATE FUNCTION adjacent_find
template<class _FI> inline
	_FI adjacent_find(_FI _F, _FI _L)
	{for (_FI _Fb; (_Fb = _F) != _L && ++_F != _L; )
		if (*_Fb == *_F)
			return (_Fb);
	return (_L); }
		// TEMPLATE FUNCTION adjacent_find WITH PRED
template<class _FI, class _Pr> inline
	_FI adjacent_find(_FI _F, _FI _L, _Pr _P)
	{for (_FI _Fb; (_Fb = _F) != _L && ++_F != _L; )
		if (_P(*_Fb, *_F))
			return (_Fb);
	return (_L); }
		// TEMPLATE FUNCTION count
template<class _II, class _Ty> inline
	_CNTSIZ(_II) count(_II _F, _II _L, const _Ty& _V)
	{_CNTSIZ(_II) _N = 0;
	for (; _F != _L; ++_F)
		if (*_F == _V)
			++_N;
	return (_N); }
		// TEMPLATE FUNCTION count_if
template<class _II, class _Pr> inline
	_CNTSIZ(_II) count_if(_II _F, _II _L, _Pr _P)
	{_CNTSIZ(_II) _N = 0;
	for (; _F != _L; ++_F)
		if (_P(*_F))
			++_N;
	return (_N); }
		// TEMPLATE FUNCTION search
template<class _FI1, class _FI2> inline
	_FI1 search(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2)
	{return (_Search(_F1, _L1, _F2, _L2,
		_Dist_type(_F1), _Dist_type(_F2))); }
template<class _FI1, class _FI2, class _Pd1, class _Pd2> inline
	_FI1 _Search(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2,
		_Pd1 *, _Pd2 *)
	{_Pd1 _D1 = 0;
	_Distance(_F1, _L1, _D1);
	_Pd2 _D2 = 0;
	_Distance(_F2, _L2, _D2);
	for (; _D2 <= _D1; ++_F1, --_D1)
		{_FI1 _X1 = _F1;
		for (_FI2 _X2 = _F2; ; ++_X1, ++_X2)
			if (_X2 == _L2)
				return (_F1);
			else if (!(*_X1 == *_X2))
				break; }
	return (_L1); }
		// TEMPLATE FUNCTION search WITH PRED
template<class _FI1, class _FI2, class _Pr> inline
	_FI1 search(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2, _Pr _P)
	{return (_Search(_F1, _L1, _F2, _L2, _P,
		_Dist_type(_F1), _Dist_type(_F2))); }
template<class _FI1, class _FI2, class _Pd1, class _Pd2,
	class _Pr> inline
	_FI1 _Search(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2,
		_Pr _P, _Pd1 *, _Pd2 *)
	{_Pd1 _D1 = 0;
	_Distance(_F1, _L1, _D1);
	_Pd2 _D2 = 0;
	_Distance(_F2, _L2, _D2);
	for (; _D2 <= _D1; ++_F1, --_D1)
		{_FI1 _X1 = _F1;
		for (_FI2 _X2 = _F2; ; ++_X1, ++_X2)
			if (_X2 == _L2)
				return (_F1);
			else if (!_P(*_X1, *_X2))
				break; }
	return (_L1); }
		// TEMPLATE FUNCTION search_n
template<class _FI1, class _Pd2, class _Ty> inline
	_FI1 search_n(_FI1 _F1, _FI1 _L1, _Pd2 _N, const _Ty& _V)
	{return (_Search_n(_F1, _L1, _N, _V, _Dist_type(_F1))); }
template<class _FI1, class _Pd2, class _Ty, class _Pd1> inline
	_FI1 _Search_n(_FI1 _F1, _FI1 _L1,
		_Pd2 _N, const _Ty& _V, _Pd1 *)
	{_Pd1 _D1 = 0;
	_Distance(_F1, _L1, _D1);
	for (; _N <= _D1; ++_F1, --_D1)
		{_FI1 _X1 = _F1;
		for (_Pd2 _D2 = _N; ; ++_X1, --_D2)
			if (_D2 == 0)
				return (_F1);
			else if (!(*_X1 == _V))
				break; }
	return (_L1); }
		// TEMPLATE FUNCTION search_n WITH PRED
template<class _FI1, class _Pd2, class _Ty, class _Pr> inline
	_FI1 search_n(_FI1 _F1, _FI1 _L1,
		_Pd2 _N, const _Ty& _V, _Pr _P)
	{return (_Search_n(_F1, _L1,
		_N, _V, _P, _Dist_type(_F1))); }
template<class _FI1, class _Pd2,
	class _Ty, class _Pd1, class _Pr> inline
	_FI1 _Search_n(_FI1 _F1, _FI1 _L1,
		_Pd2 _N, const _Ty& _V, _Pr _P, _Pd1 *)
	{_Pd1 _D1 = 0;
	_Distance(_F1, _L1, _D1);
	for (; _N <= _D1; ++_F1, --_D1)
		{_FI1 _X1 = _F1;
		for (_Pd2 _D2 = _N; ; ++_X1, --_D2)
			if (_D2 == 0)
				return (_F1);
			else if (!_P(*_X1, _V))
				break; }
	return (_L1); }
		// TEMPLATE FUNCTION find_end
template<class _FI1, class _FI2> inline
	_FI1 find_end(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2)
	{return (_Find_end(_F1, _L1, _F2, _L2,
		_Dist_type(_F1), _Dist_type(_F2))); }
template<class _FI1, class _FI2, class _Pd1, class _Pd2> inline
	_FI1 _Find_end(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2,
		_Pd1 *, _Pd2 *)
	{_Pd1 _D1 = 0;
	_Distance(_F1, _L1, _D1);
	_Pd2 _D2 = 0;
	_Distance(_F2, _L2, _D2);
	_FI1 _Ans = _L1;
	if (0 < _D2)
		for (; _D2 <= _D1; ++_F1, --_D1)
			{_FI1 _X1 = _F1;
			for (_FI2 _X2 = _F2; ; ++_X1)
				if (!(*_X1 == *_X2))
					break;
				else if (++_X2 == _L2)
					{_Ans = _F1;
					break; }}
	return (_Ans); }
		// TEMPLATE FUNCTION find_end WITH PRED
template<class _FI1, class _FI2, class _Pr> inline
	_FI1 find_end(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2, _Pr _P)
	{return (_Find_end(_F1, _L1, _F2, _L2, _P,
		_Dist_type(_F1), _Dist_type(_F2))); }
template<class _FI1, class _FI2, class _Pd1, class _Pd2,
	class _Pr> inline
	_FI1 _Find_end(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2, _Pr _P,
		_Pd1 *, _Pd2 *)
	{_Pd1 _D1 = 0;
	_Distance(_F1, _L1, _D1);
	_Pd2 _D2 = 0;
	_Distance(_F2, _L2, _D2);
	_FI1 _Ans = _L1;
	if (0 < _D2)
		for (; _D2 <= _D1; ++_F1, --_D1)
			{_FI1 _X1 = _F1;
			for (_FI2 _X2 = _F2; ; ++_X1)
				if (!_P(*_X1, *_X2))
					break;
				else if (++_X2 == _L2)
					{_Ans = _F1;
					break; }}
	return (_Ans); }
		// TEMPLATE FUNCTION find_first_of
template<class _FI1, class _FI2> inline
	_FI1 find_first_of(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2)
	{for (; _F1 != _L1; ++_F1)
		for (_FI2 _X2 = _F2; _X2 != _L2; ++_X2)
			if (*_F1 == *_X2)
				return (_F1);
	return (_F1); }
		// TEMPLATE FUNCTION find_first_of WITH PRED
template<class _FI1, class _FI2, class _Pr> inline
	_FI1 find_first_of(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2,
		_Pr _P)
	{for (; _F1 != _L1; ++_F1)
		for (_FI2 _X2 = _F2; _X2 != _L2; ++_X2)
			if (_P(*_F1, *_X2))
				return (_F1);
	return (_F1); }
		// TEMPLATE FUNCTION iter_swap
template<class _FI1, class _FI2> inline
	void iter_swap(_FI1 _X, _FI2 _Y)
	{_Iter_swap(_X, _Y, _Val_type(_X)); }
template<class _FI1, class _FI2, class _Ty> inline
	void _Iter_swap(_FI1 _X, _FI2 _Y, _Ty *)
	{_Ty _Tmp = *_X;
	*_X = *_Y, *_Y = _Tmp; }
		// TEMPLATE FUNCTION swap_ranges
template<class _FI1, class _FI2> inline
	_FI2 swap_ranges(_FI1 _F, _FI1 _L, _FI2 _X)
	{for (; _F != _L; ++_F, ++_X)
		iter_swap(_F, _X);
	return (_X); }
		// TEMPLATE FUNCTION transform WITH UNARY OP
template<class _II, class _OI, class _Uop> inline
	_OI transform(_II _F, _II _L, _OI _X, _Uop _U)
	{for (; _F != _L; ++_F, ++_X)
		*_X = _U(*_F);
	return (_X); }
		// TEMPLATE FUNCTION transform WITH BINARY OP
template<class _II1, class _II2, class _OI, class _Bop> inline
	_OI transform(_II1 _F1, _II1 _L1, _II2 _F2, _OI _X, _Bop _B)
	{for (; _F1 != _L1; ++_F1, ++_F2, ++_X)
		*_X = _B(*_F1, *_F2);
	return (_X); }
		// TEMPLATE FUNCTION replace
template<class _FI, class _Ty> inline
	void replace(_FI _F, _FI _L, const _Ty& _Vo, const _Ty& _Vn)
	{for (; _F != _L; ++_F)
		if (*_F == _Vo)
			*_F = _Vn; }
		// TEMPLATE FUNCTION replace_if
template<class _FI, class _Pr, class _Ty> inline
	void replace_if(_FI _F, _FI _L, _Pr _P, const _Ty& _V)
	{for (; _F != _L; ++_F)
		if (_P(*_F))
			*_F = _V; }
		// TEMPLATE FUNCTION replace_copy
template<class _II, class _OI, class _Ty> inline
	_OI replace_copy(_II _F, _II _L, _OI _X,
		const _Ty& _Vo, const _Ty& _Vn)
	{for (; _F != _L; ++_F, ++_X)
		*_X = *_F == _Vo ? _Vn : *_F;
		return (_X); }
		// TEMPLATE FUNCTION replace_copy_if
template<class _II, class _OI, class _Pr, class _Ty> inline
	_OI replace_copy_if(_II _F, _II _L, _OI _X,
		_Pr _P, const _Ty& _V)
	{for (; _F != _L; ++_F, ++_X)
		*_X = _P(*_F) ? _V : *_F;
		return (_X); }
		// TEMPLATE FUNCTION generate
template<class _FI, class _Gen> inline
	void generate(_FI _F, _FI _L, _Gen _G)
	{for (; _F != _L; ++_F)
		*_F = _G(); }
		// TEMPLATE FUNCTION generate_n
template<class _OI, class _Pd, class _Gen> inline
	void generate_n(_OI _F, _Pd _N, _Gen _G)
	{for (; 0 < _N; --_N, ++_F)
		*_F = _G(); }
		// TEMPLATE FUNCTION remove
template<class _FI, class _Ty> inline
	_FI remove(_FI _F, _FI _L, const _Ty& _V)
	{_F = find(_F, _L, _V);
	if (_F == _L)
		return (_F);
	else
		{_FI _Fb = _F;
		return (remove_copy(++_F, _L, _Fb, _V)); }}
		// TEMPLATE FUNCTION remove_if
template<class _FI, class _Pr> inline
	_FI remove_if(_FI _F, _FI _L, _Pr _P)
	{_F = find_if(_F, _L, _P);
	if (_F == _L)
		return (_F);
	else
		{_FI _Fb = _F;
		return (remove_copy_if(++_F, _L, _Fb, _P)); }}
		// TEMPLATE FUNCTION remove_copy
template<class _II, class _OI, class _Ty> inline
	_OI remove_copy(_II _F, _II _L, _OI _X, const _Ty& _V)
	{for (; _F != _L; ++_F)
		if (!(*_F == _V))
			*_X++ = *_F;
	return (_X); }
		// TEMPLATE FUNCTION remove_copy_if
template<class _II, class _OI, class _Pr> inline
	_OI remove_copy_if(_II _F, _II _L, _OI _X, _Pr _P)
	{for (; _F != _L; ++_F)
		if (!_P(*_F))
			*_X++ = *_F;
	return (_X); }
		// TEMPLATE FUNCTION unique
template<class _FI> inline
	_FI unique(_FI _F, _FI _L)
	{_F = adjacent_find(_F, _L);
	return (unique_copy(_F, _L, _F)); }
		// TEMPLATE FUNCTION unique WITH PRED
template<class _FI, class _Pr> inline
	_FI unique(_FI _F, _FI _L, _Pr _P)
	{_F = adjacent_find(_F, _L, _P);
	return (unique_copy(_F, _L, _F, _P)); }
		// TEMPLATE FUNCTION unique_copy
template<class _II, class _OI> inline
	_OI unique_copy(_II _F, _II _L, _OI _X)
	{return (_F == _L ? _X :
		_Unique_copy(_F, _L, _X, _Iter_cat(_F))); }
template<class _II, class _OI> inline
	_OI _Unique_copy(_II _F, _II _L, _OI _X, input_iterator_tag)
	{return (_Unique_copy(_F, _L, _X, _Val_type(_F))); }
template<class _II, class _OI, class _Ty> inline
	_OI _Unique_copy(_II _F, _II _L, _OI _X, _Ty *)
	{_Ty _V = *_F;
	for (*_X++ = _V; ++_F != _L; )
		if (!(_V == *_F))
			_V = *_F, *_X++ = _V;
	return (_X); }
template<class _FI, class _OI> inline
	_OI _Unique_copy(_FI _F, _FI _L, _OI _X, forward_iterator_tag)
	{_FI _Fb = _F;
	for (*_X++ = *_Fb; ++_F != _L; )
		if (!(*_Fb == *_F))
			_Fb = _F, *_X++ = *_Fb;
	return (_X); }
template<class _BI, class _OI> inline
	_OI _Unique_copy(_BI _F, _BI _L, _OI _X,
		bidirectional_iterator_tag)
	{return (_Unique_copy(_F, _L, _X, forward_iterator_tag())); }
template<class _RI, class _OI> inline
	_OI _Unique_copy(_RI _F, _RI _L, _OI _X,
		random_access_iterator_tag)
	{return (_Unique_copy(_F, _L, _X, forward_iterator_tag())); }
		// TEMPLATE FUNCTION unique_copy WITH PRED
template<class _II, class _OI, class _Pr> inline
	_OI unique_copy(_II _F, _II _L, _OI _X, _Pr _P)
	{return (_F == _L ? _X :
		_Unique_copy(_F, _L, _X, _P, _Iter_cat(_F))); }
template<class _II, class _OI, class _Pr> inline
	_OI _Unique_copy(_II _F, _II _L, _OI _X, _Pr _P,
		input_iterator_tag)
	{return (_Unique_copy(_F, _L, _X, _P, _Val_type(_F))); }
template<class _II, class _OI, class _Ty, class _Pr> inline
	_OI _Unique_copy(_II _F, _II _L, _OI _X, _Pr _P, _Ty *)
	{_Ty _V = *_F;
	for (*_X++ = _V; ++_F != _L; )
		if (!_P(_V, *_F))