/*ident	"@(#)Array_alg:incl/Array_alg.c	3.1" */
/******************************************************************************
*
* C++ Standard Components, Release 3.0.
*
* Copyright (c) 1991, 1992 AT&T and Unix System Laboratories, Inc.
* Copyright (c) 1988, 1989, 1990 AT&T.  All Rights Reserved.
*
* THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and Unix System
* Laboratories, Inc.  The copyright notice above does not evidence
* any actual or intended publication of such source code.
*
******************************************************************************/

#ifndef _ARRAY_ALG_C_
#define _ARRAY_ALG_C_

template <class T>
const T*
bin_loc(
	register const T& value,
	register const T* begin,
	register const T* end)
{
	while ( 5 < end - begin ) {
		register const T *index = begin + ((end - begin) >> 1);

		if (value < *index)
			end = index;
		else
			begin = index + 1;
	}

	while ( begin < end )
		if ( !(value < *--end) )
			return end + 1;

	return end;
}

template <class T>
const T*
bin_loc_r(
	int (*rel_ptr)(const T*, const T*),
	const T& value,
	register const T* begin,
	register const T* end)
{
	register const T *temp = &value;

	while ( 5 < end - begin ) {
		register const T *index = begin + ((end - begin) >> 1);

		if ( (*rel_ptr)(temp, index) < 0 )
			end = index;
		else
			begin = index + 1;
	}

	while ( begin < end )
		if ( !((*rel_ptr)(temp, --end) < 0) )
			return end + 1;

	return end;
}

template <class T>
const T* 
bin_search(
	const T &value,
	const T* begin,
	const T* end)
{
	const T *index = bin_loc(value, begin, end);

	if ( begin < index && !(*(index - 1) < value) )
		return index - 1;
	else
		return 0;
}

template <class T>
const T*
bin_search_r(
	int (*rel_ptr)(const T*, const T*),
	const T& value,
	const T* begin,
	const T* end)
{
	const T *index = bin_loc_r(rel_ptr, value, begin, end);

	if ( begin < index && !((*rel_ptr)(index - 1, &value) < 0) )
		return index - 1;
	
	return 0;
}

template <class T>
void
copy(
	register T* begin,
	register T* end,
	register T* result)
{
	if ( begin < result ) {
		result += end - begin;
		while ( begin < end )
			*--result = *--end;
	}
	else if ( result < begin )
		while (begin < end)
			*result++ = *begin++;
}

template <class T>
ptrdiff_t 
count(
	register const T& value,
	register const T* begin,
	register const T* end)
{
	register ptrdiff_t n = 0;

	while ( begin < end )
		if ( *begin++ == value )
			n++;

	return n;
}

template <class T>
ptrdiff_t 
count_p(
	register int (*pred_ptr)(const T*),
	register const T* begin,
	register const T* end)
{
	register ptrdiff_t n = 0;

	while ( begin < end )
		if ( (*pred_ptr)(begin++) )
			n++;

	return n;
}

template <class T>
ptrdiff_t 
count_r(
	register int (*rel_ptr)(const T*, const T*),
	const T& value,
	register const T* begin,
	register const T* end)
{
	register const T *temp = &value;
	register ptrdiff_t n = 0;

	while ( begin < end )
		if ( (*rel_ptr)(begin++, temp) == 0 )
			n++;

	return n;
}


template <class T>
void 
fill(
	register const T& value,
	register T* begin,
	register T* end)
{
	while ( begin < end )
		*begin++ = value;
}

template <class T>
void 
for_each(
	register void (*function)(T*),
	register T* begin,
	register T* end)
{
	while ( begin < end )
		(*function)(begin++);
}

template <class T>
void 
generate(
	void (*function)(ptrdiff_t, T*),
	register T* begin,
	register T* end)
{
	register T *index = begin;

	for ( ; begin < end ; begin++ )
		(*function)(begin - index, begin);
}

template <class T>
T* 
insert(
	const T &value,
	T* begin,
	T* end)
{
	begin = (T*)bin_loc(value, begin, end);
	copy(begin, end, begin + 1);
	*begin = value;
	return begin;
}

template <class T>
T* 
insert_r(
	int (*rel_ptr)(const T*, const T*),
	const T&	value,
	T*		begin,
	T*		end)
{
	begin = (T*)bin_loc_r(rel_ptr, value, begin, end);
	copy(begin, end, begin + 1);
	*begin = value;
	return begin;
}

template <class T>
const T* 
minimum(
	register const T* begin,
	register const T* end)
{
	register const T *index = begin;

	while ( ++begin < end )
		if ( *begin < *index )
			index = begin;

	return index;
}

template <class T>
void 
ins_sort(
	register T* begin,
	register T* end)
{
	if ( end - begin < 2 )		// size < 2
		return;
	
	T *r = (T*)minimum(begin, end);	// create a sentinel

	T temp = *begin;		// swap
	*begin = *r;
	*r = temp;

	begin++;			// there is no need to insert
					// the second element

	while ( ++begin < end ) {
		register T value = *begin;
		register T *index = begin;

		while ( value < *--index )
			*(index + 1) = *index;
		
		*(index + 1) = value;
	}
}

template <class T>
void 
ins_sort_r(
	register int (*rel_ptr)(const T*, const T*),
	register T* begin,
	T* end)
{
	register T *index = begin;

	while ( ++index < end ) {
		T value = *index;
		register T *temp = &value;
		register T *current = index;

		for ( ; begin < current && (*rel_ptr)(temp , current - 1) < 0 ; current-- )
			*current = *(current - 1);

		*current = value;
	}
}

template <class T>
#if !defined(__SUNPRO_CC)
static
#endif
void 
ins_sort_chunks(
	ptrdiff_t number,
	T* begin,
	T* end)
{
	for ( ; begin + number < end ; begin += number )
		ins_sort(begin, begin + number);

	ins_sort(begin, end);
}

template <class T>
#if !defined(__SUNPRO_CC)
static
#endif
void 
ins_sort_chunks_r(
	int (*rel_ptr)(const T*, const T*),
	ptrdiff_t number,
	T* begin,
	T* end)
{
	for ( ;  begin + number < end ; begin += number )
		ins_sort_r(rel_ptr, begin, begin + number);

	ins_sort_r(rel_ptr, begin, end);
}

template <class T>
T* 
set_inter(
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2,
	register T* result)
{
	while ( begin1 < end1 && begin2 < end2 )
		if ( *begin2 < *begin1 )
			begin2++;
		else if ( *begin1 < *begin2 )
			begin1++;
		else {
			*(result++) = *(begin1++);
			begin2++;
		}

	return result;
}

template <class T>
T* 
set_inter_r(
	register int (*rel_ptr)(const T*, const T*),
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2,
	register T* result)
{
	while ( begin1 < end1 && begin2 < end2 ) {
		register int c = (*rel_ptr)(begin2, begin1);

		if (c < 0)
			begin2++;
		else if (0 < c)
			begin1++;
		else {
			*(result++) = *(begin1++);
			begin2++;
		}
	}

	return result;
}

template <class T>
void 
merge(
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2,
	register T* result)
{
	while ( begin1 < end1 && begin2 < end2 )
		*result++ = (*begin2 < *begin1 ? *begin2++ : *begin1++);

	while ( begin1 < end1 )
		*result++ = *begin1++;

	while ( begin2 < end2 )
		*result++ = *begin2++;
}

template <class T>
void 
merge_r(
	register int (*rel_ptr)(const T*, const T*),
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2,
	register T* result)
{
	while ( begin1 < end1 && begin2 < end2 )
		*result++ = ((*rel_ptr)(begin2, begin1) < 0 ? *begin2++ : *begin1++);

	while ( begin1 < end1 )
		*result++ = *begin1++;

	while ( begin2 < end2 )
		*result++ = *begin2++;
}

template <class T>
T* 
merge_sort(
	T* begin,
	T* end,
	T* result)
{
	ptrdiff_t number = 8, length = end - begin;

	ins_sort_chunks(number, begin, end);

	for ( ; number < length ; number += number, end = begin, begin = result, result = end )
		merge_sort_step(number, begin, begin + length, result);

	return begin;
}

template <class T>
T* 
merge_sort_r(
	int (*rel_ptr)(const T*, const T*),
	T* begin,
	T* end,
	T* result)
{
	T* tmp;
	ptrdiff_t number = 8, length = end - begin;

	ins_sort_chunks_r(rel_ptr, number, begin, end);

	for ( ; number < length ; number += number, tmp = begin, begin = result, result = tmp )
		merge_sort_step_r(rel_ptr, number, begin, begin + length, result);

	return begin;
}

template <class T>
#if !defined(__SUNPRO_CC)
static
#endif
void 
merge_sort_step(
	ptrdiff_t number,
	T* begin,
	T* end,
	T* result)
{
	ptrdiff_t m = 2 * number;

	while (begin + m < end) {
		merge(begin, begin + number, begin + number, begin + m, result);
		begin += m;
		result += m;
	}

	if ( begin + number + 1 < end )
		merge(begin, begin + number, begin + number, end, result);
	else
		while ( begin < end )
			*result++ = *begin++;
}

template <class T>
#if !defined(__SUNPRO_CC)
static
#endif
void 
merge_sort_step_r(
	int (*rel_ptr)(const T*, const T*),
	ptrdiff_t number,
	T* begin,
	T* end,
	T* result)
{
	ptrdiff_t m = 2 * number;

	while ( begin + m < end ) {
		merge_r(rel_ptr, begin, begin + number, begin + number, begin + m, result);
		begin += m;
		result += m;
	}

	if ( begin + number < end )
		merge_r(rel_ptr, begin, begin + number, begin + number, end, result);
	else
		while ( begin < end )
			*result++ = *begin++;
}

template <class T>
const T* 
minimum_r(
	int (*rel_ptr)(const T*, const T*),
	const T* begin,
	const T* end)
{
	register const T *index = begin;

	while ( ++begin < end )
		if ( (*rel_ptr)(begin,index) < 0 )
			index = begin;

	return index;
}

template <class T>
const T* 
mismatch(
	const T* begin1,
	const T* end1,
	const T* begin2,
	const T* end2)
{
	register ptrdiff_t len = end1 - begin1 < end2 - begin2 ? end1 - begin1 : end2 - begin2;

	while ( 0 < len-- ) {
		if ( !(*begin1 == *begin2++) )
			return begin1;

		begin1++;
	}

	return 0;
}

template <class T>
const T* 
mismatch_r(
	register int (*rel_ptr)(const T*, const T*),
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2)
{
	register ptrdiff_t len = end1 - begin1 < end2 - begin2 ? end1 - begin1 : end2 - begin2;

	while ( 0 < len-- ) {
		if ( (*rel_ptr)(begin1, begin2++) != 0 )
			return begin1;

		begin1++;
	}

	return 0;
}


template <class T>
T* 
part(
	register const T &value,
	register T* begin,
	register T* end)
{
	for ( ; ; ) {
		for ( ; ; begin++ )
			if ( begin >= end )
				return end;
			else if ( !(*begin == value) )
				break;

		for ( ; ; )
			if ( begin >= --end )
				return end;
			else if ( *end == value )
				break;

		{
			register T temp = *begin;
			*begin++ = *end;
			*end = temp;
		}
	}
}

template <class T>
T* 
part_p(
	register int (*pred_ptr)(const T*),
	register T* begin,
	register T* end)
{
	for ( ; ; ) {
		for ( ; ; begin++ )
			if ( begin >= end )
				return end;
			else if ( !(*pred_ptr)(begin) )
				break;

		for ( ; ; )
			if ( begin >= --end )
				return end;
			else if ( (*pred_ptr)(end) )
				break;

		{
			register T temp = *begin;
			*begin++ = *end;
			*end = temp;
		}
	}
}

template <class T>
T* 
part_r(
	register int (*rel_ptr)(const T*, const T*),
	const T &value,
	register T* begin,
	register T* end)
{
	register const T *temp = &value;

	for ( ; ; ) {
		for ( ; ; begin++ )
			if ( begin >= end )
				return end;
			else if ( (*rel_ptr)(begin, temp) != 0 )
				break;

		for ( ; ; )
			if ( begin >= --end )
				return end;
			else if ( (*rel_ptr)(end, temp) == 0 )
				break;

		{
			register T temp = *begin;
			*begin++ = *end;
			*end = temp;
		}
	}
}

template <class T>
T* 
part_c(
	register const T& value,
	const T* begin,
	register const T* end,
	register T* result)
{
	register T *last = result + (end - begin);

	for ( ; begin < end ; begin++ )
		if ( *begin == value )
			*(result++) = *begin;
		else
			*(--last) = *begin;

	return last;
}

template <class T>
T* 
part_pc(
	register int (*pred_ptr)(const T*),
	register const T* begin,
        register const T* end,
	register T* result)
{
	register T *last = result + (end - begin);

	for ( ; begin < end ; begin++ )
		if ( (*pred_ptr)(begin) )
			*(result++) = *begin;
		else
			*--last = *begin;

	return last;
}

template <class T>
T* 
part_rc(
	register int (*rel_ptr)(const T*, const T*),
	const T& value,
        register const T* begin,
	register const T* end,
	register T* result)
{
	register T *last = result + (end - begin);
	register const T *temp = &value;

	for ( ; begin < end ; begin++ )
		if ( (*rel_ptr)(begin, temp) == 0 )
			*(result++) = *begin;
		else
			*(--last) = *begin;

	return last;
}

template <class T>
const T* 
pos(
	register const T& value,
	register const T* begin,
	register const T* end)
{
	while ( begin < end )
		if ( *begin++ == value )
			return begin - 1;

	return 0;
}

template <class T>
const T* 
pos_p(
	register int (*pred_ptr)(const T*),
	register const T* begin,
	register const T* end)
{
	while ( begin < end )
		if ( (*pred_ptr)(begin++) )
			return begin - 1;

	return 0;
}

template <class T>
const T* 
pos_r(
	register int (*rel_ptr)(const T*, const T*),
	const T &value,
	register const T* begin,
	register const T* end)
{
	register const T *temp = &value;

	while ( begin < end )
		if ( (*rel_ptr)(begin++, temp) == 0 )
			return begin - 1;

	return 0;
}

template <class T>
const T* 
random(
	const T* begin,
	const T* end)
{
	if ( begin < end )
		return begin + (ptrdiff_t)(drand48() * (end - begin));
	else
		return 0;
}

template <class T>
T* 
rem(
	register const T& value,
	register T* begin,
	register T* end)
{
	for ( ; ; ) {
		for ( ; ; begin++ )
			if ( begin >= end )
				return end;
			else if ( *begin == value )
				break;

		for ( ; ; )
			if ( begin >= --end )
				return end;
			else if ( !(*end == value) )
				break;

		*begin++ = *end;
	}
}

template <class T>
T* 
rem_p(
	register int (*pred_ptr)(const T*),
	register T* begin,
	register T* end)
{
	for ( ; ; ) {
		for ( ; ; begin++ )
			if ( begin >= end )
				return end;
			else if ( (*pred_ptr)(begin) )
				break;

		for ( ; ; )
			if ( begin >= --end )
				return end;
			else if ( !(*pred_ptr)(end) )
				break;

		*begin++ = *end;
	}
}

template <class T>
T* 
rem_r(
	register int (*rel_ptr)(const T*, const T*),
	const T& value,
	register T* begin,
	register T* end)
{
	register const T *temp = &value;

	for ( ; ; ) {
		for ( ; ; begin++ )
			if ( begin >= end )
				return end;
			else if ( (*rel_ptr)(begin, temp) == 0 )
				break;

		for ( ; ; )
			if ( begin >= --end )
				return end;
			else if ( (*rel_ptr)(end, temp) != 0 )
				break;

		*begin++ = *end;
	}
}

template <class T>
T* 
rem_c(
	register const T &value,
	register const T* begin,
	register const T* end,
	register T* result)
{
	for ( ; begin < end ; begin++ )
		if ( !(*begin == value) )
			*result++ = *begin;

	return result;
}

template <class T>
T* 
rem_pc(
	register int (*pred_ptr)(const T*),
	register const T* begin,
	register const T* end,
	register T* result)
{
	for ( ; begin < end ; begin++ )
		if ( !(*pred_ptr)(begin) )
			*result++ = *begin;

	return result;
}

template <class T>
T* 
rem_rc(
	register int (*rel_ptr)(const T*, const T*),
	const T& value,
	register const T* begin,
	register const T* end,
	register T* result)
{
	register const T *temp = &value;

	for ( ; begin < end ; begin++ )
		if ( (*rel_ptr)(begin, temp) != 0 )
			*result++ = *begin;

	return result;
}

template <class T>
T* 
rem_dup(
	register T* begin,
	register T* end)
{
	register T *index = begin;
	register T *m;

	for( ; index < end ; index++ )
		if ( pos(*index, begin, index) != 0 )
			break;

	m = index;

	while ( ++index < end )
		if ( pos(*index, begin, m) == 0 )
			*m++ = *index;

	return m;
}

template <class T>
T* 
rem_dup_r(
	int (*rel_ptr)(const T*, const T*),
	register T* begin,
	register T* end)
{
	register T *index = begin;
	register T *m;

	for( ; index < end ; index++ )
		if ( pos_r(rel_ptr, *index, begin, index) != 0 )
			break;

	m = index;

	while ( ++index < end )
		if ( pos_r(rel_ptr, *index, begin, m) == 0 )
			*m++ = *index;

	return m;
}

template <class T>
T* 
rem_dup_c(
	register const T* begin,
	register const T* end,
	register T* result)
{
	register T *m = result;

	for ( ; begin < end ; begin++ )
		if ( !pos(*begin, result, m) )
			*m++ = *begin;

	return m;
}

template <class T>
T* 
rem_dup_rc(
	int (*rel_ptr)(const T*, const T*),
	register const T* begin,
	register const T* end,
	register T* result)
{
	register T *m = result;

	for ( ; begin < end ; begin++ )
		if ( pos_r(rel_ptr, *begin, result, m) == 0 )
			*m++ = *begin;

	return m;
}

template <class T>
void 
reverse(
	register T* begin,
	register T* end)
{
	while ( begin < --end ) {
		register T temp = *begin;
		*begin++ = *end;
		*end = temp;
	}
}

template <class T>
void 
reverse_c(
	register const T* begin,
	register const T* end,
	register T* result)
{
	while ( begin < end-- )
		*result++ = *end;
}

template <class T>
const T* 
rt_pos(
	register const T& value,
	register const T* begin,
	register const T* end)
{
	while ( begin < end )
		if ( *--end == value )
			return end;

	return 0;
}

template <class T>
const T* 
rt_pos_p(
	register int (*pred_ptr)(const T*),
	register const T* begin,
	register const T* end)
{
	while ( begin < end )
		if ( (*pred_ptr)(--end) )
			return end;

	return 0;
}

template <class T>
const T* 
rt_pos_r(
	register int (*rel_ptr)(const T*, const T*),
	const T& value,
	register const T* begin,
	register const T* end)
{
	register const T *temp = &value;

	while ( begin < end )
		if ( (*rel_ptr)(--end, temp) == 0 )
			return end;

	return 0;
}

template <class T>
void 
rotate(
	ptrdiff_t number,
	T* begin,
	T* end)
{
	if ( begin >= end )
		return;

	number %= end - begin;

	if ( number == 0 )
		return;

	if ( number < 0 )
		number += (end - begin);

	reverse(begin, end);
	reverse(begin, begin + number);
	reverse(begin + number, end);
}

template <class T>
void 
rotate_c(
	ptrdiff_t number,
	const T* begin,
	const T* end,
	T* result)
{
	if ( begin >= end )
		return;

	number %= end - begin;

	if ( number == 0 ) {
		copy((T*)begin, (T*)end, result);
		return;
	}

	if ( number < 0 )
		number += (end - begin);

	copy((T*)end - number, (T*)end, result);
	copy((T*)begin, (T*)end - number, result + number);
}

template <class T>
const T* 
search(
	register const T* begin1,
	const T* end1,
	register const T* begin2,
	const T* end2)
{
	register ptrdiff_t d1, d2, k;

	if ( begin2 >= end2 )
		return begin1;

	d1 = end1 - begin1;
	d2 = end2 - begin2;

	if ( d1 < d2 )
		return 0;

	k = 0;

	while ( k < d2 ) {
		if ( begin1[k] == begin2[k] )
			k++;
		else if ( d1 == d2 )
			return 0;
		else {
			k = 0;
			begin1++;
			d1--;
		}
	}

	return begin1;
}

template <class T>
const T* 
search_r(
	register int (*rel_ptr)(const T*, const T*),
	register const T* begin1,
	const T* end1,
	register const T* begin2,
	const T* end2)
{
	register ptrdiff_t d1, d2, k;

	if ( begin2 >= end2 )
		return begin1;

	d1 = end1 - begin1;
	d2 = end2 - begin2;

	if ( d1 < d2 )
		return 0;

	k = 0;

	while ( k < d2 ) {
		if ( (*rel_ptr)(begin1 + k, begin2 + k) == 0 )
			k++;
		else if ( d1 == d2 )
			return 0;
		else {
			k = 0;
			begin1++;
			d1--;
		}
	}
	return begin1;
}

template <class T>
void 
select(
	ptrdiff_t nth,
	T* begin,
	T* end)
{
	if ( begin >= end || nth <= 0 || end - begin < nth )
		return;

	for ( ; ; ) {
		if ( end - begin < 6 ) {
			ins_sort(begin, end);
			return;
		}
		else if ( nth < 4 ) {
			while (nth--) {
				register T *r = (T*)minimum(begin, end);
				register T temp = *begin;
				*begin = *r;
				*r = temp;
			}
			return;
		}
		else {
			T *index = ordered_part_ATTLC(begin, end);

			if ( index - begin >= nth )
				end = index;
			else {
				nth -= index - begin;
				begin = index;
			}
		}
	}
}

template <class T>
void 
select_r(
	int (*rel_ptr)(const T*, const T*),
	ptrdiff_t nth,
	T* begin,
	T* end)
{
	if ( begin >= end || nth <= 0 || end - begin < nth )
		return;

	for ( ; ; ) {
		if ( end - begin < 6 ) {
			ins_sort_r(rel_ptr, begin, end);
			return;
		}
		else if ( nth < 4 ) {
			while ( nth-- ) {
				register T *r = (T*)minimum_r(rel_ptr, begin, end);
				register T temp = *begin;
				*begin++ = *r;
				*r = temp;
			}
			return;
		}
		else {
			T *index = ordered_part_r_ATTLC(rel_ptr, begin, end);

			if ( index - begin >= nth )
				end = index;
			else {
				nth -= index - begin;
				begin = index;
			}
		}
	}
}

template <class T>
T* 
set_diff(
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2,
	register T* result)
{
	while ( begin1 < end1 && begin2 < end2 )
		if ( *begin1 < *begin2 )
			*result++ = *begin1++;
		else if ( !(*begin2++ < *begin1) )
			begin1++;

	while ( begin1 < end1 )
		*result++ = *begin1++;

	return result;
}

template <class T>
T* 
set_diff_r(
	register int (*rel_ptr)(const T*, const T*),
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2,
	register T* result)
{
	while ( begin1 < end1 && begin2 < end2 ) {
		register int c = (*rel_ptr)(begin2, begin1);

		if ( 0 < c )
			*result++ = *begin1++;
		else {
			if ( c == 0 )
				begin1++;

			begin2++;
		}
	}

	while ( begin1 < end1 )
		*result++ = *begin1++;

	return result;
}

template <class T>
T* 
set_insert(
	const T& value,
	T* begin,
	T* end)
{
	T *index = (T*)bin_loc(value, begin, end);

	if ( begin < index && !(*(index - 1) < value) )
		return 0;
	else {
		copy(index, end, index + 1);
		*index = value;
		return index;
	}
}

template <class T>
T* 
set_insert_r(
	int (*rel_ptr)(const T*, const T*),
	const T &value,
	T* begin,
	T* end)
{
	T *index = (T*)bin_loc_r(rel_ptr, value, begin, end);

	if ( begin < index && !((*rel_ptr)(index - 1, &value) < 0) )
		return 0;
	else {
		copy(index, end, index + 1);
		*index = value;
		return index;
	}
}

template <class T>
T* 
set_remove(
	const T& value,
	T* begin,
	T* end)
{
	T *index = (T*)bin_loc(value, begin, end);

	if ( begin < index && !(*(index - 1) < value) ) {
		copy(index, end, index - 1);
		return end-1;
	}
	else
		return end;
}

template <class T>
T* 
set_remove_r(
	int (*rel_ptr)(const T*, const T*),
	const T& value,
	T* begin,
	T* end)
{
	T *index = (T*)bin_loc_r(rel_ptr, value, begin, end);

	if ( begin < index && !((*rel_ptr)(index - 1, &value) < 0) ) {
		copy(index, end, index - 1);
		return end-1;
	}
	else
		return end;
}

template <class T>
T* 
set_union(
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2,
	register T* result)
{
	while ( begin1 < end1 && begin2 < end2 ) {
		if ( *begin2 < *begin1 )
			*result++ = *begin2++;
		else {
			if ( *begin1 < *begin2 )
				*result++ = *begin1++;
			else {
				*result++ = *begin2++;
				begin1++;
			}
		}
	}

	while ( begin1 < end1 )
		*result++ = *begin1++;

	while ( begin2 < end2 )
		*result++ = *begin2++;

	return result;
}

template <class T>
T*
set_union_r(
	register int (*rel_ptr)(const T*, const T*),
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2,
	register T* result)
{
	while ( begin1 < end1 && begin2 < end2 ) {
		register int c = (*rel_ptr)(begin2, begin1);

		if ( c < 0 )
			*result++ = *begin2++;
		else {
			*result++ = *begin1++;
			if ( c == 0 )
				begin2++;
		}
	}

	while ( begin1 < end1 )
		*result++ = *begin1++;

	while ( begin2 < end2 )
		*result++ = *begin2++;

	return result;
}

template <class T>
void 
shuffle(
	register T* begin,
	register T* end)
{
	register T *index = begin + 1;

	while ( index < end ) {
		register T *r = (T*)random(begin, index + 1);
		register T temp = *index;
		*index++ = *r;
		*r = temp;
	}
}

template <class T>
void 
shuffle_c(
	register const T* begin,
	register const T* end,
	register T* result)
{
	register T *result_end = result;

	while ( begin < end ) {
		register T *r = (T*)random(result, result_end + 1);
		*result_end++ = *r;
		*r = *begin++;
	}
}

template <class T>
#if !defined(__SUNPRO_CC)
static
#endif
T*
ordered_part_ATTLC(
	register T *begin,
	register T *end)
{
	T *old_begin = begin;
	register T value = *random(begin, end);

	begin--;

	for ( ; ; ) {
		while ( *++begin < value );

		while ( value < *--end );
		
		if ( begin < end ) {
			register T temp = *begin;
			*begin = *end;
			*end = temp;
		}
		else
			return (begin == old_begin) ? begin + 1 : begin;
	}
}

template <class T>
#if !defined(__SUNPRO_CC)
static
#endif
void 
quicksort_loop_ATTLC(
	register T *begin,
	register T *end)
{
	while ( 10 < end - begin ) {
		register T *index = ordered_part_ATTLC(begin, end);

		if ( end - index < index - begin ) {
			quicksort_loop_ATTLC(index, end);
			end = index;
		}
		else {
			quicksort_loop_ATTLC(begin, index);
			begin = index;
		}
	}
}

template <class T>
void 
sort(
	T* begin,
	T* end)
{
	quicksort_loop_ATTLC(begin, end);
	ins_sort(begin, end);
}

template <class T>
#if !defined(__SUNPRO_CC)
static
#endif
T* 
ordered_part_r_ATTLC(
	register int (*rel_ptr)(const T*, const T*),
        register T* begin, register T* end)
{
	T* old_begin = begin;
	T value = *random(begin, end);
	register T *temp = &value;

	begin--;

	for ( ; ; ) {
		while ( (*rel_ptr)(++begin, temp) < 0 );

		while ( (*rel_ptr)(temp, --end) < 0 );

		if ( begin < end ) {
			register T temp = *begin;
			*begin = *end;
			*end = temp;
		}
		else
			return (begin==old_begin) ? begin + 1 : begin;
	}
}

template <class T>
#if !defined(__SUNPRO_CC)
static
#endif
void 
quicksort_loop_r_ATTLC(
	int (*rel_ptr)(const T*, const T*),
	T* begin,
	T* end)
{
	while ( 10 < end - begin ) {
		T *index = ordered_part_r_ATTLC(rel_ptr, begin, end);

		if ( end - index < index - begin ) {
			quicksort_loop_r_ATTLC(rel_ptr, index, end);
			end = index;
		}
		else {
			quicksort_loop_r_ATTLC(rel_ptr, begin, index);
			begin = index;
		}
	}
}

template <class T>
void 
sort_r(
	int (*rel_ptr)(const T*, const T*),
	T* begin,
	T* end)
{
	quicksort_loop_r_ATTLC(rel_ptr, begin, end);
	ins_sort_r(rel_ptr, begin, end);
}

template <class T>
T* 
part_s(
	const T& value,
	T* begin, T* end)
{
	if ( end - begin > 1 ) {
		T *middle = begin + ((end - begin) >> 1);
		T *first_half = part_s(value, begin, middle);
		T *second_half = part_s(value, middle, end);

		rotate(first_half - middle, first_half, second_half);
		return first_half + (second_half - middle);

	}
	else if ( begin < end )
		return *begin == value ? begin + 1 : begin;
	else
		return end;
}

template <class T>
T* 
part_ps(
	int (*pred_ptr)(const T*),
	T* begin,
	T* end)
{
	if ( end - begin > 1 ) {
		T *middle = begin + ((end - begin) >> 1);
		T *first_half = part_ps(pred_ptr, begin, middle);
		T *second_half = part_ps(pred_ptr, middle, end);

		rotate(first_half - middle, first_half, second_half);
		return first_half + (second_half - middle);

	}
	else if ( begin < end )
		return (*pred_ptr)(begin) ? begin + 1 : begin;
	else
		return end;
}

template <class T>
T* 
part_rs(
	int (*rel_ptr)(const T*, const T*),
	const T &value,
	T* begin,
	T* end)
{
	if ( end - begin > 1 ) {
		T *middle = begin + ((end - begin) >> 1);
		T *first_half = part_rs(rel_ptr, value, begin, middle);
		T *second_half = part_rs(rel_ptr, value, middle, end);

		rotate(first_half - middle, first_half, second_half);
		return first_half + (second_half - middle);

	}
	else if ( begin < end )
		return ((*rel_ptr)(begin, &value) == 0) ? begin + 1 : begin;
	else
		return end;
}

template <class T>
T* 
part_sc(
	const T& value,
	const T* begin,
	const T* end,
	T* result)
{
	T *m = part_c(value, begin, end, result);
	reverse(m, result + (end - begin));
	return m;
}

template <class T>
T* 
part_psc(
	int (*pred_ptr)(const T*), 
	const T* begin, 
	const T* end,
	T* result)
{
	T *m = part_pc(pred_ptr, begin, end, result);
	reverse(m, result + (end - begin));
	return m;
}

template <class T>
T* 
part_rsc(
	int (*rel_ptr)(const T*, const T*),
	const T& value,
	const T* begin,
	const T* end,
	T* result)
{
	T *m = part_rc(rel_ptr, value, begin, end, result);
	reverse(m, result + (end - begin));
	return m;
}

template <class T>
T* 
rem_s(
	register const T& value,
	register T* begin,
	register T* end)
{
	register T *m;

	while ( begin < end && !(*begin == value) )
		begin++;

	if ( begin >= end )
		return end;

	m = begin;

	while ( ++begin < end )
		if ( !(*begin == value) )
			*m++ = *begin;

	return m;
}

template <class T>
T* 
rem_ps(
	register int (*pred_ptr)(const T*),
	register T* begin,
	register T* end)
{
	register T *m;

	while ( begin < end && !(*pred_ptr)(begin) )
		begin++;

	if ( begin >= end )
		return end;

	m = begin;

	while ( ++begin < end )
		if ( !(*pred_ptr)(begin) )
			*m++ = *begin;

	return m;
}

template <class T>
T* 
rem_rs(
	register int (*rel_ptr)(const T*, const T*),
	const T &value,
	register T* begin,
	register T* end)
{
	register const T *temp = &value;
	register T *m;

	while ( begin < end && (*rel_ptr)(begin, temp) != 0 )
		begin++;

	if ( begin >= end )
		return end;

	m = begin;

	while ( ++begin < end )
		if ( (*rel_ptr)(begin, temp) != 0 )
			*m++ = *begin;

	return m;
}

template <class T>
T* 
rem_sc(
	const T& value,
	const T* begin,
	const T* end,
	T* result)
{
	return rem_c(value, begin, end, result);
}

template <class T>
T* 
rem_psc(
	int (*pred_ptr)(const T*),
	const T* begin,
	const T* end,
	T* result)
{
	return rem_pc(pred_ptr, begin, end, result);
}

template <class T>
T* 
rem_rsc(
	int (*rel_ptr)(const T*, const T*),
	const T& value,
	const T* begin,
	const T* end,
	T* result)
{
	return rem_rc(rel_ptr, value, begin, end, result);
}

template <class T>
void 
sort_s(
	register T* begin,
	register T* end)
{
	T *index = new T[end-begin];

	if ( index == 0 ) {
		ins_sort(begin, end);
		return;
	}

	if ( merge_sort(begin, end, index) == index ) {
		T *i = index;

		while ( begin < end )
			*begin++ = *i++;
	}

	delete [/*end-begin*/]index;
}

template <class T>
void 
sort_rs(
	int (*rel_ptr)(const T*, const T*),
	T* begin,
	T* end)
{
	T* index = new T[end-begin];

	if ( index == 0 ) {
		ins_sort_r(rel_ptr, begin, end);
		return;
	}

	if ( merge_sort_r(rel_ptr, begin, end, index) == index ) {
		T *i = index;

		while ( begin < end )
			*begin++ = *i++;
	}

	delete [/*end-begin*/]index;
}

template <class T>
void 
subs(
	register const T &value,
	register T new_value,
	register T* begin,
	register T* end)
{
	for ( ; begin < end; begin++ )
		if ( *begin == value )
			*begin = new_value;

}

template <class T>
void 
subs_r(
	register int (*rel_ptr)(const T*, const T*),
	const T &value,
	register T new_value,
	register T* begin,
	register T* end)
{
	register const T *temp = &value;

	for ( ; begin < end; begin++ )
		if ( (*rel_ptr)(begin, temp) == 0 )
			*begin = new_value;

}

template <class T>
void 
subs_c(
	register const T& value,
	register T new_value,
	register const T* begin,
	register const T* end,
	register T* result)
{
	for ( ; begin < end; begin++ )
		*result++ = (*begin == value ? new_value : *begin);
}

template <class T>
void 
subs_rc(
	register int (*rel_ptr)(const T*, const T*),
	const T &value,
	register T new_value,
	register const T* begin,
	register const T* end,
	register T* result)
{
	register const T *temp = &value;

	for ( ; begin < end; begin++ )
		*result++ = ((*rel_ptr)(begin, temp) == 0 ? new_value : *begin);
}

template <class T>
T* 
set_sdiff(
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2,
	register T* result)
{
	while ( begin1 < end1 && begin2 < end2 )
		if ( *begin1 < *begin2 )
			*result++ = *begin1++;
		else if ( *begin2 < *begin1 )
			*result++ = *begin2++;
		else {
			begin1++;
			begin2++;
		}

	while ( begin1 < end1 )
		*result++ = *begin1++;

	while ( begin2 < end2 )
		*result++ = *begin2++;

	return result;
}

template <class T>
T* 
set_sdiff_r(
	register int (*rel_ptr)(const T*, const T*),
	register const T* begin1,
	register const T* end1,
	register const T* begin2,
	register const T* end2,
	register T* result)
{
	while ( begin1 < end1 && begin2 < end2 ) {
		register int c = (*rel_ptr)(begin2, begin1);

		if ( 0 < c )
			*result++ = *begin1++;
		else if ( c < 0 )
			*result++ = *begin2++;
		else
			begin1++, begin2++;
	}

	while ( begin1 < end1 )
		*result++ = *begin1++;

	while ( begin2 < end2 )
		*result++ = *begin2++;

	return result;
}

template <class T>
T* 
unique(
	register T* begin,
	register T* end)
{
	register T *m;

	if ( begin >= end )
		return begin;

	while ( ++begin < end )
		if ( *(begin - 1) == *begin )
			break;
	
	if ( begin == end )
		return begin;

	m = begin - 1;

	while ( ++begin < end )
		if ( !(*m == *begin) )
			*++m = *begin;

	return m + 1;
}

template <class T>
T* 
unique_r(
	register int (*rel_ptr)(const T*, const T*),
	register T* begin,
	register T* end)
{
	register T *m;

	if ( begin >= end )
		return begin;

	while ( ++begin < end )
		if ( !(*rel_ptr)(begin - 1, begin) )
			break;

	if ( begin == end )
		return begin;

	m = begin - 1;

	while ( ++begin < end )
		if ( (*rel_ptr)(m, begin) )
			*++m = *begin;

	return m + 1;
}

template <class T>
T* 
unique_c(
	register const T* begin,
	register const T* end,
	register T* result)
{
	if ( begin >= end )
		return result;

	*result = *begin;

	while ( ++begin < end )
		if ( !(*result == *begin) )
			*++result = *begin;

	return result + 1;
}

template <class T>
T* 
unique_rc(
	register int (*rel_ptr)(const T*, const T*),
	register const T* begin,
	register const T* end,
	register T* result)
{
	if ( begin >= end )
		return result;

	*result = *begin;

	while ( ++begin < end )
		if ( (*rel_ptr)(result, begin) )
			*++result = *begin;

	return result + 1;
}

#endif