This is the mail archive of the gcc-prs@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

c++/4253: gcc-3.0.1 problems with -frepo



>Number:         4253
>Category:       c++
>Synopsis:       gcc-3.0.1 problems with -frepo
>Confidential:   no
>Severity:       serious
>Priority:       low
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Thu Sep 06 16:56:00 PDT 2001
>Closed-Date:
>Last-Modified:
>Originator:     Juergen Heinzl
>Release:        3.0.1
>Organization:
>Environment:
System: Linux monocerus.demon.co.uk 2.2.19 #1 Mon Mar 26 21:18:17 BST 2001 i686 unknown
Architecture: i686

	
host: i686-pc-linux-gnu
build: i686-pc-linux-gnu
target: i686-pc-linux-gnu
configured with: ../gcc-3.0.1/configure --prefix=/usr --infodir=/usr/share/info --mandir=/usr/share/man --enable-threads --enable-languages=c,c++ --disable-nls
binutils: 2.11.2

>Description:
	Related to c++/3729 I think.

	A simple test programme does (not) compile with -frepo. It actually
	compiles and links when using --save-temps (nah, no kidding).

>How-To-Repeat:
        Source as in c++/3729
	---------------------
#include <map>

int
main()
{
  std::map<int, int> theMap;

  return 0;
}

	1st run using --save-temps
	--------------------------
Script started on Fri Sep  7 00:43:21 2001
$ cp /tmp/try.cc .
$ g++ -c --save-temps -frepo try.cc
$ g++ --save-temps -frepo try.o
collect: recompiling try.ii
collect: relinking
$ 
Script done on Fri Sep  7 00:43:48 2001
	
	2nd run without using --save-temps
	----------------------------------
Script started on Fri Sep  7 00:43:58 2001
$ g++ -c -frepo try.cc
$ g++ -frepo try.o
collect: recompiling try.cc
In file included from /usr/include/g++-v3/bits/std_cstring.h:37,
                 from /usr/include/g++-v3/bits/stl_algobase.h:71,
                 from /usr/include/g++-v3/bits/stl_tree.h:85,
                 from /usr/include/g++-v3/bits/std_map.h:62,
                 from /usr/include/g++-v3/map:31,
                 from try.cc:1:
/usr/include/g++-v3/bits/std_cstddef.h:38:25: stddef.h: No such file or directory
In file included from /usr/include/g++-v3/bits/std_cstring.h:37,
                 from /usr/include/g++-v3/bits/stl_algobase.h:71,
                 from /usr/include/g++-v3/bits/stl_tree.h:85,
                 from /usr/include/g++-v3/bits/std_map.h:62,
                 from /usr/include/g++-v3/map:31,
                 from try.cc:1:
/usr/include/g++-v3/bits/std_cstddef.h:42: `ptrdiff_t' not declared
/usr/include/g++-v3/bits/std_cstddef.h:43: `size_t' not declared
In file included from /usr/include/g++-v3/bits/std_climits.h:38,
                 from /usr/include/g++-v3/bits/stl_algobase.h:72,
                 from /usr/include/g++-v3/bits/stl_tree.h:85,
                 from /usr/include/g++-v3/bits/std_map.h:62,
                 from /usr/include/g++-v3/map:31,
                 from try.cc:1:
/usr/include/limits.h:124:26: No include path in which to find limits.h
In file included from /usr/include/g++-v3/bits/stl_algobase.h:75,
                 from /usr/include/g++-v3/bits/stl_tree.h:85,
                 from /usr/include/g++-v3/bits/std_map.h:62,
                 from /usr/include/g++-v3/map:31,
                 from try.cc:1:
/usr/include/g++-v3/new:76: `size_t' undeclared in namespace `std'
/usr/include/g++-v3/new:76: declaration of `operator new' as non-function
/usr/include/g++-v3/new:76: invalid declarator
/usr/include/g++-v3/new:77: `size_t' undeclared in namespace `std'
/usr/include/g++-v3/new:77: declaration of `operator new []' as non-function
/usr/include/g++-v3/new:77: invalid declarator
/usr/include/g++-v3/new:80: `size_t' undeclared in namespace `std'
/usr/include/g++-v3/new:80: parse error before `::' token
/usr/include/g++-v3/new:80: `operator new' takes type `size_t' (`unsigned int') 
   as first parameter
/usr/include/g++-v3/new:81: `size_t' undeclared in namespace `std'
/usr/include/g++-v3/new:81: parse error before `::' token
/usr/include/g++-v3/new:81: `operator new' takes type `size_t' (`unsigned int') 
   as first parameter
/usr/include/g++-v3/new:86: `size_t' undeclared in namespace `std'
/usr/include/g++-v3/new:86: parse error before `*' token
/usr/include/g++-v3/new:86: `operator new' takes type `size_t' (`unsigned int') 
   as first parameter
/usr/include/g++-v3/new: In function `void* operator new(unsigned int, ...)':
/usr/include/g++-v3/new:86: `place' undeclared (first use this function)
/usr/include/g++-v3/new:86: (Each undeclared identifier is reported only once 
   for each function it appears in.)
/usr/include/g++-v3/new: At global scope:
/usr/include/g++-v3/new:87: `size_t' undeclared in namespace `std'
/usr/include/g++-v3/new:87: parse error before `*' token
/usr/include/g++-v3/new:87: `operator new' takes type `size_t' (`unsigned int') 
   as first parameter
In file included from /usr/include/g++-v3/bits/fpos.h:39,
                 from /usr/include/g++-v3/bits/std_iosfwd.h:41,
                 from /usr/include/g++-v3/bits/stl_algobase.h:77,
                 from /usr/include/g++-v3/bits/stl_tree.h:85,
                 from /usr/include/g++-v3/bits/std_map.h:62,
                 from /usr/include/g++-v3/map:31,
                 from try.cc:1:
/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++io.h:43: syntax error before `;' 
   token
/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++io.h:45: syntax error before `;' 
   token
In file included from /usr/include/g++-v3/bits/stl_algobase.h:78,
                 from /usr/include/g++-v3/bits/stl_tree.h:85,
                 from /usr/include/g++-v3/bits/std_map.h:62,
                 from /usr/include/g++-v3/map:31,
                 from try.cc:1:
/usr/include/g++-v3/bits/stl_iterator_base_types.h:128: parse error before `,' 
   token
/usr/include/g++-v3/bits/stl_iterator_base_types.h:131: template declaration of 
   `typedef _Tp std::value_type'
/usr/include/g++-v3/bits/stl_iterator_base_types.h:131: confused by earlier errors, bailing out
try.o: In function `std::_Rb_tree<int, std::pair<int const, int>, std::_Select1st<std::pair<int const, int> >, std::less<int>, std::allocator<std::pair<int const, int> > >::clear()':
try.o(.gnu.linkonce.t._ZNSt8_Rb_treeIiSt4pairIKiiESt10_Select1stIS2_ESt4lessIiESaIS2_EE5clearEv+0x26): undefined reference to `std::_Rb_tree<int, std::pair<int const, int>, std::_Select1st<std::pair<int const, int> >, std::less<int>, std::allocator<std::pair<int const, int> > >::_M_erase(std::_Rb_tree_node<std::pair<int const, int> >*)'
collect2: ld returned 1 exit status
$ 
Script done on Fri Sep  7 00:44:11 2001

	cpp output
	----------
# 1 "try.cc"
# 1 "/usr/include/g++-v3/map" 1 3
# 31 "/usr/include/g++-v3/map" 3
# 1 "/usr/include/g++-v3/bits/std_map.h" 1 3
# 60 "/usr/include/g++-v3/bits/std_map.h" 3


# 1 "/usr/include/g++-v3/bits/stl_tree.h" 1 3
# 85 "/usr/include/g++-v3/bits/stl_tree.h" 3
# 1 "/usr/include/g++-v3/bits/stl_algobase.h" 1 3
# 64 "/usr/include/g++-v3/bits/stl_algobase.h" 3
# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 1 3
# 34 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 3
# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/os_defines.h" 1 3
# 37 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/os_defines.h" 3
# 1 "/usr/include/features.h" 1 3
# 283 "/usr/include/features.h" 3
# 1 "/usr/include/sys/cdefs.h" 1 3
# 284 "/usr/include/features.h" 2 3
# 312 "/usr/include/features.h" 3
# 1 "/usr/include/gnu/stubs.h" 1 3
# 313 "/usr/include/features.h" 2 3
# 38 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/os_defines.h" 2 3
# 35 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 2 3

# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/limits.h" 1 3
# 37 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 2 3
# 65 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3

# 1 "/usr/include/g++-v3/bits/stl_pair.h" 1 3
# 64 "/usr/include/g++-v3/bits/stl_pair.h" 3
namespace std
{


template <class _T1, class _T2>
struct pair {
  typedef _T1 first_type;
  typedef _T2 second_type;

  _T1 first;
  _T2 second;




  pair() : first(), second() {}




  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) {}
};


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);
}
# 139 "/usr/include/g++-v3/bits/stl_pair.h" 3
template <class _T1, class _T2>


inline pair<_T1, _T2> make_pair(_T1 __x, _T2 __y)



{
  return pair<_T1, _T2>(__x, __y);
}

}
# 67 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3


# 1 "/usr/include/g++-v3/bits/type_traits.h" 1 3
# 48 "/usr/include/g++-v3/bits/type_traits.h" 3

# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 1 3
# 50 "/usr/include/g++-v3/bits/type_traits.h" 2 3
# 86 "/usr/include/g++-v3/bits/type_traits.h" 3
template <bool _Truth> struct _Bool {};
typedef _Bool<true> __true_type;
typedef _Bool<false> __false_type;

template <class _Tp>
struct __type_traits {
   typedef __true_type this_dummy_member_must_be_first;
# 110 "/usr/include/g++-v3/bits/type_traits.h" 3
   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<bool> {
   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<> struct __type_traits<char> {
   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<> struct __type_traits<signed char> {
   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<> struct __type_traits<unsigned char> {
   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<> struct __type_traits<wchar_t> {
   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<> struct __type_traits<short> {
   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<> struct __type_traits<unsigned short> {
   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<> struct __type_traits<int> {
   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<> struct __type_traits<unsigned int> {
   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<> struct __type_traits<long> {
   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<> struct __type_traits<unsigned long> {
   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<> struct __type_traits<long long> {
   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<> struct __type_traits<unsigned long long> {
   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<> struct __type_traits<float> {
   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<> struct __type_traits<double> {
   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<> struct __type_traits<long double> {
   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 __type_traits<_Tp*> {
   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 _Is_integer {
  typedef __false_type _Integral;
};

template<> struct _Is_integer<bool> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<char> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<signed char> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<unsigned char> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<wchar_t> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<short> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<unsigned short> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<int> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<unsigned int> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<long> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<unsigned long> {
  typedef __true_type _Integral;
};



template<> struct _Is_integer<long long> {
  typedef __true_type _Integral;
};

template<> struct _Is_integer<unsigned long long> {
  typedef __true_type _Integral;
};



template<typename _Tp> struct _Is_normal_iterator {
   typedef __false_type _Normal;
};


namespace std {
   template<typename _Iterator, typename _Container> class __normal_iterator;
};

template<typename _Iterator, typename _Container>
struct _Is_normal_iterator< std::__normal_iterator<_Iterator, _Container> > {
   typedef __true_type _Normal;
};
# 70 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3

# 1 "/usr/include/g++-v3/bits/std_cstring.h" 1 3
# 37 "/usr/include/g++-v3/bits/std_cstring.h" 3
# 1 "/usr/include/g++-v3/bits/std_cstddef.h" 1 3
# 38 "/usr/include/g++-v3/bits/std_cstddef.h" 3
# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 147 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 3
typedef int ptrdiff_t;
# 199 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 3
typedef unsigned int size_t;
# 39 "/usr/include/g++-v3/bits/std_cstddef.h" 2 3

namespace std
{
  using ::ptrdiff_t;
  using ::size_t;
}
# 38 "/usr/include/g++-v3/bits/std_cstring.h" 2 3
# 40 "/usr/include/g++-v3/bits/std_cstring.h" 3
# 1 "/usr/include/string.h" 1 3
# 26 "/usr/include/string.h" 3
# 1 "/usr/include/features.h" 1 3
# 27 "/usr/include/string.h" 2 3

extern "C" {




# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 34 "/usr/include/string.h" 2 3



extern void *memcpy (void *__restrict __dest,
                     __const void *__restrict __src, size_t __n) throw ();


extern void *memmove (void *__dest, __const void *__src, size_t __n)
     throw ();





extern void *memccpy (void *__restrict __dest, __const void *__restrict __src,
                      int __c, size_t __n)
     throw ();




extern void *memset (void *__s, int __c, size_t __n) throw ();


extern int memcmp (__const void *__s1, __const void *__s2, size_t __n)
     throw () __attribute__ ((__pure__));


extern void *memchr (__const void *__s, int __c, size_t __n)
      throw () __attribute__ ((__pure__));




extern void *rawmemchr (__const void *__s, int __c) throw () __attribute__ ((__pure__));


extern void *memrchr (__const void *__s, int __c, size_t __n)
      throw () __attribute__ ((__pure__));




extern char *strcpy (char *__restrict __dest, __const char *__restrict __src)
     throw ();

extern char *strncpy (char *__restrict __dest,
                      __const char *__restrict __src, size_t __n) throw ();


extern char *strcat (char *__restrict __dest, __const char *__restrict __src)
     throw ();

extern char *strncat (char *__restrict __dest, __const char *__restrict __src,
                      size_t __n) throw ();


extern int strcmp (__const char *__s1, __const char *__s2)
     throw () __attribute__ ((__pure__));

extern int strncmp (__const char *__s1, __const char *__s2, size_t __n)
     throw () __attribute__ ((__pure__));


extern int strcoll (__const char *__s1, __const char *__s2)
     throw () __attribute__ ((__pure__));

extern size_t strxfrm (char *__restrict __dest,
                       __const char *__restrict __src, size_t __n) throw ();





# 1 "/usr/include/xlocale.h" 1 3
# 28 "/usr/include/xlocale.h" 3
typedef struct __locale_struct
{

  struct locale_data *__locales[13];


  const unsigned short int *__ctype_b;
  const int *__ctype_tolower;
  const int *__ctype_toupper;
} *__locale_t;
# 109 "/usr/include/string.h" 2 3


extern int __strcoll_l (__const char *__s1, __const char *__s2, __locale_t __l)
     throw () __attribute__ ((__pure__));

extern size_t __strxfrm_l (char *__dest, __const char *__src, size_t __n,
                           __locale_t __l) throw ();




extern char *strdup (__const char *__s) throw () __attribute__ ((__malloc__));






extern char *strndup (__const char *__string, size_t __n)
     throw () __attribute__ ((__malloc__));
# 155 "/usr/include/string.h" 3
extern char *strchr (__const char *__s, int __c) throw () __attribute__ ((__pure__));

extern char *strrchr (__const char *__s, int __c) throw () __attribute__ ((__pure__));




extern char *strchrnul (__const char *__s, int __c) throw () __attribute__ ((__pure__));




extern size_t strcspn (__const char *__s, __const char *__reject)
     throw () __attribute__ ((__pure__));


extern size_t strspn (__const char *__s, __const char *__accept)
     throw () __attribute__ ((__pure__));

extern char *strpbrk (__const char *__s, __const char *__accept)
     throw () __attribute__ ((__pure__));

extern char *strstr (__const char *__haystack, __const char *__needle)
     throw () __attribute__ ((__pure__));



extern char *strcasestr (__const char *__haystack, __const char *__needle)
     throw () __attribute__ ((__pure__));



extern char *strtok (char *__restrict __s, __const char *__restrict __delim)
     throw ();



extern char *__strtok_r (char *__restrict __s,
                         __const char *__restrict __delim,
                         char **__restrict __save_ptr) throw ();

extern char *strtok_r (char *__restrict __s, __const char *__restrict __delim,
                       char **__restrict __save_ptr) throw ();






extern void *memmem (__const void *__haystack, size_t __haystacklen,
                     __const void *__needle, size_t __needlelen)
     throw () __attribute__ ((__pure__));



extern void *__mempcpy (void *__restrict __dest,
                        __const void *__restrict __src, size_t __n) throw ();
extern void *mempcpy (void *__restrict __dest,
                      __const void *__restrict __src, size_t __n) throw ();




extern size_t strlen (__const char *__s) throw () __attribute__ ((__pure__));




extern size_t strnlen (__const char *__string, size_t __maxlen)
     throw () __attribute__ ((__pure__));




extern char *strerror (int __errnum) throw ();



extern char *strerror_r (int __errnum, char *__buf, size_t __buflen) throw ();




extern void __bzero (void *__s, size_t __n) throw ();



extern void bcopy (__const void *__src, void *__dest, size_t __n) throw ();


extern void bzero (void *__s, size_t __n) throw ();


extern int bcmp (__const void *__s1, __const void *__s2, size_t __n)
     throw () __attribute__ ((__pure__));


extern char *index (__const char *__s, int __c) throw () __attribute__ ((__pure__));


extern char *rindex (__const char *__s, int __c) throw () __attribute__ ((__pure__));



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__));


extern int strncasecmp (__const char *__s1, __const char *__s2, size_t __n)
     throw () __attribute__ ((__pure__));





extern int __strcasecmp_l (__const char *__s1, __const char *__s2,
                           __locale_t __loc) throw () __attribute__ ((__pure__));

extern int __strncasecmp_l (__const char *__s1, __const char *__s2,
                            size_t __n, __locale_t __loc)
     throw () __attribute__ ((__pure__));





extern char *strsep (char **__restrict __stringp,
                     __const char *__restrict __delim) throw ();




extern int strverscmp (__const char *__s1, __const char *__s2)
     throw () __attribute__ ((__pure__));


extern char *strsignal (int __sig) throw ();


extern char *__stpcpy (char *__restrict __dest, __const char *__restrict __src)
     throw ();
extern char *stpcpy (char *__restrict __dest, __const char *__restrict __src)
     throw ();



extern char *__stpncpy (char *__restrict __dest,
                        __const char *__restrict __src, size_t __n) throw ();
extern char *stpncpy (char *__restrict __dest,
                      __const char *__restrict __src, size_t __n) throw ();


extern char *strfry (char *__string) throw ();


extern void *memfrob (void *__s, size_t __n) throw ();






extern char *basename (__const char *__filename) throw ();
# 364 "/usr/include/string.h" 3
}
# 41 "/usr/include/g++-v3/bits/std_cstring.h" 2 3
# 66 "/usr/include/g++-v3/bits/std_cstring.h" 3
namespace std
{
  using ::memcpy;
  using ::memmove;
  using ::strcpy;
  using ::strncpy;
  using ::strcat;
  using ::strncat;
  using ::memcmp;
  using ::strcmp;
  using ::strcoll;
  using ::strncmp;
  using ::strxfrm;
  using ::strcspn;
  using ::strspn;
  using ::strtok;
  using ::memset;
  using ::strerror;
  using ::strlen;

  using ::memchr;

  inline void*
  memchr(void* __p, int __c, size_t __n)
  { return memchr(const_cast<const void*>(__p), __c, __n); }

  using ::strchr;

  inline char*
  strchr(char* __s1, int __n)
  { return __builtin_strchr(const_cast<const char*>(__s1), __n); }

  using ::strpbrk;

  inline char*
  strpbrk(char* __s1, const char* __s2)
  { return __builtin_strpbrk(const_cast<const char*>(__s1), __s2); }

  using ::strrchr;

  inline char*
  strrchr(char* __s1, int __n)
  { return __builtin_strrchr(const_cast<const char*>(__s1), __n); }

  using ::strstr;

  inline char*
  strstr(char* __s1, const char* __s2)
  { return __builtin_strstr(const_cast<const char*>(__s1), __s2); }
}
# 72 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_climits.h" 1 3
# 38 "/usr/include/g++-v3/bits/std_climits.h" 3
# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/limits.h" 1 3
# 11 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/limits.h" 3
# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/syslimits.h" 1 3






# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/limits.h" 1 3
# 125 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/limits.h" 3
# 1 "/usr/include/limits.h" 1 3
# 26 "/usr/include/limits.h" 3
# 1 "/usr/include/features.h" 1 3
# 27 "/usr/include/limits.h" 2 3
# 144 "/usr/include/limits.h" 3
# 1 "/usr/include/bits/posix1_lim.h" 1 3
# 126 "/usr/include/bits/posix1_lim.h" 3
# 1 "/usr/include/bits/local_lim.h" 1 3
# 36 "/usr/include/bits/local_lim.h" 3
# 1 "/usr/include/linux/limits.h" 1 3
# 37 "/usr/include/bits/local_lim.h" 2 3
# 127 "/usr/include/bits/posix1_lim.h" 2 3
# 145 "/usr/include/limits.h" 2 3



# 1 "/usr/include/bits/posix2_lim.h" 1 3
# 149 "/usr/include/limits.h" 2 3



# 1 "/usr/include/bits/xopen_lim.h" 1 3
# 34 "/usr/include/bits/xopen_lim.h" 3
# 1 "/usr/include/bits/stdio_lim.h" 1 3
# 35 "/usr/include/bits/xopen_lim.h" 2 3
# 136 "/usr/include/bits/xopen_lim.h" 3
# 1 "/usr/include/bits/wordsize.h" 1 3
# 137 "/usr/include/bits/xopen_lim.h" 2 3
# 153 "/usr/include/limits.h" 2 3
# 126 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/limits.h" 2 3
# 8 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/syslimits.h" 2 3
# 12 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/limits.h" 2 3
# 39 "/usr/include/g++-v3/bits/std_climits.h" 2 3
# 73 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_cstdlib.h" 1 3
# 37 "/usr/include/g++-v3/bits/std_cstdlib.h" 3
# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 1 3
# 38 "/usr/include/g++-v3/bits/std_cstdlib.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_cstddef.h" 1 3
# 39 "/usr/include/g++-v3/bits/std_cstdlib.h" 2 3
# 41 "/usr/include/g++-v3/bits/std_cstdlib.h" 3
# 1 "/usr/include/stdlib.h" 1 3
# 25 "/usr/include/stdlib.h" 3
# 1 "/usr/include/features.h" 1 3
# 26 "/usr/include/stdlib.h" 2 3







# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 34 "/usr/include/stdlib.h" 2 3

extern "C" {






# 1 "/usr/include/bits/waitflags.h" 1 3
# 43 "/usr/include/stdlib.h" 2 3
# 1 "/usr/include/bits/waitstatus.h" 1 3
# 63 "/usr/include/bits/waitstatus.h" 3
# 1 "/usr/include/endian.h" 1 3
# 22 "/usr/include/endian.h" 3
# 1 "/usr/include/features.h" 1 3
# 23 "/usr/include/endian.h" 2 3
# 37 "/usr/include/endian.h" 3
# 1 "/usr/include/bits/endian.h" 1 3
# 38 "/usr/include/endian.h" 2 3
# 64 "/usr/include/bits/waitstatus.h" 2 3

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;
  };
# 44 "/usr/include/stdlib.h" 2 3
# 94 "/usr/include/stdlib.h" 3
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;
# 133 "/usr/include/stdlib.h" 3
extern size_t __ctype_get_mb_cur_max (void) throw ();



extern double atof (__const char *__nptr) throw () __attribute__ ((__pure__));

extern int atoi (__const char *__nptr) throw () __attribute__ ((__pure__));

extern long int atol (__const char *__nptr) throw () __attribute__ ((__pure__));



__extension__ extern long long int atoll (__const char *__nptr)
     throw () __attribute__ ((__pure__));



extern double strtod (__const char *__restrict __nptr,
                      char **__restrict __endptr) throw ();



extern float strtof (__const char *__restrict __nptr,
                     char **__restrict __endptr) throw ();

extern long double strtold (__const char *__restrict __nptr,
                            char **__restrict __endptr) throw ();



extern long int strtol (__const char *__restrict __nptr,
                        char **__restrict __endptr, int __base) throw ();

extern unsigned long int strtoul (__const char *__restrict __nptr,
                                  char **__restrict __endptr, int __base)
     throw ();



__extension__
extern long long int strtoq (__const char *__restrict __nptr,
                             char **__restrict __endptr, int __base) throw ();

__extension__
extern unsigned long long int strtouq (__const char *__restrict __nptr,
                                       char **__restrict __endptr, int __base)
     throw ();






__extension__
extern long long int strtoll (__const char *__restrict __nptr,
                              char **__restrict __endptr, int __base) throw ();

__extension__
extern unsigned long long int strtoull (__const char *__restrict __nptr,
                                        char **__restrict __endptr, int __base)
     throw ();
# 211 "/usr/include/stdlib.h" 3
# 1 "/usr/include/xlocale.h" 1 3
# 212 "/usr/include/stdlib.h" 2 3



extern long int __strtol_l (__const char *__restrict __nptr,
                            char **__restrict __endptr, int __base,
                            __locale_t __loc) throw ();

extern unsigned long int __strtoul_l (__const char *__restrict __nptr,
                                      char **__restrict __endptr,
                                      int __base, __locale_t __loc) throw ();

__extension__
extern long long int __strtoll_l (__const char *__restrict __nptr,
                                  char **__restrict __endptr, int __base,
                                  __locale_t __loc) throw ();

__extension__
extern unsigned long long int __strtoull_l (__const char *__restrict __nptr,
                                            char **__restrict __endptr,
                                            int __base, __locale_t __loc)
     throw ();

extern double __strtod_l (__const char *__restrict __nptr,
                          char **__restrict __endptr, __locale_t __loc)
     throw ();

extern float __strtof_l (__const char *__restrict __nptr,
                         char **__restrict __endptr, __locale_t __loc) throw ();

extern long double __strtold_l (__const char *__restrict __nptr,
                                char **__restrict __endptr,
                                __locale_t __loc) throw ();






extern double __strtod_internal (__const char *__restrict __nptr,
                                 char **__restrict __endptr, int __group)
     throw ();
extern float __strtof_internal (__const char *__restrict __nptr,
                                char **__restrict __endptr, int __group)
     throw ();
extern long double __strtold_internal (__const char *__restrict __nptr,
                                       char **__restrict __endptr,
                                       int __group) throw ();

extern long int __strtol_internal (__const char *__restrict __nptr,
                                   char **__restrict __endptr,
                                   int __base, int __group) throw ();



extern unsigned long int __strtoul_internal (__const char *__restrict __nptr,
                                             char **__restrict __endptr,
                                             int __base, int __group) throw ();




__extension__
extern long long int __strtoll_internal (__const char *__restrict __nptr,
                                         char **__restrict __endptr,
                                         int __base, int __group) throw ();



__extension__
extern unsigned long long int __strtoull_internal (__const char *
                                                   __restrict __nptr,
                                                   char **__restrict __endptr,
                                                   int __base, int __group)
     throw ();
# 384 "/usr/include/stdlib.h" 3
extern char *l64a (long int __n) throw ();


extern long int a64l (__const char *__s) throw () __attribute__ ((__pure__));


# 1 "/usr/include/sys/types.h" 1 3
# 26 "/usr/include/sys/types.h" 3
# 1 "/usr/include/features.h" 1 3
# 27 "/usr/include/sys/types.h" 2 3

extern "C" {

# 1 "/usr/include/bits/types.h" 1 3
# 26 "/usr/include/bits/types.h" 3
# 1 "/usr/include/features.h" 1 3
# 27 "/usr/include/bits/types.h" 2 3


# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 30 "/usr/include/bits/types.h" 2 3


typedef unsigned char __u_char;
typedef unsigned short __u_short;
typedef unsigned int __u_int;
typedef unsigned long __u_long;

__extension__ typedef unsigned long long int __u_quad_t;
__extension__ typedef long long int __quad_t;
# 49 "/usr/include/bits/types.h" 3
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;

__extension__ typedef signed long long int __int64_t;
__extension__ typedef unsigned long long int __uint64_t;

typedef __quad_t *__qaddr_t;

typedef __u_quad_t __dev_t;
typedef __u_int __uid_t;
typedef __u_int __gid_t;
typedef __u_long __ino_t;
typedef __u_int __mode_t;
typedef __u_int __nlink_t;
typedef long int __off_t;
typedef __quad_t __loff_t;
typedef int __pid_t;
typedef int __ssize_t;
typedef __u_long __rlim_t;
typedef __u_quad_t __rlim64_t;
typedef __u_int __id_t;

typedef struct
  {
    int __val[2];
  } __fsid_t;


typedef int __daddr_t;
typedef char *__caddr_t;
typedef long int __time_t;
typedef unsigned int __useconds_t;
typedef long int __suseconds_t;
typedef long int __swblk_t;

typedef long int __clock_t;


typedef int __clockid_t;


typedef int __timer_t;






typedef int __key_t;


typedef unsigned short int __ipc_pid_t;



typedef long int __blksize_t;




typedef long int __blkcnt_t;
typedef __quad_t __blkcnt64_t;


typedef __u_long __fsblkcnt_t;
typedef __u_quad_t __fsblkcnt64_t;


typedef __u_long __fsfilcnt_t;
typedef __u_quad_t __fsfilcnt64_t;


typedef __u_quad_t __ino64_t;


typedef __loff_t __off64_t;


typedef long int __t_scalar_t;
typedef unsigned long int __t_uscalar_t;


typedef int __intptr_t;


typedef unsigned int __socklen_t;




# 1 "/usr/include/bits/pthreadtypes.h" 1 3
# 23 "/usr/include/bits/pthreadtypes.h" 3
# 1 "/usr/include/bits/sched.h" 1 3
# 68 "/usr/include/bits/sched.h" 3
struct __sched_param
  {
    int __sched_priority;
  };
# 24 "/usr/include/bits/pthreadtypes.h" 2 3


struct _pthread_fastlock
{
  long int __status;
  int __spinlock;

};



typedef struct _pthread_descr_struct *_pthread_descr;





typedef struct __pthread_attr_s
{
  int __detachstate;
  int __schedpolicy;
  struct __sched_param __schedparam;
  int __inheritsched;
  int __scope;
  size_t __guardsize;
  int __stackaddr_set;
  void *__stackaddr;
  size_t __stacksize;
} pthread_attr_t;



typedef struct
{
  struct _pthread_fastlock __c_lock;
  _pthread_descr __c_waiting;
} pthread_cond_t;



typedef struct
{
  int __dummy;
} pthread_condattr_t;


typedef unsigned int pthread_key_t;





typedef struct
{
  int __m_reserved;
  int __m_count;
  _pthread_descr __m_owner;
  int __m_kind;
  struct _pthread_fastlock __m_lock;
} pthread_mutex_t;



typedef struct
{
  int __mutexkind;
} pthread_mutexattr_t;



typedef int pthread_once_t;




typedef struct _pthread_rwlock_t
{
  struct _pthread_fastlock __rw_lock;
  int __rw_readers;
  _pthread_descr __rw_writer;
  _pthread_descr __rw_read_waiting;
  _pthread_descr __rw_write_waiting;
  int __rw_kind;
  int __rw_pshared;
} pthread_rwlock_t;



typedef struct
{
  int __lockkind;
  int __pshared;
} pthread_rwlockattr_t;




typedef volatile int pthread_spinlock_t;


typedef struct {
  struct _pthread_fastlock __ba_lock;
  int __ba_required;
  int __ba_present;
  _pthread_descr __ba_waiting;
} pthread_barrier_t;


typedef struct {
  int __pshared;
} pthread_barrierattr_t;





typedef unsigned long int pthread_t;
# 144 "/usr/include/bits/types.h" 2 3
# 31 "/usr/include/sys/types.h" 2 3



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 __ino_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 __off_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;
# 132 "/usr/include/sys/types.h" 3
# 1 "/usr/include/time.h" 1 3
# 56 "/usr/include/time.h" 3
# 1 "/usr/include/bits/types.h" 1 3
# 57 "/usr/include/time.h" 2 3


typedef __clock_t clock_t;







# 1 "/usr/include/bits/types.h" 1 3
# 68 "/usr/include/time.h" 2 3


typedef __time_t time_t;
# 79 "/usr/include/time.h" 3
# 1 "/usr/include/bits/types.h" 1 3
# 80 "/usr/include/time.h" 2 3


typedef __clockid_t clockid_t;
# 91 "/usr/include/time.h" 3
# 1 "/usr/include/bits/types.h" 1 3
# 92 "/usr/include/time.h" 2 3


typedef __timer_t timer_t;
# 133 "/usr/include/sys/types.h" 2 3



typedef __useconds_t useconds_t;



typedef __suseconds_t suseconds_t;





# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 147 "/usr/include/sys/types.h" 2 3



typedef unsigned long int ulong;
typedef unsigned short int ushort;
typedef unsigned int uint;
# 190 "/usr/include/sys/types.h" 3
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__)));
# 212 "/usr/include/sys/types.h" 3
# 1 "/usr/include/endian.h" 1 3
# 213 "/usr/include/sys/types.h" 2 3


# 1 "/usr/include/sys/select.h" 1 3
# 25 "/usr/include/sys/select.h" 3
# 1 "/usr/include/features.h" 1 3
# 26 "/usr/include/sys/select.h" 2 3


# 1 "/usr/include/bits/types.h" 1 3
# 29 "/usr/include/sys/select.h" 2 3


# 1 "/usr/include/bits/select.h" 1 3
# 32 "/usr/include/sys/select.h" 2 3


# 1 "/usr/include/bits/sigset.h" 1 3
# 23 "/usr/include/bits/sigset.h" 3
typedef int __sig_atomic_t;




typedef struct
  {
    unsigned long int __val[(1024 / (8 * sizeof (unsigned long int)))];
  } __sigset_t;
# 35 "/usr/include/sys/select.h" 2 3



typedef __sigset_t sigset_t;




# 1 "/usr/include/time.h" 1 3
# 106 "/usr/include/time.h" 3
struct timespec
  {
    long int tv_sec;
    long int tv_nsec;
  };
# 44 "/usr/include/sys/select.h" 2 3

# 1 "/usr/include/bits/time.h" 1 3
# 63 "/usr/include/bits/time.h" 3
# 1 "/usr/include/bits/types.h" 1 3
# 64 "/usr/include/bits/time.h" 2 3



struct timeval
  {
    __time_t tv_sec;
    __suseconds_t tv_usec;
  };
# 46 "/usr/include/sys/select.h" 2 3



typedef long int __fd_mask;







typedef struct
  {



    __fd_mask fds_bits[1024 / (8 * sizeof (__fd_mask))];





  } fd_set;






typedef __fd_mask fd_mask;
# 89 "/usr/include/sys/select.h" 3
extern "C" {






extern int select (int __nfds, fd_set *__restrict __readfds,
                   fd_set *__restrict __writefds,
                   fd_set *__restrict __exceptfds,
                   struct timeval *__restrict __timeout) throw ();





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) throw ();


}
# 216 "/usr/include/sys/types.h" 2 3


# 1 "/usr/include/sys/sysmacros.h" 1 3
# 219 "/usr/include/sys/types.h" 2 3




typedef __blksize_t blksize_t;






typedef __blkcnt_t blkcnt_t;



typedef __fsblkcnt_t fsblkcnt_t;



typedef __fsfilcnt_t fsfilcnt_t;
# 257 "/usr/include/sys/types.h" 3
typedef __blkcnt64_t blkcnt64_t;
typedef __fsblkcnt64_t fsblkcnt64_t;
typedef __fsfilcnt64_t fsfilcnt64_t;


}
# 391 "/usr/include/stdlib.h" 2 3






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 ();



extern char *setstate (char *__statebuf) throw ();







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 ();

extern int srandom_r (unsigned int __seed, struct random_data *__buf) throw ();

extern int initstate_r (unsigned int __seed, char *__restrict __statebuf,
                        size_t __statelen,
                        struct random_data *__restrict __buf) throw ();

extern int setstate_r (char *__restrict __statebuf,
                       struct random_data *__restrict __buf) throw ();





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 ();


extern long int lrand48 (void) throw ();
extern long int nrand48 (unsigned short int __xsubi[3]) throw ();


extern long int mrand48 (void) throw ();
extern long int jrand48 (unsigned short int __xsubi[3]) throw ();


extern void srand48 (long int __seedval) throw ();
extern unsigned short int *seed48 (unsigned short int __seed16v[3]) throw ();
extern void lcong48 (unsigned short int __param[7]) throw ();





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 ();
extern int erand48_r (unsigned short int __xsubi[3],
                      struct drand48_data *__restrict __buffer,
                      double *__restrict __result) throw ();


extern int lrand48_r (struct drand48_data *__restrict __buffer,
                      long int *__restrict __result) throw ();
extern int nrand48_r (unsigned short int __xsubi[3],
                      struct drand48_data *__restrict __buffer,
                      long int *__restrict __result) throw ();


extern int mrand48_r (struct drand48_data *__restrict __buffer,
                      long int *__restrict __result) throw ();
extern int jrand48_r (unsigned short int __xsubi[3],
                      struct drand48_data *__restrict __buffer,
                      long int *__restrict __result) throw ();


extern int srand48_r (long int __seedval, struct drand48_data *__buffer)
     throw ();

extern int seed48_r (unsigned short int __seed16v[3],
                     struct drand48_data *__buffer) throw ();

extern int lcong48_r (unsigned short int __param[7],
                      struct drand48_data *__buffer) throw ();
# 527 "/usr/include/stdlib.h" 3
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__ ((__malloc__));

extern void free (void *__ptr) throw ();



extern void cfree (void *__ptr) throw ();



# 1 "/usr/include/alloca.h" 1 3
# 22 "/usr/include/alloca.h" 3
# 1 "/usr/include/features.h" 1 3
# 23 "/usr/include/alloca.h" 2 3


# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 26 "/usr/include/alloca.h" 2 3

extern "C" {





extern void *alloca (size_t __size) throw ();





}
# 547 "/usr/include/stdlib.h" 2 3




extern void *valloc (size_t __size) throw () __attribute__ ((__malloc__));




extern int posix_memalign (void **__memptr, size_t __alignment, size_t __size)
     throw () __attribute__ ((__malloc__));



extern void abort (void) throw () __attribute__ ((__noreturn__));



extern int atexit (void (*__func) (void)) throw ();




extern int on_exit (void (*__func) (int __status, void *__arg), void *__arg)
     throw ();





extern void exit (int __status) throw () __attribute__ ((__noreturn__));




extern void _Exit (int __status) throw () __attribute__ ((__noreturn__));




extern char *getenv (__const char *__name) throw ();



extern char *__secure_getenv (__const char *__name) throw ();





extern int putenv (char *__string) throw ();





extern int setenv (__const char *__name, __const char *__value, int __replace)
     throw ();


extern int unsetenv (__const char *__name) throw ();






extern int clearenv (void) throw ();
# 623 "/usr/include/stdlib.h" 3
extern char *mktemp (char *__template) throw ();







extern int mkstemp (char *__template) throw ();
# 640 "/usr/include/stdlib.h" 3
extern int mkstemp64 (char *__template) throw ();
# 650 "/usr/include/stdlib.h" 3
extern char *mkdtemp (char *__template) throw ();




extern int system (__const char *__command) throw ();






extern char *canonicalize_file_name (__const char *__name) throw ();
# 672 "/usr/include/stdlib.h" 3
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;





extern void *bsearch (__const void *__key, __const void *__base,
                      size_t __nmemb, size_t __size, __compar_fn_t __compar);



extern void qsort (void *__base, size_t __nmemb, size_t __size,
                   __compar_fn_t __compar);



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__));
# 728 "/usr/include/stdlib.h" 3
extern char *ecvt (double __value, int __ndigit, int *__restrict __decpt,
                   int *__restrict __sign) throw ();




extern char *fcvt (double __value, int __ndigit, int *__restrict __decpt,
                   int *__restrict __sign) throw ();




extern char *gcvt (double __value, int __ndigit, char *__buf) throw ();




extern char *qecvt (long double __value, int __ndigit,
                    int *__restrict __decpt, int *__restrict __sign) throw ();
extern char *qfcvt (long double __value, int __ndigit,
                    int *__restrict __decpt, int *__restrict __sign) throw ();
extern char *qgcvt (long double __value, int __ndigit, char *__buf) throw ();




extern int ecvt_r (double __value, int __ndigit, int *__restrict __decpt,
                   int *__restrict __sign, char *__restrict __buf,
                   size_t __len) throw ();
extern int fcvt_r (double __value, int __ndigit, int *__restrict __decpt,
                   int *__restrict __sign, char *__restrict __buf,
                   size_t __len) throw ();

extern int qecvt_r (long double __value, int __ndigit,
                    int *__restrict __decpt, int *__restrict __sign,
                    char *__restrict __buf, size_t __len) throw ();
extern int qfcvt_r (long double __value, int __ndigit,
                    int *__restrict __decpt, int *__restrict __sign,
                    char *__restrict __buf, size_t __len) throw ();






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 ();
# 808 "/usr/include/stdlib.h" 3
extern int getsubopt (char **__restrict __optionp,
                      char *__const *__restrict __tokens,
                      char **__restrict __valuep) throw ();





extern void setkey (__const char *__key) throw ();







extern int posix_openpt (int __oflag) throw ();







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 ();


extern int getpt (void) throw ();






extern int getloadavg (double __loadavg[], int __nelem) throw ();





}
# 42 "/usr/include/g++-v3/bits/std_cstdlib.h" 2 3
# 73 "/usr/include/g++-v3/bits/std_cstdlib.h" 3
namespace std
{
  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); }
}
# 125 "/usr/include/g++-v3/bits/std_cstdlib.h" 3
namespace __gnu_cxx
{
  using ::lldiv_t;
  using ::_Exit;

  inline long long
  abs(long long __x) { return __x >= 0 ? __x : -__x; }

  inline long long
  llabs(long long __x) { return __x >= 0 ? __x : -__x; }

  inline lldiv_t
  div(long long __n, long long __d)
  { lldiv_t __q; __q.quot = __n / __d; __q.rem = __n % __d; return __q; }

  inline lldiv_t
  lldiv(long long __n, long long __d)
  { lldiv_t __q; __q.quot = __n / __d; __q.rem = __n % __d; return __q; }

  using ::atoll;
  using ::strtof;
  using ::strtoll;
  using ::strtoull;
  using ::strtold;
}

namespace std
{
  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;
}
# 74 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_cstddef.h" 1 3
# 75 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/include/g++-v3/new" 1 3
# 40 "/usr/include/g++-v3/new" 3
# 1 "/usr/include/g++-v3/cstddef" 1 3
# 41 "/usr/include/g++-v3/new" 2 3
# 1 "/usr/include/g++-v3/exception" 1 3
# 39 "/usr/include/g++-v3/exception" 3
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();
  };


  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__));
# 95 "/usr/include/g++-v3/exception" 3
  bool uncaught_exception() throw();
}

}
# 42 "/usr/include/g++-v3/new" 2 3

extern "C++" {

namespace std
{


  class bad_alloc : public exception
  {
  public:
    bad_alloc() throw() { }
    virtual ~bad_alloc() throw();
  };

  struct nothrow_t { };
  extern const nothrow_t nothrow;


  typedef void (*new_handler)();

  new_handler set_new_handler(new_handler);
}
# 76 "/usr/include/g++-v3/new" 3
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 *place) throw() { return place; }
inline void *operator new[](std::size_t, void *place) throw() { return place; }

}
# 76 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3

# 1 "/usr/include/g++-v3/bits/std_iosfwd.h" 1 3
# 38 "/usr/include/g++-v3/bits/std_iosfwd.h" 3

# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 1 3
# 40 "/usr/include/g++-v3/bits/std_iosfwd.h" 2 3
# 1 "/usr/include/g++-v3/bits/stringfwd.h" 1 3
# 38 "/usr/include/g++-v3/bits/stringfwd.h" 3

# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 1 3
# 40 "/usr/include/g++-v3/bits/stringfwd.h" 2 3

namespace std
{
  template<class _CharT>
    struct char_traits;

  template<> struct char_traits<char>;

  template<> struct char_traits<wchar_t>;


  template<typename _Alloc>
    class allocator;

  template<typename _CharT, typename _Traits = char_traits<_CharT>,
           typename _Alloc = allocator<_CharT> >
    class basic_string;

  typedef basic_string<char> string;

  typedef basic_string<wchar_t> wstring;

}
# 41 "/usr/include/g++-v3/bits/std_iosfwd.h" 2 3
# 1 "/usr/include/g++-v3/bits/fpos.h" 1 3
# 38 "/usr/include/g++-v3/bits/fpos.h" 3

# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++io.h" 1 3
# 35 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++io.h" 3
# 1 "/usr/include/g++-v3/cstdio" 1 3
# 31 "/usr/include/g++-v3/cstdio" 3
# 1 "/usr/include/g++-v3/bits/std_cstdio.h" 1 3
# 37 "/usr/include/g++-v3/bits/std_cstdio.h" 3
# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 1 3
# 38 "/usr/include/g++-v3/bits/std_cstdio.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_cstddef.h" 1 3
# 39 "/usr/include/g++-v3/bits/std_cstdio.h" 2 3
# 41 "/usr/include/g++-v3/bits/std_cstdio.h" 3
# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 1 3
# 37 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
# 1 "/usr/include/features.h" 1 3
# 38 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 2 3

extern "C" {



# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 44 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 2 3

# 1 "/usr/include/bits/types.h" 1 3
# 46 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 2 3
# 54 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
typedef struct _IO_FILE FILE;
# 64 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
typedef struct _IO_FILE __FILE;
# 74 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
# 1 "/usr/include/libio.h" 1 3
# 32 "/usr/include/libio.h" 3
# 1 "/usr/include/_G_config.h" 1 3
# 9 "/usr/include/_G_config.h" 3
# 1 "/usr/include/bits/types.h" 1 3
# 10 "/usr/include/_G_config.h" 2 3




# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 312 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 3
typedef unsigned int wint_t;
# 15 "/usr/include/_G_config.h" 2 3
# 24 "/usr/include/_G_config.h" 3
# 1 "/usr/include/wchar.h" 1 3
# 48 "/usr/include/wchar.h" 3
# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 49 "/usr/include/wchar.h" 2 3

# 1 "/usr/include/bits/wchar.h" 1 3
# 51 "/usr/include/wchar.h" 2 3
# 67 "/usr/include/wchar.h" 3
typedef struct
{
  int __count;
  union
  {
    wint_t __wch;
    char __wchb[4];
  } __value;
} __mbstate_t;
# 25 "/usr/include/_G_config.h" 2 3

typedef struct
{
  __off_t __pos;
  __mbstate_t __state;
} _G_fpos_t;
typedef struct
{
  __off64_t __pos;
  __mbstate_t __state;
} _G_fpos64_t;
# 44 "/usr/include/_G_config.h" 3
# 1 "/usr/include/gconv.h" 1 3
# 26 "/usr/include/gconv.h" 3
# 1 "/usr/include/features.h" 1 3
# 27 "/usr/include/gconv.h" 2 3

# 1 "/usr/include/wchar.h" 1 3
# 48 "/usr/include/wchar.h" 3
# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 49 "/usr/include/wchar.h" 2 3

# 1 "/usr/include/bits/wchar.h" 1 3
# 51 "/usr/include/wchar.h" 2 3
# 29 "/usr/include/gconv.h" 2 3

# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 31 "/usr/include/gconv.h" 2 3





enum
{
  __GCONV_OK = 0,
  __GCONV_NOCONV,
  __GCONV_NODB,
  __GCONV_NOMEM,

  __GCONV_EMPTY_INPUT,
  __GCONV_FULL_OUTPUT,
  __GCONV_ILLEGAL_INPUT,
  __GCONV_INCOMPLETE_INPUT,

  __GCONV_ILLEGAL_DESCRIPTOR,
  __GCONV_INTERNAL_ERROR
};



enum
{
  __GCONV_IS_LAST = 0x0001,
  __GCONV_IGNORE_ERRORS = 0x0002
};



struct __gconv_step;
struct __gconv_step_data;
struct __gconv_loaded_object;
struct __gconv_trans_data;



typedef int (*__gconv_fct) (struct __gconv_step *, struct __gconv_step_data *,
                            __const unsigned char **, __const unsigned char *,
                            unsigned char **, size_t *, int, int);


typedef int (*__gconv_init_fct) (struct __gconv_step *);
typedef void (*__gconv_end_fct) (struct __gconv_step *);



typedef int (*__gconv_trans_fct) (struct __gconv_step *,
                                  struct __gconv_step_data *, void *,
                                  __const unsigned char *,
                                  __const unsigned char **,
                                  __const unsigned char *, unsigned char **,
                                  size_t *);


typedef int (*__gconv_trans_context_fct) (void *, __const unsigned char *,
                                          __const unsigned char *,
                                          unsigned char *, unsigned char *);


typedef int (*__gconv_trans_query_fct) (__const char *, __const char ***,
                                        size_t *);


typedef int (*__gconv_trans_init_fct) (void **, const char *);
typedef void (*__gconv_trans_end_fct) (void *);

struct __gconv_trans_data
{

  __gconv_trans_fct __trans_fct;
  __gconv_trans_context_fct __trans_context_fct;
  __gconv_trans_end_fct __trans_end_fct;
  void *__data;
  struct __gconv_trans_data *__next;
};



struct __gconv_step
{
  struct __gconv_loaded_object *__shlib_handle;
  __const char *__modname;

  int __counter;

  char *__from_name;
  char *__to_name;

  __gconv_fct __fct;
  __gconv_init_fct __init_fct;
  __gconv_end_fct __end_fct;



  int __min_needed_from;
  int __max_needed_from;
  int __min_needed_to;
  int __max_needed_to;


  int __stateful;

  void *__data;
};



struct __gconv_step_data
{
  unsigned char *__outbuf;
  unsigned char *__outbufend;



  int __flags;



  int __invocation_counter;



  int __internal_use;

  __mbstate_t *__statep;
  __mbstate_t __state;



  struct __gconv_trans_data *__trans;
};



typedef struct __gconv_info
{
  size_t __nsteps;
  struct __gconv_step *__steps;
  __extension__ struct __gconv_step_data __data [];
} *__gconv_t;
# 45 "/usr/include/_G_config.h" 2 3
typedef union
{
  struct __gconv_info __cd;
  struct
  {
    struct __gconv_info __cd;
    struct __gconv_step_data __data;
  } __combined;
} _G_iconv_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__)));
# 33 "/usr/include/libio.h" 2 3
# 53 "/usr/include/libio.h" 3
# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdarg.h" 1 3
# 43 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdarg.h" 3
typedef __builtin_va_list __gnuc_va_list;
# 54 "/usr/include/libio.h" 2 3
# 160 "/usr/include/libio.h" 3
struct _IO_jump_t; struct _IO_FILE;
# 170 "/usr/include/libio.h" 3
typedef void _IO_lock_t;





struct _IO_marker {
  struct _IO_marker *_next;
  struct _IO_FILE *_sbuf;



  int _pos;
# 193 "/usr/include/libio.h" 3
};


enum __codecvt_result
{
  __codecvt_ok,
  __codecvt_partial,
  __codecvt_error,
  __codecvt_noconv
};




struct _IO_codecvt
{
  void (*__codecvt_destr) (struct _IO_codecvt *);
  enum __codecvt_result (*__codecvt_do_out) (struct _IO_codecvt *,
                                             __mbstate_t *,
                                             const wchar_t *,
                                             const wchar_t *,
                                             const wchar_t **, char *,
                                             char *, char **);
  enum __codecvt_result (*__codecvt_do_unshift) (struct _IO_codecvt *,
                                                 __mbstate_t *, char *,
                                                 char *, char **);
  enum __codecvt_result (*__codecvt_do_in) (struct _IO_codecvt *,
                                            __mbstate_t *,
                                            const char *, const char *,
                                            const char **, wchar_t *,
                                            wchar_t *, wchar_t **);
  int (*__codecvt_do_encoding) (struct _IO_codecvt *);
  int (*__codecvt_do_always_noconv) (struct _IO_codecvt *);
  int (*__codecvt_do_length) (struct _IO_codecvt *, __mbstate_t *,
                              const char *, const char *, size_t);
  int (*__codecvt_do_max_length) (struct _IO_codecvt *);

  _G_iconv_t __cd_in;
  _G_iconv_t __cd_out;
};


struct _IO_wide_data
{
  wchar_t *_IO_read_ptr;
  wchar_t *_IO_read_end;
  wchar_t *_IO_read_base;
  wchar_t *_IO_write_base;
  wchar_t *_IO_write_ptr;
  wchar_t *_IO_write_end;
  wchar_t *_IO_buf_base;
  wchar_t *_IO_buf_end;

  wchar_t *_IO_save_base;
  wchar_t *_IO_backup_base;

  wchar_t *_IO_save_end;

  __mbstate_t _IO_state;
  __mbstate_t _IO_last_state;
  struct _IO_codecvt _codecvt;

  wchar_t _shortbuf[1];

  struct _IO_jump_t *_wide_vtable;
};


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 _blksize;
  __off_t _old_offset;



  unsigned short _cur_column;
  signed char _vtable_offset;
  char _shortbuf[1];



  _IO_lock_t *_lock;
# 305 "/usr/include/libio.h" 3
  __off64_t _offset;


  struct _IO_codecvt *_codecvt;
  struct _IO_wide_data *_wide_data;




  int _mode;

  char _unused2[15 * sizeof (int) - 2 * sizeof (void *)];

};





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_;
# 344 "/usr/include/libio.h" 3
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 *) throw ();
extern int __uflow (_IO_FILE *) throw ();
extern int __overflow (_IO_FILE *, int) throw ();
extern wint_t __wunderflow (_IO_FILE *) throw ();
extern wint_t __wuflow (_IO_FILE *) throw ();
extern wint_t __woverflow (_IO_FILE *, wint_t) throw ();
# 426 "/usr/include/libio.h" 3
extern int _IO_getc (_IO_FILE *__fp) throw ();
extern int _IO_putc (int __c, _IO_FILE *__fp) throw ();
extern int _IO_feof (_IO_FILE *__fp) throw ();
extern int _IO_ferror (_IO_FILE *__fp) throw ();

extern int _IO_peekc_locked (_IO_FILE *__fp) throw ();





extern void _IO_flockfile (_IO_FILE *) throw ();
extern void _IO_funlockfile (_IO_FILE *) throw ();
extern int _IO_ftrylockfile (_IO_FILE *) throw ();
# 456 "/usr/include/libio.h" 3
extern int _IO_vfscanf (_IO_FILE * __restrict, const char * __restrict,
                        __gnuc_va_list, int *__restrict) throw ();
extern int _IO_vfprintf (_IO_FILE *__restrict, const char *__restrict,
                         __gnuc_va_list) throw ();
extern __ssize_t _IO_padn (_IO_FILE *, int, __ssize_t) throw ();
extern size_t _IO_sgetn (_IO_FILE *, void *, size_t) throw ();

extern __off64_t _IO_seekoff (_IO_FILE *, __off64_t, int, int) throw ();
extern __off64_t _IO_seekpos (_IO_FILE *, __off64_t, int) throw ();

extern void _IO_free_backup_area (_IO_FILE *) throw ();


extern wint_t _IO_getwc (_IO_FILE *__fp) throw ();
extern wint_t _IO_putwc (wchar_t __wc, _IO_FILE *__fp) throw ();
extern int _IO_fwide (_IO_FILE *__fp, int __mode) throw ();
# 505 "/usr/include/libio.h" 3
extern int _IO_vfwscanf (_IO_FILE * __restrict, const wchar_t * __restrict,
                         __gnuc_va_list, int *__restrict) throw ();
extern int _IO_vfwprintf (_IO_FILE *__restrict, const wchar_t *__restrict,
                          __gnuc_va_list) throw ();
extern __ssize_t _IO_wpadn (_IO_FILE *, wint_t, __ssize_t) throw ();
extern void _IO_free_wbackup_area (_IO_FILE *) throw ();



}
# 75 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 2 3




typedef __gnuc_va_list __not_va_list__;
# 89 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
typedef _G_fpos_t fpos_t;




typedef _G_fpos64_t fpos64_t;
# 138 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
# 1 "/usr/include/bits/stdio_lim.h" 1 3
# 139 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 2 3



extern FILE *stdin;
extern FILE *stdout;
extern FILE *stderr;






extern int remove (__const char *__filename) throw ();

extern int rename (__const char *__old, __const char *__new) throw ();




extern FILE *tmpfile (void) throw ();
# 167 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
extern FILE *tmpfile64 (void) throw ();


extern char *tmpnam (char *__s) throw ();




extern char *tmpnam_r (char *__s) throw ();
# 187 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
extern char *tempnam (__const char *__dir, __const char *__pfx)
     throw () __attribute__ ((__malloc__));




extern int fclose (FILE *__stream) throw ();

extern int fflush (FILE *__stream) throw ();



extern int fflush_unlocked (FILE *__stream) throw ();




extern int fcloseall (void) throw ();





extern FILE *fopen (__const char *__restrict __filename,
                    __const char *__restrict __modes) throw ();

extern FILE *freopen (__const char *__restrict __filename,
                      __const char *__restrict __modes,
                      FILE *__restrict __stream) throw ();
# 231 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
extern FILE *fopen64 (__const char *__restrict __filename,
                      __const char *__restrict __modes) throw ();
extern FILE *freopen64 (__const char *__restrict __filename,
                        __const char *__restrict __modes,
                        FILE *__restrict __stream) throw ();




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 **__restrict __bufloc,
                             size_t *__restrict __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, ...) throw ();

extern int printf (__const char *__restrict __format, ...) throw ();

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) throw ();

extern int vprintf (__const char *__restrict __format, __gnuc_va_list __arg)
     throw ();

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)
     throw () __attribute__ ((__format__ (__printf__, 2, 0)));
extern int dprintf (int __fd, __const char *__restrict __fmt, ...)
     throw () __attribute__ ((__format__ (__printf__, 2, 3)));




extern int fscanf (FILE *__restrict __stream,
                   __const char *__restrict __format, ...) throw ();

extern int scanf (__const char *__restrict __format, ...) throw ();

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)
     throw () __attribute__ ((__format__ (__scanf__, 2, 0)));


extern int vscanf (__const char *__restrict __format, __gnuc_va_list __arg)
     throw () __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) throw ();
extern int getc (FILE *__stream) throw ();


extern int getchar (void) throw ();







extern int getc_unlocked (FILE *__stream) throw ();
extern int getchar_unlocked (void) throw ();




extern int fgetc_unlocked (FILE *__stream) throw ();




extern int fputc (int __c, FILE *__stream) throw ();
extern int putc (int __c, FILE *__stream) throw ();


extern int putchar (int __c) throw ();







extern int fputc_unlocked (int __c, FILE *__stream) throw ();




extern int putc_unlocked (int __c, FILE *__stream) throw ();
extern int putchar_unlocked (int __c) throw ();





extern int getw (FILE *__stream) throw ();


extern int putw (int __w, FILE *__stream) throw ();




extern char *fgets (char *__restrict __s, int __n, FILE *__restrict __stream)
     throw ();



extern char *fgets_unlocked (char *__restrict __s, int __n,
                             FILE *__restrict __stream) throw ();




extern char *gets (char *__s) throw ();
# 435 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
extern __ssize_t __getdelim (char **__restrict __lineptr,
                               size_t *__restrict __n, int __delimiter,
                               FILE *__restrict __stream) throw ();
extern __ssize_t getdelim (char **__restrict __lineptr,
                             size_t *__restrict __n, int __delimiter,
                             FILE *__restrict __stream) throw ();


extern __ssize_t getline (char **__restrict __lineptr,
                            size_t *__restrict __n,
                            FILE *__restrict __stream) throw ();




extern int fputs (__const char *__restrict __s, FILE *__restrict __stream)
     throw ();



extern int fputs_unlocked (__const char *__restrict __s,
                           FILE *__restrict __stream) throw ();



extern int puts (__const char *__s) throw ();



extern int ungetc (int __c, FILE *__stream) throw ();



extern size_t fread (void *__restrict __ptr, size_t __size,
                     size_t __n, FILE *__restrict __stream) throw ();

extern size_t fwrite (__const void *__restrict __ptr, size_t __size,
                      size_t __n, FILE *__restrict __s) throw ();



extern size_t fread_unlocked (void *__restrict __ptr, size_t __size,
                              size_t __n, FILE *__restrict __stream) throw ();
extern size_t fwrite_unlocked (__const void *__restrict __ptr, size_t __size,
                               size_t __n, FILE *__restrict __stream) throw ();




extern int fseek (FILE *__stream, long int __off, int __whence) throw ();

extern long int ftell (FILE *__stream) throw ();

extern void rewind (FILE *__stream) throw ();
# 498 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
extern int fseeko (FILE *__stream, __off_t __off, int __whence) throw ();

extern __off_t ftello (FILE *__stream) throw ();



extern int fgetpos (FILE *__restrict __stream, fpos_t *__restrict __pos)
     throw ();

extern int fsetpos (FILE *__stream, __const fpos_t *__pos) throw ();
# 532 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
extern int fseeko64 (FILE *__stream, __off64_t __off, int __whence) throw ();
extern __off64_t ftello64 (FILE *__stream) throw ();
extern int fgetpos64 (FILE *__restrict __stream, fpos64_t *__restrict __pos)
     throw ();
extern int fsetpos64 (FILE *__stream, __const fpos64_t *__pos) throw ();



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) throw ();




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) throw ();


extern int pclose (FILE *__stream) throw ();





extern char *ctermid (char *__s) throw ();





extern char *cuserid (char *__s) throw ();




struct obstack;


extern int obstack_printf (struct obstack *__restrict __obstack,
                           __const char *__restrict __format, ...) throw ();
extern int obstack_vprintf (struct obstack *__restrict __obstack,
                            __const char *__restrict __format,
                            __gnuc_va_list __args) throw ();







extern void flockfile (FILE *__stream) throw ();



extern int ftrylockfile (FILE *__stream) throw ();


extern void funlockfile (FILE *__stream) throw ();
# 642 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 3
}
# 42 "/usr/include/g++-v3/bits/std_cstdio.h" 2 3
# 86 "/usr/include/g++-v3/bits/std_cstdio.h" 3
namespace std
{
  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;
}
# 142 "/usr/include/g++-v3/bits/std_cstdio.h" 3
namespace __gnu_cxx
{
  using ::snprintf;
  using ::vfscanf;
  using ::vscanf;
  using ::vsnprintf;
  using ::vsscanf;
}

namespace std
{
  using __gnu_cxx::snprintf;
  using __gnu_cxx::vfscanf;
  using __gnu_cxx::vscanf;
  using __gnu_cxx::vsnprintf;
  using __gnu_cxx::vsscanf;
}
# 32 "/usr/include/g++-v3/cstdio" 2 3
# 36 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++io.h" 2 3
# 1 "/usr/include/g++-v3/cstddef" 1 3
# 37 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++io.h" 2 3
# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/gthr.h" 1 3
# 98 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/gthr.h" 3
# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/gthr-default.h" 1 3
# 37 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/gthr-default.h" 3
# 1 "/usr/include/pthread.h" 1 3
# 18 "/usr/include/pthread.h" 3
# 1 "/usr/include/features.h" 1 3
# 19 "/usr/include/pthread.h" 2 3

# 1 "/usr/include/sched.h" 1 3
# 23 "/usr/include/sched.h" 3
# 1 "/usr/include/features.h" 1 3
# 24 "/usr/include/sched.h" 2 3


# 1 "/usr/include/bits/types.h" 1 3
# 27 "/usr/include/sched.h" 2 3


# 1 "/usr/include/time.h" 1 3
# 30 "/usr/include/sched.h" 2 3


# 1 "/usr/include/bits/sched.h" 1 3
# 47 "/usr/include/bits/sched.h" 3
struct sched_param
  {
    int __sched_priority;
  };

extern "C" {



extern int clone (int (*__fn) (void *__arg), void *__child_stack,
                  int __flags, void *__arg) throw ();


}
# 33 "/usr/include/sched.h" 2 3




extern "C" {


extern int sched_setparam (__pid_t __pid, __const struct sched_param *__param)
     throw ();


extern int sched_getparam (__pid_t __pid, struct sched_param *__param) throw ();


extern int sched_setscheduler (__pid_t __pid, int __policy,
                               __const struct sched_param *__param) throw ();


extern int sched_getscheduler (__pid_t __pid) throw ();


extern int sched_yield (void) throw ();


extern int sched_get_priority_max (int __algorithm) throw ();


extern int sched_get_priority_min (int __algorithm) throw ();


extern int sched_rr_get_interval (__pid_t __pid, struct timespec *__t) throw ();

}
# 21 "/usr/include/pthread.h" 2 3
# 1 "/usr/include/time.h" 1 3
# 28 "/usr/include/time.h" 3
# 1 "/usr/include/features.h" 1 3
# 29 "/usr/include/time.h" 2 3

extern "C" {







# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 39 "/usr/include/time.h" 2 3



# 1 "/usr/include/bits/time.h" 1 3
# 43 "/usr/include/time.h" 2 3
# 118 "/usr/include/time.h" 3
struct tm
{
  int tm_sec;
  int tm_min;
  int tm_hour;
  int tm_mday;
  int tm_mon;
  int tm_year;
  int tm_wday;
  int tm_yday;
  int tm_isdst;


  long int tm_gmtoff;
  __const char *tm_zone;




};




struct itimerspec
  {
    struct timespec it_interval;
    struct timespec it_value;
  };


struct sigevent;
# 163 "/usr/include/time.h" 3
extern clock_t clock (void) throw ();


extern time_t time (time_t *__timer) throw ();


extern double difftime (time_t __time1, time_t __time0)
     throw () __attribute__ ((__const__));


extern time_t mktime (struct tm *__tp) throw ();





extern size_t strftime (char *__restrict __s, size_t __maxsize,
                        __const char *__restrict __format,
                        __const struct tm *__restrict __tp) throw ();




extern char *strptime (__const char *__restrict __s,
                       __const char *__restrict __fmt, struct tm *__tp)
     throw ();





extern struct tm *gmtime (__const time_t *__timer) throw ();



extern struct tm *localtime (__const time_t *__timer) throw ();




extern struct tm *gmtime_r (__const time_t *__restrict __timer,
                            struct tm *__restrict __tp) throw ();



extern struct tm *localtime_r (__const time_t *__restrict __timer,
                               struct tm *__restrict __tp) throw ();




extern char *asctime (__const struct tm *__tp) throw ();


extern char *ctime (__const time_t *__timer) throw ();






extern char *asctime_r (__const struct tm *__restrict __tp,
                        char *__restrict __buf) throw ();


extern char *ctime_r (__const time_t *__restrict __timer,
                      char *__restrict __buf) throw ();




extern char *__tzname[2];
extern int __daylight;
extern long int __timezone;




extern char *tzname[2];



extern void tzset (void) throw ();



extern int daylight;
extern long int timezone;





extern int stime (__const time_t *__when) throw ();
# 271 "/usr/include/time.h" 3
extern time_t timegm (struct tm *__tp) throw ();


extern time_t timelocal (struct tm *__tp) throw ();


extern int dysize (int __year) throw () __attribute__ ((__const__));





extern int nanosleep (__const struct timespec *__requested_time,
                      struct timespec *__remaining) throw ();



extern int clock_getres (clockid_t __clock_id, struct timespec *__res) throw ();


extern int clock_gettime (clockid_t __clock_id, struct timespec *__tp) throw ();


extern int clock_settime (clockid_t __clock_id, __const struct timespec *__tp)
     throw ();



extern int clock_nanosleep (clockid_t __clock_id, int __flags,
                            __const struct timespec *__req,
                            struct timespec *__rem) throw ();


extern int clock_getcpuclockid (pid_t __pid, clockid_t *__clock_id) throw ();




extern int timer_create (clockid_t __clock_id,
                         struct sigevent *__restrict __evp,
                         timer_t *__restrict __timerid) throw ();


extern int timer_delete (timer_t __timerid) throw ();


extern int timer_settime (timer_t __timerid, int __flags,
                          __const struct itimerspec *__restrict __value,
                          struct itimerspec *__restrict __ovalue) throw ();


extern int timer_gettime (timer_t __timerid, struct itimerspec *__value)
     throw ();


extern int timer_getoverrun (timer_t __timerid) throw ();
# 342 "/usr/include/time.h" 3
extern int getdate_err;





extern struct tm *getdate (__const char *__string) throw ();
# 357 "/usr/include/time.h" 3
extern int getdate_r (__const char *__restrict __string,
                      struct tm *__restrict __resbufp) throw ();



}
# 22 "/usr/include/pthread.h" 2 3


# 1 "/usr/include/signal.h" 1 3
# 29 "/usr/include/signal.h" 3
# 1 "/usr/include/features.h" 1 3
# 30 "/usr/include/signal.h" 2 3

extern "C" {

# 1 "/usr/include/bits/sigset.h" 1 3
# 34 "/usr/include/signal.h" 2 3
# 371 "/usr/include/signal.h" 3
}
# 25 "/usr/include/pthread.h" 2 3
# 1 "/usr/include/bits/pthreadtypes.h" 1 3
# 26 "/usr/include/pthread.h" 2 3
# 1 "/usr/include/bits/initspin.h" 1 3
# 27 "/usr/include/pthread.h" 2 3


extern "C" {
# 59 "/usr/include/pthread.h" 3
enum
{
  PTHREAD_CREATE_JOINABLE,

  PTHREAD_CREATE_DETACHED

};

enum
{
  PTHREAD_INHERIT_SCHED,

  PTHREAD_EXPLICIT_SCHED

};

enum
{
  PTHREAD_SCOPE_SYSTEM,

  PTHREAD_SCOPE_PROCESS

};

enum
{
  PTHREAD_MUTEX_TIMED_NP,
  PTHREAD_MUTEX_RECURSIVE_NP,
  PTHREAD_MUTEX_ERRORCHECK_NP,
  PTHREAD_MUTEX_ADAPTIVE_NP

  ,
  PTHREAD_MUTEX_NORMAL = PTHREAD_MUTEX_TIMED_NP,
  PTHREAD_MUTEX_RECURSIVE = PTHREAD_MUTEX_RECURSIVE_NP,
  PTHREAD_MUTEX_ERRORCHECK = PTHREAD_MUTEX_ERRORCHECK_NP,
  PTHREAD_MUTEX_DEFAULT = PTHREAD_MUTEX_NORMAL



  , PTHREAD_MUTEX_FAST_NP = PTHREAD_MUTEX_ADAPTIVE_NP

};

enum
{
  PTHREAD_PROCESS_PRIVATE,

  PTHREAD_PROCESS_SHARED

};


enum
{
  PTHREAD_RWLOCK_PREFER_READER_NP,
  PTHREAD_RWLOCK_PREFER_WRITER_NP,
  PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP,
  PTHREAD_RWLOCK_DEFAULT_NP = PTHREAD_RWLOCK_PREFER_WRITER_NP
};
# 131 "/usr/include/pthread.h" 3
struct _pthread_cleanup_buffer
{
  void (*__routine) (void *);
  void *__arg;
  int __canceltype;
  struct _pthread_cleanup_buffer *__prev;
};



enum
{
  PTHREAD_CANCEL_ENABLE,

  PTHREAD_CANCEL_DISABLE

};
enum
{
  PTHREAD_CANCEL_DEFERRED,

  PTHREAD_CANCEL_ASYNCHRONOUS

};
# 163 "/usr/include/pthread.h" 3
extern int pthread_create (pthread_t *__restrict __thread,
                           __const pthread_attr_t *__restrict __attr,
                           void *(*__start_routine) (void *),
                           void *__restrict __arg) throw ();


extern pthread_t pthread_self (void) throw ();


extern int pthread_equal (pthread_t __thread1, pthread_t __thread2) throw ();


extern void pthread_exit (void *__retval)
     throw () __attribute__ ((__noreturn__));




extern int pthread_join (pthread_t __th, void **__thread_return) throw ();





extern int pthread_detach (pthread_t __th) throw ();







extern int pthread_attr_init (pthread_attr_t *__attr) throw ();


extern int pthread_attr_destroy (pthread_attr_t *__attr) throw ();


extern int pthread_attr_setdetachstate (pthread_attr_t *__attr,
                                        int __detachstate) throw ();


extern int pthread_attr_getdetachstate (__const pthread_attr_t *__attr,
                                        int *__detachstate) throw ();


extern int pthread_attr_setschedparam (pthread_attr_t *__restrict __attr,
                                       __const struct sched_param *__restrict
                                       __param) throw ();


extern int pthread_attr_getschedparam (__const pthread_attr_t *__restrict
                                       __attr,
                                       struct sched_param *__restrict __param)
     throw ();


extern int pthread_attr_setschedpolicy (pthread_attr_t *__attr, int __policy)
     throw ();


extern int pthread_attr_getschedpolicy (__const pthread_attr_t *__restrict
                                        __attr, int *__restrict __policy)
     throw ();


extern int pthread_attr_setinheritsched (pthread_attr_t *__attr,
                                         int __inherit) throw ();


extern int pthread_attr_getinheritsched (__const pthread_attr_t *__restrict
                                         __attr, int *__restrict __inherit)
     throw ();


extern int pthread_attr_setscope (pthread_attr_t *__attr, int __scope)
     throw ();


extern int pthread_attr_getscope (__const pthread_attr_t *__restrict __attr,
                                  int *__restrict __scope) throw ();



extern int pthread_attr_setguardsize (pthread_attr_t *__attr,
                                      size_t __guardsize) throw ();


extern int pthread_attr_getguardsize (__const pthread_attr_t *__restrict
                                      __attr, size_t *__restrict __guardsize)
     throw ();






extern int pthread_attr_setstackaddr (pthread_attr_t *__attr,
                                      void *__stackaddr) throw ();


extern int pthread_attr_getstackaddr (__const pthread_attr_t *__restrict
                                      __attr, void **__restrict __stackaddr)
     throw ();





extern int pthread_attr_setstack (pthread_attr_t *__attr, void *__stackaddr,
                                  size_t __stacksize) throw ();


extern int pthread_attr_getstack (__const pthread_attr_t *__restrict __attr,
                                  void **__restrict __stackaddr,
                                  size_t *__restrict __stacksize) throw ();





extern int pthread_attr_setstacksize (pthread_attr_t *__attr,
                                      size_t __stacksize) throw ();


extern int pthread_attr_getstacksize (__const pthread_attr_t *__restrict
                                      __attr, size_t *__restrict __stacksize)
     throw ();



extern int pthread_getattr_np (pthread_t __th, pthread_attr_t *__attr) throw ();






extern int pthread_setschedparam (pthread_t __target_thread, int __policy,
                                  __const struct sched_param *__param)
     throw ();


extern int pthread_getschedparam (pthread_t __target_thread,
                                  int *__restrict __policy,
                                  struct sched_param *__restrict __param)
     throw ();



extern int pthread_getconcurrency (void) throw ();


extern int pthread_setconcurrency (int __level) throw ();







extern int pthread_yield (void) throw ();






extern int pthread_mutex_init (pthread_mutex_t *__restrict __mutex,
                               __const pthread_mutexattr_t *__restrict
                               __mutex_attr) throw ();


extern int pthread_mutex_destroy (pthread_mutex_t *__mutex) throw ();


extern int pthread_mutex_trylock (pthread_mutex_t *__mutex) throw ();


extern int pthread_mutex_lock (pthread_mutex_t *__mutex) throw ();



extern int pthread_mutex_timedlock (pthread_mutex_t *__restrict __mutex,
                                    __const struct timespec *__restrict
                                    __abstime) throw ();



extern int pthread_mutex_unlock (pthread_mutex_t *__mutex) throw ();






extern int pthread_mutexattr_init (pthread_mutexattr_t *__attr) throw ();


extern int pthread_mutexattr_destroy (pthread_mutexattr_t *__attr) throw ();


extern int pthread_mutexattr_getpshared (__const pthread_mutexattr_t *
                                         __restrict __attr,
                                         int *__restrict __pshared) throw ();


extern int pthread_mutexattr_setpshared (pthread_mutexattr_t *__attr,
                                         int __pshared) throw ();





extern int pthread_mutexattr_settype (pthread_mutexattr_t *__attr, int __kind)
     throw ();


extern int pthread_mutexattr_gettype (__const pthread_mutexattr_t *__restrict
                                      __attr, int *__restrict __kind) throw ();







extern int pthread_cond_init (pthread_cond_t *__restrict __cond,
                              __const pthread_condattr_t *__restrict
                              __cond_attr) throw ();


extern int pthread_cond_destroy (pthread_cond_t *__cond) throw ();


extern int pthread_cond_signal (pthread_cond_t *__cond) throw ();


extern int pthread_cond_broadcast (pthread_cond_t *__cond) throw ();



extern int pthread_cond_wait (pthread_cond_t *__restrict __cond,
                              pthread_mutex_t *__restrict __mutex) throw ();





extern int pthread_cond_timedwait (pthread_cond_t *__restrict __cond,
                                   pthread_mutex_t *__restrict __mutex,
                                   __const struct timespec *__restrict
                                   __abstime) throw ();




extern int pthread_condattr_init (pthread_condattr_t *__attr) throw ();


extern int pthread_condattr_destroy (pthread_condattr_t *__attr) throw ();


extern int pthread_condattr_getpshared (__const pthread_condattr_t *
                                        __restrict __attr,
                                        int *__restrict __pshared) throw ();


extern int pthread_condattr_setpshared (pthread_condattr_t *__attr,
                                        int __pshared) throw ();







extern int pthread_rwlock_init (pthread_rwlock_t *__restrict __rwlock,
                                __const pthread_rwlockattr_t *__restrict
                                __attr) throw ();


extern int pthread_rwlock_destroy (pthread_rwlock_t *__rwlock) throw ();


extern int pthread_rwlock_rdlock (pthread_rwlock_t *__rwlock) throw ();


extern int pthread_rwlock_tryrdlock (pthread_rwlock_t *__rwlock) throw ();



extern int pthread_rwlock_timedrdlock (pthread_rwlock_t *__restrict __rwlock,
                                       __const struct timespec *__restrict
                                       __abstime) throw ();



extern int pthread_rwlock_wrlock (pthread_rwlock_t *__rwlock) throw ();


extern int pthread_rwlock_trywrlock (pthread_rwlock_t *__rwlock) throw ();



extern int pthread_rwlock_timedwrlock (pthread_rwlock_t *__restrict __rwlock,
                                       __const struct timespec *__restrict
                                       __abstime) throw ();



extern int pthread_rwlock_unlock (pthread_rwlock_t *__rwlock) throw ();





extern int pthread_rwlockattr_init (pthread_rwlockattr_t *__attr) throw ();


extern int pthread_rwlockattr_destroy (pthread_rwlockattr_t *__attr) throw ();


extern int pthread_rwlockattr_getpshared (__const pthread_rwlockattr_t *
                                          __restrict __attr,
                                          int *__restrict __pshared) throw ();


extern int pthread_rwlockattr_setpshared (pthread_rwlockattr_t *__attr,
                                          int __pshared) throw ();


extern int pthread_rwlockattr_getkind_np (__const pthread_rwlockattr_t *__attr,
                                          int *__pref) throw ();


extern int pthread_rwlockattr_setkind_np (pthread_rwlockattr_t *__attr,
                                          int __pref) throw ();
# 509 "/usr/include/pthread.h" 3
extern int pthread_spin_init (pthread_spinlock_t *__lock, int __pshared)
     throw ();


extern int pthread_spin_destroy (pthread_spinlock_t *__lock) throw ();


extern int pthread_spin_lock (pthread_spinlock_t *__lock) throw ();


extern int pthread_spin_trylock (pthread_spinlock_t *__lock) throw ();


extern int pthread_spin_unlock (pthread_spinlock_t *__lock) throw ();




extern int pthread_barrier_init (pthread_barrier_t *__restrict __barrier,
                                 __const pthread_barrierattr_t *__restrict
                                 __attr, unsigned int __count) throw ();

extern int pthread_barrier_destroy (pthread_barrier_t *__barrier) throw ();

extern int pthread_barrierattr_init (pthread_barrierattr_t *__attr) throw ();

extern int pthread_barrierattr_destroy (pthread_barrierattr_t *__attr) throw ();

extern int pthread_barrierattr_getpshared (__const pthread_barrierattr_t *
                                           __restrict __attr,
                                           int *__restrict __pshared) throw ();

extern int pthread_barrierattr_setpshared (pthread_barrierattr_t *__attr,
                                           int __pshared) throw ();

extern int pthread_barrier_wait (pthread_barrier_t *__barrier) throw ();
# 556 "/usr/include/pthread.h" 3
extern int pthread_key_create (pthread_key_t *__key,
                               void (*__destr_function) (void *)) throw ();


extern int pthread_key_delete (pthread_key_t __key) throw ();


extern int pthread_setspecific (pthread_key_t __key,
                                __const void *__pointer) throw ();


extern void *pthread_getspecific (pthread_key_t __key) throw ();
# 576 "/usr/include/pthread.h" 3
extern int pthread_once (pthread_once_t *__once_control,
                         void (*__init_routine) (void)) throw ();






extern int pthread_setcancelstate (int __state, int *__oldstate) throw ();



extern int pthread_setcanceltype (int __type, int *__oldtype) throw ();


extern int pthread_cancel (pthread_t __thread) throw ();




extern void pthread_testcancel (void) throw ();
# 610 "/usr/include/pthread.h" 3
extern void _pthread_cleanup_push (struct _pthread_cleanup_buffer *__buffer,
                                   void (*__routine) (void *),
                                   void *__arg) throw ();







extern void _pthread_cleanup_pop (struct _pthread_cleanup_buffer *__buffer,
                                  int __execute) throw ();
# 631 "/usr/include/pthread.h" 3
extern void _pthread_cleanup_push_defer (struct _pthread_cleanup_buffer *__buffer,
                                         void (*__routine) (void *),
                                         void *__arg) throw ();
# 642 "/usr/include/pthread.h" 3
extern void _pthread_cleanup_pop_restore (struct _pthread_cleanup_buffer *__buffer,
                                          int __execute) throw ();





extern int pthread_getcpuclockid (pthread_t __thread_id,
                                  clockid_t *__clock_id) throw ();




# 1 "/usr/include/bits/sigthread.h" 1 3
# 31 "/usr/include/bits/sigthread.h" 3
extern int pthread_sigmask (int __how,
                            __const __sigset_t *__restrict __newmask,
                            __sigset_t *__restrict __oldmask)throw ();


extern int pthread_kill (pthread_t __thread, int __signo) throw ();
# 656 "/usr/include/pthread.h" 2 3
# 671 "/usr/include/pthread.h" 3
extern int pthread_atfork (void (*__prepare) (void),
                           void (*__parent) (void),
                           void (*__child) (void)) throw ();




extern void pthread_kill_other_threads_np (void) throw ();

}
# 38 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/gthr-default.h" 2 3

typedef pthread_key_t __gthread_key_t;
typedef pthread_once_t __gthread_once_t;
typedef pthread_mutex_t __gthread_mutex_t;






#pragma weak pthread_once
#pragma weak pthread_key_create
#pragma weak pthread_key_delete
#pragma weak pthread_getspecific
#pragma weak pthread_setspecific
#pragma weak pthread_create

#pragma weak pthread_mutex_lock
#pragma weak pthread_mutex_trylock
#pragma weak pthread_mutex_unlock
# 80 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/gthr-default.h" 3
static void *__gthread_active_ptr = (void *) &pthread_create;

static inline int
__gthread_active_p (void)
{
  return __gthread_active_ptr != 0;
}
# 438 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/gthr-default.h" 3
static inline int
__gthread_once (__gthread_once_t *once, void (*func) (void))
{
  if (__gthread_active_p ())
    return pthread_once (once, func);
  else
    return -1;
}

static inline int
__gthread_key_create (__gthread_key_t *key, void (*dtor) (void *))
{
  return pthread_key_create (key, dtor);
}

static inline int
__gthread_key_dtor (__gthread_key_t key, void *ptr)
{

  if (ptr)
    return pthread_setspecific (key, 0);
  else
    return 0;
}

static inline int
__gthread_key_delete (__gthread_key_t key)
{
  return pthread_key_delete (key);
}

static inline void *
__gthread_getspecific (__gthread_key_t key)
{
  return pthread_getspecific (key);
}

static inline int
__gthread_setspecific (__gthread_key_t key, const void *ptr)
{
  return pthread_setspecific (key, ptr);
}

static inline int
__gthread_mutex_lock (__gthread_mutex_t *mutex)
{
  if (__gthread_active_p ())
    return pthread_mutex_lock (mutex);
  else
    return 0;
}

static inline int
__gthread_mutex_trylock (__gthread_mutex_t *mutex)
{
  if (__gthread_active_p ())
    return pthread_mutex_trylock (mutex);
  else
    return 0;
}

static inline int
__gthread_mutex_unlock (__gthread_mutex_t *mutex)
{
  if (__gthread_active_p ())
    return pthread_mutex_unlock (mutex);
  else
    return 0;
}
# 99 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/gthr.h" 2 3
# 38 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++io.h" 2 3

namespace std
{

  typedef long streamoff;
  typedef ptrdiff_t streamsize;

  typedef ptrdiff_t wstreamsize;

  typedef fpos_t __c_streampos;

  typedef __gthread_mutex_t __c_lock;



  typedef FILE __c_file_type;


  struct __ios_flags
  {
    typedef short __int_type;

    static const __int_type _S_boolalpha = 0x0001;
    static const __int_type _S_dec = 0x0002;
    static const __int_type _S_fixed = 0x0004;
    static const __int_type _S_hex = 0x0008;
    static const __int_type _S_internal = 0x0010;
    static const __int_type _S_left = 0x0020;
    static const __int_type _S_oct = 0x0040;
    static const __int_type _S_right = 0x0080;
    static const __int_type _S_scientific = 0x0100;
    static const __int_type _S_showbase = 0x0200;
    static const __int_type _S_showpoint = 0x0400;
    static const __int_type _S_showpos = 0x0800;
    static const __int_type _S_skipws = 0x1000;
    static const __int_type _S_unitbuf = 0x2000;
    static const __int_type _S_uppercase = 0x4000;
    static const __int_type _S_adjustfield = 0x0020 | 0x0080 | 0x0010;
    static const __int_type _S_basefield = 0x0002 | 0x0040 | 0x0008;
    static const __int_type _S_floatfield = 0x0100 | 0x0004;


    static const __int_type _S_badbit = 0x01;
    static const __int_type _S_eofbit = 0x02;
    static const __int_type _S_failbit = 0x04;


    static const __int_type _S_app = 0x01;
    static const __int_type _S_ate = 0x02;
    static const __int_type _S_bin = 0x04;
    static const __int_type _S_in = 0x08;
    static const __int_type _S_out = 0x10;
    static const __int_type _S_trunc = 0x20;
  };
}
# 40 "/usr/include/g++-v3/bits/fpos.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_cwchar.h" 1 3
# 37 "/usr/include/g++-v3/bits/std_cwchar.h" 3
# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 1 3
# 38 "/usr/include/g++-v3/bits/std_cwchar.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_cstddef.h" 1 3
# 39 "/usr/include/g++-v3/bits/std_cwchar.h" 2 3
# 42 "/usr/include/g++-v3/bits/std_cwchar.h" 3
# 1 "/usr/include/wchar.h" 1 3
# 28 "/usr/include/wchar.h" 3
# 1 "/usr/include/features.h" 1 3
# 29 "/usr/include/wchar.h" 2 3
# 37 "/usr/include/wchar.h" 3
# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdio.h" 1 3
# 38 "/usr/include/wchar.h" 2 3


# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stdarg.h" 1 3
# 41 "/usr/include/wchar.h" 2 3







# 1 "/usr/lib/gcc-lib/i686-pc-linux-gnu/3.0.1/include/stddef.h" 1 3
# 49 "/usr/include/wchar.h" 2 3

# 1 "/usr/include/bits/wchar.h" 1 3
# 51 "/usr/include/wchar.h" 2 3
# 85 "/usr/include/wchar.h" 3
typedef __mbstate_t mbstate_t;
# 105 "/usr/include/wchar.h" 3
struct tm;


extern "C" {


extern wchar_t *wcscpy (wchar_t *__restrict __dest,
                        __const wchar_t *__restrict __src) throw ();

extern wchar_t *wcsncpy (wchar_t *__restrict __dest,
                         __const wchar_t *__restrict __src, size_t __n)
     throw ();


extern wchar_t *wcscat (wchar_t *__restrict __dest,
                        __const wchar_t *__restrict __src) throw ();

extern wchar_t *wcsncat (wchar_t *__restrict __dest,
                         __const wchar_t *__restrict __src, size_t __n)
     throw ();


extern int wcscmp (__const wchar_t *__s1, __const wchar_t *__s2)
     throw () __attribute__ ((__pure__));

extern int wcsncmp (__const wchar_t *__s1, __const wchar_t *__s2, size_t __n)
     throw () __attribute__ ((__pure__));



extern int wcscasecmp (__const wchar_t *__s1, __const wchar_t *__s2) throw ();


extern int wcsncasecmp (__const wchar_t *__s1, __const wchar_t *__s2,
                        size_t __n) throw ();



# 1 "/usr/include/xlocale.h" 1 3
# 144 "/usr/include/wchar.h" 2 3

extern int __wcscasecmp_l (__const wchar_t *__s1, __const wchar_t *__s2,
                           __locale_t __loc) throw ();

extern int __wcsncasecmp_l (__const wchar_t *__s1, __const wchar_t *__s2,
                            size_t __n, __locale_t __loc) throw ();




extern int wcscoll (__const wchar_t *__s1, __const wchar_t *__s2) throw ();



extern size_t wcsxfrm (wchar_t *__restrict __s1,
                       __const wchar_t *__restrict __s2, size_t __n) throw ();







extern int __wcscoll_l (__const wchar_t *__s1, __const wchar_t *__s2,
                        __locale_t __loc) throw ();



extern size_t __wcsxfrm_l (wchar_t *__s1, __const wchar_t *__s2,
                           size_t __n, __locale_t __loc) throw ();


extern wchar_t *wcsdup (__const wchar_t *__s) throw () __attribute__ ((__malloc__));



extern wchar_t *wcschr (__const wchar_t *__wcs, wchar_t __wc)
     throw () __attribute__ ((__pure__));

extern wchar_t *wcsrchr (__const wchar_t *__wcs, wchar_t __wc)
     throw () __attribute__ ((__pure__));




extern wchar_t *wcschrnul (__const wchar_t *__s, wchar_t __wc)
     throw () __attribute__ ((__pure__));




extern size_t wcscspn (__const wchar_t *__wcs, __const wchar_t *__reject)
     throw () __attribute__ ((__pure__));


extern size_t wcsspn (__const wchar_t *__wcs, __const wchar_t *__accept)
     throw () __attribute__ ((__pure__));

extern wchar_t *wcspbrk (__const wchar_t *__wcs, __const wchar_t *__accept)
     throw () __attribute__ ((__pure__));

extern wchar_t *wcsstr (__const wchar_t *__haystack, __const wchar_t *__needle)
     throw () __attribute__ ((__pure__));



extern wchar_t *wcswcs (__const wchar_t *__haystack, __const wchar_t *__needle)
     throw () __attribute__ ((__pure__));



extern wchar_t *wcstok (wchar_t *__restrict __s,
                        __const wchar_t *__restrict __delim,
                        wchar_t **__restrict __ptr) throw ();


extern size_t wcslen (__const wchar_t *__s) throw () __attribute__ ((__pure__));



extern size_t wcsnlen (__const wchar_t *__s, size_t __maxlen)
     throw () __attribute__ ((__pure__));




extern wchar_t *wmemchr (__const wchar_t *__s, wchar_t __c, size_t __n)
     throw () __attribute__ ((__pure__));


extern int wmemcmp (__const wchar_t *__restrict __s1,
                    __const wchar_t *__restrict __s2, size_t __n)
     throw () __attribute__ ((__pure__));


extern wchar_t *wmemcpy (wchar_t *__restrict __s1,
                         __const wchar_t *__restrict __s2, size_t __n) throw ();



extern wchar_t *wmemmove (wchar_t *__s1, __const wchar_t *__s2, size_t __n)
     throw ();


extern wchar_t *wmemset (wchar_t *__s, wchar_t __c, size_t __n) throw ();




extern wchar_t *wmempcpy (wchar_t *__restrict __s1,
                          __const wchar_t *__restrict __s2, size_t __n)
     throw ();





extern wint_t btowc (int __c) throw ();



extern int wctob (wint_t __c) throw ();



extern int mbsinit (__const mbstate_t *__ps) throw ();



extern size_t mbrtowc (wchar_t *__restrict __pwc,
                       __const char *__restrict __s, size_t __n,
                       mbstate_t *__p) throw ();


extern size_t wcrtomb (char *__restrict __s, wchar_t __wc,
                       mbstate_t *__restrict __ps) throw ();


extern size_t __mbrlen (__const char *__restrict __s, size_t __n,
                        mbstate_t *__restrict __ps) throw ();
extern size_t mbrlen (__const char *__restrict __s, size_t __n,
                      mbstate_t *__restrict __ps) throw ();
# 297 "/usr/include/wchar.h" 3
extern size_t mbsrtowcs (wchar_t *__restrict __dst,
                         __const char **__restrict __src, size_t __len,
                         mbstate_t *__restrict __ps) throw ();



extern size_t wcsrtombs (char *__restrict __dst,
                         __const wchar_t **__restrict __src, size_t __len,
                         mbstate_t *__restrict __ps) throw ();





extern size_t mbsnrtowcs (wchar_t *__restrict __dst,
                          __const char **__restrict __src, size_t __nmc,
                          size_t __len, mbstate_t *__restrict __ps) throw ();



extern size_t wcsnrtombs (char *__restrict __dst,
                          __const wchar_t **__restrict __src,
                          size_t __nwc, size_t __len,
                          mbstate_t *__restrict __ps) throw ();






extern int wcwidth (wint_t __c) throw ();



extern int wcswidth (__const wchar_t *__s, size_t __n) throw ();





extern double wcstod (__const wchar_t *__restrict __nptr,
                      wchar_t **__restrict __endptr) throw ();



extern float wcstof (__const wchar_t *__restrict __nptr,
                     wchar_t **__restrict __endptr) throw ();
extern long double wcstold (__const wchar_t *__restrict __nptr,
                            wchar_t **__restrict __endptr) throw ();





extern long int wcstol (__const wchar_t *__restrict __nptr,
                        wchar_t **__restrict __endptr, int __base) throw ();



extern unsigned long int wcstoul (__const wchar_t *__restrict __nptr,
                                  wchar_t **__restrict __endptr, int __base)
     throw ();




__extension__
extern long long int wcstoq (__const wchar_t *__restrict __nptr,
                             wchar_t **__restrict __endptr, int __base)
     throw ();



__extension__
extern unsigned long long int wcstouq (__const wchar_t *__restrict __nptr,
                                       wchar_t **__restrict __endptr,
                                       int __base) throw ();





__extension__
extern long long int wcstoll (__const wchar_t *__restrict __nptr,
                              wchar_t **__restrict __endptr, int __base)
     throw ();



__extension__
extern unsigned long long int wcstoull (__const wchar_t *__restrict __nptr,
                                        wchar_t **__restrict __endptr,
                                        int __base) throw ();
# 406 "/usr/include/wchar.h" 3
# 1 "/usr/include/xlocale.h" 1 3
# 407 "/usr/include/wchar.h" 2 3



extern long int __wcstol_l (__const wchar_t *__restrict __nptr,
                            wchar_t **__restrict __endptr, int __base,
                            __locale_t __loc) throw ();

extern unsigned long int __wcstoul_l (__const wchar_t *__restrict __nptr,
                                      wchar_t **__restrict __endptr,
                                      int __base, __locale_t __loc) throw ();

__extension__
extern long long int __wcstoll_l (__const wchar_t *__restrict __nptr,
                                  wchar_t **__restrict __endptr,
                                  int __base, __locale_t __loc) throw ();

__extension__
extern unsigned long long int __wcstoull_l (__const wchar_t *__restrict __nptr,
                                            wchar_t **__restrict __endptr,
                                            int __base, __locale_t __loc)
     throw ();

extern double __wcstod_l (__const wchar_t *__restrict __nptr,
                          wchar_t **__restrict __endptr, __locale_t __loc)
     throw ();

extern float __wcstof_l (__const wchar_t *__restrict __nptr,
                         wchar_t **__restrict __endptr, __locale_t __loc)
     throw ();

extern long double __wcstold_l (__const wchar_t *__restrict __nptr,
                                wchar_t **__restrict __endptr,
                                __locale_t __loc) throw ();





extern double __wcstod_internal (__const wchar_t *__restrict __nptr,
                                 wchar_t **__restrict __endptr, int __group)
     throw ();
extern float __wcstof_internal (__const wchar_t *__restrict __nptr,
                                wchar_t **__restrict __endptr, int __group)
     throw ();
extern long double __wcstold_internal (__const wchar_t *__restrict __nptr,
                                       wchar_t **__restrict __endptr,
                                       int __group) throw ();


extern long int __wcstol_internal (__const wchar_t *__restrict __nptr,
                                   wchar_t **__restrict __endptr,
                                   int __base, int __group) throw ();



extern unsigned long int __wcstoul_internal (__const wchar_t *__restrict __npt,
                                             wchar_t **__restrict __endptr,
                                             int __base, int __group) throw ();



__extension__
extern long long int __wcstoll_internal (__const wchar_t *__restrict __nptr,
                                         wchar_t **__restrict __endptr,
                                         int __base, int __group) throw ();



__extension__
extern unsigned long long int __wcstoull_internal (__const wchar_t *
                                                   __restrict __nptr,
                                                   wchar_t **
                                                   __restrict __endptr,
                                                   int __base,
                                                   int __group) throw ();
# 528 "/usr/include/wchar.h" 3
extern wchar_t *wcpcpy (wchar_t *__dest, __const wchar_t *__src) throw ();



extern wchar_t *wcpncpy (wchar_t *__dest, __const wchar_t *__src, size_t __n)
     throw ();







extern int fwide (__FILE *__fp, int __mode) throw ();



extern int fwprintf (__FILE *__restrict __stream,
                     __const wchar_t *__restrict __format, ...)
     throw () ;

extern int wprintf (__const wchar_t *__restrict __format, ...)
     throw () ;

extern int swprintf (wchar_t *__restrict __s, size_t __n,
                     __const wchar_t *__restrict __format, ...)
     throw () ;


extern int vfwprintf (__FILE *__restrict __s,
                      __const wchar_t *__restrict __format,
                      __gnuc_va_list __arg)
     throw () ;

extern int vwprintf (__const wchar_t *__restrict __format,
                     __gnuc_va_list __arg)
     throw () ;


extern int vswprintf (wchar_t *__restrict __s, size_t __n,
                      __const wchar_t *__restrict __format,
                      __gnuc_va_list __arg)
     throw () ;



extern int fwscanf (__FILE *__restrict __stream,
                    __const wchar_t *__restrict __format, ...)
     throw () ;

extern int wscanf (__const wchar_t *__restrict __format, ...)
     throw () ;

extern int swscanf (__const wchar_t *__restrict __s,
                    __const wchar_t *__restrict __format, ...)
     throw () ;




extern int vfwscanf (__FILE *__restrict __s,
                     __const wchar_t *__restrict __format,
                     __gnuc_va_list __arg)
     throw () ;

extern int vwscanf (__const wchar_t *__restrict __format,
                    __gnuc_va_list __arg)
     throw () ;

extern int vswscanf (__const wchar_t *__restrict __s,
                     __const wchar_t *__restrict __format,
                     __gnuc_va_list __arg)
     throw () ;




extern wint_t fgetwc (__FILE *__stream) throw ();
extern wint_t getwc (__FILE *__stream) throw ();


extern wint_t getwchar (void) throw ();



extern wint_t fputwc (wchar_t __wc, __FILE *__stream) throw ();
extern wint_t putwc (wchar_t __wc, __FILE *__stream) throw ();


extern wint_t putwchar (wchar_t __wc) throw ();




extern wchar_t *fgetws (wchar_t *__restrict __ws, int __n,
                        __FILE *__restrict __stream) throw ();


extern int fputws (__const wchar_t *__restrict __ws,
                   __FILE *__restrict __stream) throw ();



extern wint_t ungetwc (wint_t __wc, __FILE *__stream) throw ();





extern wint_t getwc_unlocked (__FILE *__stream) throw ();
extern wint_t getwchar_unlocked (void) throw ();


extern wint_t fgetwc_unlocked (__FILE *__stream) throw ();


extern wint_t fputwc_unlocked (wchar_t __wc, __FILE *__stream) throw ();



extern wint_t putwc_unlocked (wchar_t __wc, __FILE *__stream) throw ();
extern wint_t putwchar_unlocked (wchar_t __wc) throw ();



extern wchar_t *fgetws_unlocked (wchar_t *__restrict __ws, int __n,
                                 __FILE *__restrict __stream) throw ();


extern int fputws_unlocked (__const wchar_t *__restrict __ws,
                            __FILE *__restrict __stream) throw ();






extern size_t wcsftime (wchar_t *__restrict __s, size_t __maxsize,
                        __const wchar_t *__restrict __format,
                        __const struct tm *__restrict __tp) throw ();
# 680 "/usr/include/wchar.h" 3
}
# 43 "/usr/include/g++-v3/bits/std_cwchar.h" 2 3
# 57 "/usr/include/g++-v3/bits/std_cwchar.h" 3
namespace std
{
  using ::mbstate_t;
}
# 121 "/usr/include/g++-v3/bits/std_cwchar.h" 3
namespace std
{
  using ::wint_t;

  using ::btowc;
  using ::fgetwc;
  using ::fgetws;
  using ::fputwc;
  using ::fputws;
  using ::fwide;
  using ::fwprintf;
  using ::fwscanf;
  using ::getwc;
  using ::getwchar;
  using ::mbrlen;
  using ::mbrtowc;
  using ::mbsinit;
  using ::mbsrtowcs;
  using ::putwc;
  using ::putwchar;
  using ::swprintf;
  using ::swscanf;
  using ::ungetwc;
  using ::vfwprintf;
  using ::vfwscanf;
  using ::vswprintf;
  using ::vswscanf;
  using ::vwprintf;
  using ::vwscanf;
  using ::wcrtomb;
  using ::wcscat;
  using ::wcscmp;
  using ::wcscoll;
  using ::wcscpy;
  using ::wcscspn;
  using ::wcsftime;
  using ::wcslen;
  using ::wcsncat;
  using ::wcsncmp;
  using ::wcsncpy;
  using ::wcsrtombs;
  using ::wcsspn;
  using ::wcstod;
  using ::wcstof;
  using ::wcstok;
  using ::wcstol;
  using ::wcstoul;
  using ::wcsxfrm;
  using ::wctob;
  using ::wmemcmp;
  using ::wmemcpy;
  using ::wmemmove;
  using ::wmemset;
  using ::wprintf;
  using ::wscanf;

  using ::wcschr;

  inline wchar_t*
  wcschr(wchar_t* __p, wchar_t __c)
  { return wcschr(const_cast<const wchar_t*>(__p), __c); }

  using ::wcspbrk;

  inline wchar_t*
  wcspbrk(wchar_t* __s1, wchar_t* __s2)
  { return wcspbrk(const_cast<const wchar_t*>(__s1), __s2); }

  using ::wcsrchr;

  inline wchar_t*
  wcsrchr(wchar_t* __p, wchar_t __c)
  { return wcsrchr(const_cast<const wchar_t*>(__p), __c); }

  using ::wcsstr;

  inline wchar_t*
  wcsstr(wchar_t* __s1, wchar_t* __s2)
  { return wcsstr(const_cast<const wchar_t*>(__s1), __s2); }

  using ::wmemchr;

  inline wchar_t*
  wmemchr(wchar_t* __p, wchar_t __c, size_t __n)
  { return wmemchr(const_cast<const wchar_t*>(__p), __c, __n); }
}







namespace __gnu_cxx
{
  using ::wcstold;
  using ::wcstoll;
  using ::wcstoull;
}

namespace std
{
  using __gnu_cxx::wcstold;
  using __gnu_cxx::wcstoll;
  using __gnu_cxx::wcstoull;
}
# 41 "/usr/include/g++-v3/bits/fpos.h" 2 3

namespace std
{



  template<typename _StateT>
    class fpos
    {
    public:

      typedef _StateT __state_type;

    private:
      streamoff _M_off;
      __state_type _M_st;

    public:
      __state_type
      state() const { return _M_st; }

      void
      state(__state_type __st) { _M_st = __st; }



      fpos(): _M_off(streamoff()), _M_st(__state_type()) { }

      fpos(streamoff __off, __state_type __st = __state_type())
      : _M_off(__off), _M_st(__st) { }

      operator streamoff() const { return _M_off; }

      fpos&
      operator+=(streamoff __off) { _M_off += __off; return *this; }

      fpos&
      operator-=(streamoff __off) { _M_off -= __off; return *this; }

      fpos
      operator+(streamoff __off)
      {
        fpos __t(*this);
        __t += __off;
        return __t;
      }

      fpos
      operator-(streamoff __off)
      {
        fpos __t(*this);
        __t -= __off;
        return __t;
      }

      bool
      operator==(const fpos& __pos) const
      { return _M_off == __pos._M_off; }

      bool
      operator!=(const fpos& __pos) const
      { return _M_off != __pos._M_off; }

      streamoff
      _M_position() const { return _M_off; }

      void
      _M_position(streamoff __off) { _M_off = __off; }
    };


  typedef fpos<mbstate_t> streampos;

  typedef fpos<mbstate_t> wstreampos;

}
# 42 "/usr/include/g++-v3/bits/std_iosfwd.h" 2 3
# 1 "/usr/include/g++-v3/bits/functexcept.h" 1 3
# 34 "/usr/include/g++-v3/bits/functexcept.h" 3
# 1 "/usr/include/g++-v3/exception_defines.h" 1 3
# 35 "/usr/include/g++-v3/bits/functexcept.h" 2 3

namespace std
{

  void
  __throw_bad_exception(void);


  void
  __throw_bad_alloc(void);


  void
  __throw_bad_cast(void);

  void
  __throw_bad_typeid(void);


  void
  __throw_logic_error(const char* __s);

  void
  __throw_domain_error(const char* __s);

  void
  __throw_invalid_argument(const char* __s);

  void
  __throw_length_error(const char* __s);

  void
  __throw_out_of_range(const char* __s);

  void
  __throw_runtime_error(const char* __s);

  void
  __throw_range_error(const char* __s);

  void
  __throw_overflow_error(const char* __s);

  void
  __throw_underflow_error(const char* __s);


  void
  __throw_ios_failure(const char* __s);
}
# 43 "/usr/include/g++-v3/bits/std_iosfwd.h" 2 3

namespace std
{
  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class basic_ios;

  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class basic_streambuf;

  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class basic_istream;

  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class basic_ostream;

  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class basic_iostream;

  template<typename _CharT, typename _Traits = char_traits<_CharT>,
            typename _Alloc = allocator<_CharT> >
    class basic_stringbuf;

  template<typename _CharT, typename _Traits = char_traits<_CharT>,
           typename _Alloc = allocator<_CharT> >
    class basic_istringstream;

  template<typename _CharT, typename _Traits = char_traits<_CharT>,
           typename _Alloc = allocator<_CharT> >
    class basic_ostringstream;

  template<typename _CharT, typename _Traits = char_traits<_CharT>,
           typename _Alloc = allocator<_CharT> >
    class basic_stringstream;

  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class basic_filebuf;

  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class basic_ifstream;

  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class basic_ofstream;

  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class basic_fstream;

  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class istreambuf_iterator;

  template<typename _CharT, typename _Traits = char_traits<_CharT> >
    class ostreambuf_iterator;



  class ios_base;


  typedef basic_ios<char> ios;
  typedef basic_streambuf<char> streambuf;
  typedef basic_istream<char> istream;
  typedef basic_ostream<char> ostream;
  typedef basic_iostream<char> iostream;
  typedef basic_stringbuf<char> stringbuf;
  typedef basic_istringstream<char> istringstream;
  typedef basic_ostringstream<char> ostringstream;
  typedef basic_stringstream<char> stringstream;
  typedef basic_filebuf<char> filebuf;
  typedef basic_ifstream<char> ifstream;
  typedef basic_ofstream<char> ofstream;
  typedef basic_fstream<char> fstream;


  typedef basic_ios<wchar_t> wios;
  typedef basic_streambuf<wchar_t> wstreambuf;
  typedef basic_istream<wchar_t> wistream;
  typedef basic_ostream<wchar_t> wostream;
  typedef basic_iostream<wchar_t> wiostream;
  typedef basic_stringbuf<wchar_t> wstringbuf;
  typedef basic_istringstream<wchar_t> wistringstream;
  typedef basic_ostringstream<wchar_t> wostringstream;
  typedef basic_stringstream<wchar_t> wstringstream;
  typedef basic_filebuf<wchar_t> wfilebuf;
  typedef basic_ifstream<wchar_t> wifstream;
  typedef basic_ofstream<wchar_t> wofstream;
  typedef basic_fstream<wchar_t> wfstream;

}
# 78 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/include/g++-v3/bits/stl_iterator_base_types.h" 1 3
# 69 "/usr/include/g++-v3/bits/stl_iterator_base_types.h" 3

# 1 "/usr/include/g++-v3/bits/std_cstddef.h" 1 3
# 71 "/usr/include/g++-v3/bits/stl_iterator_base_types.h" 2 3


namespace std
{

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 _Tp, class _Distance> struct input_iterator {
  typedef input_iterator_tag iterator_category;
  typedef _Tp value_type;
  typedef _Distance difference_type;
  typedef _Tp* pointer;
  typedef _Tp& reference;
};

struct output_iterator {
  typedef output_iterator_tag iterator_category;
  typedef void value_type;
  typedef void difference_type;
  typedef void pointer;
  typedef void reference;
};

template <class _Tp, class _Distance> struct forward_iterator {
  typedef forward_iterator_tag iterator_category;
  typedef _Tp value_type;
  typedef _Distance difference_type;
  typedef _Tp* pointer;
  typedef _Tp& reference;
};


template <class _Tp, class _Distance> struct bidirectional_iterator {
  typedef bidirectional_iterator_tag iterator_category;
  typedef _Tp value_type;
  typedef _Distance difference_type;
  typedef _Tp* pointer;
  typedef _Tp& reference;
};

template <class _Tp, class _Distance> struct random_access_iterator {
  typedef random_access_iterator_tag iterator_category;
  typedef _Tp value_type;
  typedef _Distance difference_type;
  typedef _Tp* pointer;
  typedef _Tp& reference;
};

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 <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<_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 _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;
};
# 171 "/usr/include/g++-v3/bits/stl_iterator_base_types.h" 3
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&)
{
  return static_cast<typename iterator_traits<_Iter>::difference_type*>(0);
}

template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
__value_type(const _Iter&)
{
  return static_cast<typename iterator_traits<_Iter>::value_type*>(0);
}

template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
iterator_category(const _Iter& __i) { return __iterator_category(__i); }


template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type*
distance_type(const _Iter& __i) { return __distance_type(__i); }

template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
value_type(const _Iter& __i) { return __value_type(__i); }

}
# 79 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/include/g++-v3/bits/stl_iterator_base_funcs.h" 1 3
# 69 "/usr/include/g++-v3/bits/stl_iterator_base_funcs.h" 3
# 1 "/usr/include/g++-v3/bits/concept_check.h" 1 3
# 34 "/usr/include/g++-v3/bits/concept_check.h" 3

# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/c++config.h" 1 3
# 36 "/usr/include/g++-v3/bits/concept_check.h" 2 3
# 70 "/usr/include/g++-v3/bits/stl_iterator_base_funcs.h" 2 3

namespace std
{





template <class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator __last,
                       _Distance& __n, input_iterator_tag)
{

                                                                    ;
  while (__first != __last) { ++__first; ++__n; }
}

template <class _RandomAccessIterator, class _Distance>
inline void __distance(_RandomAccessIterator __first,
                       _RandomAccessIterator __last,
                       _Distance& __n, random_access_iterator_tag)
{

                                                                                  ;
  __n += __last - __first;
}

template <class _InputIterator, class _Distance>
inline void distance(_InputIterator __first,
                     _InputIterator __last, _Distance& __n)
{

  __distance(__first, __last, __n, iterator_category(__first));
}

template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
{

                                                                    ;
  typename iterator_traits<_InputIterator>::difference_type __n = 0;
  while (__first != __last) {
    ++__first; ++__n;
  }
  return __n;
}

template <class _RandomAccessIterator>
inline typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
           random_access_iterator_tag)
{

                                                                                  ;
  return __last - __first;
}

template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last)
{

  typedef typename iterator_traits<_InputIterator>::iterator_category
    _Category;
  return __distance(__first, __last, _Category());
}

template <class _InputIter, class _Distance>
inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag)
{

                                                                ;
  while (__n--) ++__i;
}

template <class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator& __i, _Distance __n,
                      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,
                      random_access_iterator_tag)
{

                                                                                  ;
  __i += __n;
}

template <class _InputIterator, class _Distance>
inline void advance(_InputIterator& __i, _Distance __n)
{

  __advance(__i, __n, iterator_category(__i));
}

}
# 80 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/include/g++-v3/bits/stl_iterator.h" 1 3
# 63 "/usr/include/g++-v3/bits/stl_iterator.h" 3
namespace std
{

template <class _Container>
class back_insert_iterator {
protected:
  _Container* container;
public:
  typedef _Container container_type;
  typedef output_iterator_tag iterator_category;
  typedef void value_type;
  typedef void difference_type;
  typedef void pointer;
  typedef void reference;

  explicit back_insert_iterator(_Container& __x) : container(&__x) {}
  back_insert_iterator<_Container>&
  operator=(const typename _Container::value_type& __value) {
    container->push_back(__value);
    return *this;
  }
  back_insert_iterator<_Container>& operator*() { return *this; }
  back_insert_iterator<_Container>& operator++() { return *this; }
  back_insert_iterator<_Container>& 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 {
protected:
  _Container* container;
public:
  typedef _Container container_type;
  typedef output_iterator_tag iterator_category;
  typedef void value_type;
  typedef void difference_type;
  typedef void pointer;
  typedef void reference;

  explicit front_insert_iterator(_Container& __x) : container(&__x) {}
  front_insert_iterator<_Container>&
  operator=(const typename _Container::value_type& __value) {
    container->push_front(__value);
    return *this;
  }
  front_insert_iterator<_Container>& operator*() { return *this; }
  front_insert_iterator<_Container>& operator++() { return *this; }
  front_insert_iterator<_Container>& 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 {
protected:
  _Container* container;
  typename _Container::iterator iter;
public:
  typedef _Container container_type;
  typedef output_iterator_tag iterator_category;
  typedef void value_type;
  typedef void difference_type;
  typedef void pointer;
  typedef void reference;

  insert_iterator(_Container& __x, typename _Container::iterator __i)
    : container(&__x), iter(__i) {}
  insert_iterator<_Container>&
  operator=(const typename _Container::value_type& __value) {
    iter = container->insert(iter, __value);
    ++iter;
    return *this;
  }
  insert_iterator<_Container>& operator*() { return *this; }
  insert_iterator<_Container>& operator++() { return *this; }
  insert_iterator<_Container>& 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));
}

template <class _BidirectionalIterator, class _Tp, class _Reference = _Tp&,
          class _Distance = ptrdiff_t>
class reverse_bidirectional_iterator {
  typedef reverse_bidirectional_iterator<_BidirectionalIterator, _Tp,
                                         _Reference, _Distance> _Self;
protected:
  _BidirectionalIterator current;
public:
  typedef bidirectional_iterator_tag iterator_category;
  typedef _Tp value_type;
  typedef _Distance difference_type;
  typedef _Tp* pointer;
  typedef _Reference reference;

  reverse_bidirectional_iterator() {}
  explicit reverse_bidirectional_iterator(_BidirectionalIterator __x)
    : current(__x) {}
  _BidirectionalIterator base() const { return current; }
  _Reference operator*() const {
    _BidirectionalIterator __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;
  }
};

template <class _BiIter, class _Tp, class _Ref, class _Distance>
inline bool operator==(
    const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
    const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
{
  return __x.base() == __y.base();
}

template <class _BiIter, class _Tp, class _Ref, class _Distance>
inline bool operator!=(
    const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __x,
    const reverse_bidirectional_iterator<_BiIter, _Tp, _Ref, _Distance>& __y)
{
  return !(__x == __y);
}
# 222 "/usr/include/g++-v3/bits/stl_iterator.h" 3
template <class _Iterator>
class reverse_iterator
{
protected:
  _Iterator current;
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;
  typedef reverse_iterator<_Iterator> _Self;

public:
  reverse_iterator() {}
  explicit reverse_iterator(iterator_type __x) : current(__x) {}

  reverse_iterator(const _Self& __x) : current(__x.current) {}
  template <class _Iter>
  reverse_iterator(const reverse_iterator<_Iter>& __x)
    : current(__x.base()) {}

  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>
inline reverse_iterator<_Iterator>
operator+(typename reverse_iterator<_Iterator>::difference_type __n,
          const reverse_iterator<_Iterator>& __x) {
  return reverse_iterator<_Iterator>(__x.base() - __n);
}


template <class _Tp,
          class _CharT = char, class _Traits = char_traits<_CharT>,
          class _Dist = ptrdiff_t>
class istream_iterator {
public:
  typedef _CharT char_type;
  typedef _Traits traits_type;
  typedef basic_istream<_CharT, _Traits> istream_type;

  typedef input_iterator_tag iterator_category;
  typedef _Tp value_type;
  typedef _Dist difference_type;
  typedef const _Tp* pointer;
  typedef const _Tp& reference;

  istream_iterator() : _M_stream(0), _M_ok(false) {}
  istream_iterator(istream_type& __s) : _M_stream(&__s) { _M_read(); }

  reference operator*() const { return _M_value; }
  pointer operator->() const { return &(operator*()); }

  istream_iterator& operator++() {
    _M_read();
    return *this;
  }
  istream_iterator operator++(int) {
    istream_iterator __tmp = *this;
    _M_read();
    return __tmp;
  }

  bool _M_equal(const istream_iterator& __x) const
    { return (_M_ok == __x._M_ok) && (!_M_ok || _M_stream == __x._M_stream); }

private:
  istream_type* _M_stream;
  _Tp _M_value;
  bool _M_ok;

  void _M_read() {
    _M_ok = (_M_stream && *_M_stream) ? true : false;
    if (_M_ok) {
      *_M_stream >> _M_value;
      _M_ok = *_M_stream ? true : false;
    }
  }
};

template <class _Tp, class _CharT, class _Traits, class _Dist>
inline bool
operator==(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
           const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
  return __x._M_equal(__y);
}

template <class _Tp, class _CharT, class _Traits, class _Dist>
inline bool
operator!=(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
           const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y) {
  return !__x._M_equal(__y);
}


template <class _Tp,
          class _CharT = char, class _Traits = char_traits<_CharT> >
class ostream_iterator {
public:
  typedef _CharT char_type;
  typedef _Traits traits_type;
  typedef basic_ostream<_CharT, _Traits> ostream_type;

  typedef output_iterator_tag iterator_category;
  typedef void value_type;
  typedef void difference_type;
  typedef void pointer;
  typedef void reference;

  ostream_iterator(ostream_type& __s) : _M_stream(&__s), _M_string(0) {}
  ostream_iterator(ostream_type& __s, const _CharT* __c)
    : _M_stream(&__s), _M_string(__c) {}
  ostream_iterator<_Tp>& operator=(const _Tp& __value) {
    *_M_stream << __value;
    if (_M_string) *_M_stream << _M_string;
    return *this;
  }
  ostream_iterator<_Tp>& operator*() { return *this; }
  ostream_iterator<_Tp>& operator++() { return *this; }
  ostream_iterator<_Tp>& operator++(int) { return *this; }
private:
  ostream_type* _M_stream;
  const _CharT* _M_string;
};
# 446 "/usr/include/g++-v3/bits/stl_iterator.h" 3
template<typename _Iterator, typename _Container>
class __normal_iterator
  : public iterator<iterator_traits<_Iterator>::iterator_category,
                    iterator_traits<_Iterator>::value_type,
                    iterator_traits<_Iterator>::difference_type,
                    iterator_traits<_Iterator>::pointer,
                    iterator_traits<_Iterator>::reference>
{

protected:
  _Iterator _M_current;

public:
  typedef __normal_iterator<_Iterator, _Container> normal_iterator_type;
  typedef iterator_traits<_Iterator> __traits_type;
  typedef typename __traits_type::iterator_category iterator_category;
  typedef typename __traits_type::value_type value_type;
  typedef typename __traits_type::difference_type difference_type;
  typedef typename __traits_type::pointer pointer;
  typedef typename __traits_type::reference reference;

  __normal_iterator() : _M_current(_Iterator()) { }

  explicit __normal_iterator(const _Iterator& __i) : _M_current(__i) { }


  template<typename _Iter>
  inline __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
    : _M_current(__i.base()) { }


  reference
  operator*() const { return *_M_current; }

  pointer
  operator->() const { return _M_current; }

  normal_iterator_type&
  operator++() { ++_M_current; return *this; }

  normal_iterator_type
  operator++(int) { return __normal_iterator(_M_current++); }


  normal_iterator_type&
  operator--() { --_M_current; return *this; }

  normal_iterator_type
  operator--(int) { return __normal_iterator(_M_current--); }


  reference
  operator[](const difference_type& __n) const
  { return _M_current[__n]; }

  normal_iterator_type&
  operator+=(const difference_type& __n)
  { _M_current += __n; return *this; }

  normal_iterator_type
  operator+(const difference_type& __n) const
  { return __normal_iterator(_M_current + __n); }

  normal_iterator_type&
  operator-=(const difference_type& __n)
  { _M_current -= __n; return *this; }

  normal_iterator_type
  operator-(const difference_type& __n) const
  { return __normal_iterator(_M_current - __n); }

  difference_type
  operator-(const normal_iterator_type& __i) const
  { return _M_current - __i._M_current; }

  const _Iterator&
  base() const { return _M_current; }
};



template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
           const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return __lhs.base() == __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
           const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return !(__lhs == __rhs); }



template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
          const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return __lhs.base() < __rhs.base(); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
          const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return __rhs < __lhs; }

template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
           const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return !(__rhs < __lhs); }

template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
           const __normal_iterator<_IteratorR, _Container>& __rhs)
{ return !(__lhs < __rhs); }

template<typename _Iterator, typename _Container>
inline __normal_iterator<_Iterator, _Container>
operator+(typename __normal_iterator<_Iterator, _Container>::difference_type __n,
          const __normal_iterator<_Iterator, _Container>& __i)
{ return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }

}
# 81 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/include/g++-v3/bits/concept_check.h" 1 3
# 82 "/usr/include/g++-v3/bits/stl_algobase.h" 2 3

namespace std
{



template <class _ForwardIter1, class _ForwardIter2, class _Tp>
inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*)
{
  _Tp __tmp = *__a;
  *__a = *__b;
  *__b = __tmp;
}

template <class _ForwardIter1, class _ForwardIter2>
inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b)
{

                                                                             ;
                                                                             ;
                                                             ;


                                                             ;



  __iter_swap(__a, __b, __value_type(__a));
}

template <class _Tp>
inline void swap(_Tp& __a, _Tp& __b)
{

                                                         ;

  _Tp __tmp = __a;
  __a = __b;
  __b = __tmp;
}







template <class _Tp>
inline const _Tp& min(const _Tp& __a, const _Tp& __b) {

                                                              ;

  if (__b < __a) return __b; return __a;
}

template <class _Tp>
inline const _Tp& max(const _Tp& __a, const _Tp& __b) {

                                                              ;

  if (__a < __b) return __b; return __a;
}

template <class _Tp, class _Compare>
inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {

  if (__comp(__b, __a)) return __b; return __a;
}

template <class _Tp, class _Compare>
inline const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) {

  if (__comp(__a, __b)) return __b; return __a;
}
# 166 "/usr/include/g++-v3/bits/stl_algobase.h" 3
template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __copy(_InputIter __first, _InputIter __last,
                          _OutputIter __result,
                          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, random_access_iterator_tag, _Distance*)
{
  for (_Distance __n = __last - __first; __n > 0; --__n) {
    *__result = *__first;
    ++__first;
    ++__result;
  }
  return __result;
}

template <class _Tp>
inline _Tp*
__copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
{
  memmove(__result, __first, sizeof(_Tp) * (__last - __first));
  return __result + (__last - __first);
}


template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
                               _OutputIter __result, __false_type)
{
  return __copy(__first, __last, __result,
                __iterator_category(__first),
                __distance_type(__first));
}

template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
                               _OutputIter __result, __true_type)
{
  return __copy(__first, __last, __result,
                __iterator_category(__first),
                __distance_type(__first));
}

template <class _Tp>
inline _Tp* __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result,
                        __true_type)
{
  return __copy_trivial(__first, __last, __result);
}

template <class _Tp>
inline _Tp* __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result,
                        __true_type)
{
  return __copy_trivial(__first, __last, __result);
}


template <class _InputIter, class _OutputIter, class _Tp>
inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last,
                              _OutputIter __result, _Tp*)
{
  typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
          _Trivial;
  return __copy_aux2(__first, __last, __result, _Trivial());
}

template<typename _InputIter, typename _OutputIter>
inline _OutputIter __copy_ni2(_InputIter __first, _InputIter __last,
                               _OutputIter __result, __true_type)
{
  return _OutputIter(__copy_aux(__first, __last, __result.base(),
                                __value_type(__first)));
}

template<typename _InputIter, typename _OutputIter>
inline _OutputIter __copy_ni2(_InputIter __first, _InputIter __last,
                              _OutputIter __result, __false_type)
{
  return __copy_aux(__first, __last, __result, __value_type(__first));
}

template<typename _InputIter, typename _OutputIter>
inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last,
                               _OutputIter __result, __true_type)
{
  typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
  return __copy_ni2(__first.base(), __last.base(), __result, __Normal());
}

template<typename _InputIter, typename _OutputIter>
inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last,
                               _OutputIter __result, __false_type)
{
  typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
  return __copy_ni2(__first, __last, __result, __Normal());
}

template <class _InputIter, class _OutputIter>
inline _OutputIter copy(_InputIter __first, _InputIter __last,
                        _OutputIter __result)
{

                                                                ;
                                                          ;


   typedef typename _Is_normal_iterator<_InputIter>::_Normal __Normal;
   return __copy_ni1(__first, __last, __result, __Normal());
}




template <class _BidirectionalIter1, class _BidirectionalIter2,
          class _Distance>
inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,
                                           _BidirectionalIter1 __last,
                                           _BidirectionalIter2 __result,
                                           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,
                                          random_access_iterator_tag,
                                          _Distance*)
{
  for (_Distance __n = __last - __first; __n > 0; --__n)
    *--__result = *--__last;
  return __result;
}







template <class _BidirectionalIter1, class _BidirectionalIter2,
          class _BoolType>
struct __copy_backward_dispatch
{
  typedef typename iterator_traits<_BidirectionalIter1>::iterator_category
          _Cat;
  typedef typename iterator_traits<_BidirectionalIter1>::difference_type
          _Distance;

  static _BidirectionalIter2 copy(_BidirectionalIter1 __first,
                                  _BidirectionalIter1 __last,
                                  _BidirectionalIter2 __result) {
    return __copy_backward(__first, __last, __result, _Cat(), (_Distance*) 0);
  }
};

template <class _Tp>
struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
{
  static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
    const ptrdiff_t _Num = __last - __first;
    memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
    return __result - _Num;
  }
};

template <class _Tp>
struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
{
  static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
    return __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
      ::copy(__first, __last, __result);
  }
};

template <class _BI1, class _BI2>
inline _BI2 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) {
  typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
                        ::has_trivial_assignment_operator
          _Trivial;
  return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
              ::copy(__first, __last, __result);
}

template <typename _BI1, typename _BI2>
inline _BI2 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
                                                   _BI2 __result, __true_type) {
  return _BI2(__copy_backward_aux(__first, __last, __result.base()));
}

template <typename _BI1, typename _BI2>
inline _BI2 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
                                                   _BI2 __result, __false_type){
  return __copy_backward_aux(__first, __last, __result);
}

template <typename _BI1, typename _BI2>
inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
                                                  _BI2 __result, __true_type) {
  typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
  return __copy_backward_output_normal_iterator(__first.base(), __last.base(),
                                                __result, __Normal());
}

template <typename _BI1, typename _BI2>
inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
                                                  _BI2 __result, __false_type) {
  typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
  return __copy_backward_output_normal_iterator(__first, __last, __result,
                                                __Normal());
}

template <typename _BI1, typename _BI2>
inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
{

                                                                  ;
                                                                          ;
                                                    ;



  typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal;
  return __copy_backward_input_normal_iterator(__first, __last, __result,
                                               __Normal());
}




template <class _InputIter, class _Size, class _OutputIter>
pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
                                       _OutputIter __result,
                                       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,
         random_access_iterator_tag) {
  _RAIter __last = __first + __count;
  return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
}

template <class _InputIter, class _Size, class _OutputIter>
inline pair<_InputIter, _OutputIter>
__copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
  return __copy_n(__first, __count, __result,
                  __iterator_category(__first));
}

template <class _InputIter, class _Size, class _OutputIter>
inline pair<_InputIter, _OutputIter>
copy_n(_InputIter __first, _Size __count, _OutputIter __result)
{

                                                                ;
                                                          ;


  return __copy_n(__first, __count, __result);
}





template <class _ForwardIter, class _Tp>
void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value)
{

                                                                            ;

  for ( ; __first != __last; ++__first)
    *__first = __value;
}

template <class _OutputIter, class _Size, class _Tp>
_OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value)
{

                                                                      ;

  for ( ; __n > 0; --__n, ++__first)
    *__first = __value;
  return __first;
}



inline void fill(unsigned char* __first, unsigned char* __last,
                 const unsigned char& __c)
{
  unsigned char __tmp = __c;
  memset(__first, __tmp, __last - __first);
}

inline void fill(signed char* __first, signed char* __last,
                 const signed char& __c)
{
  signed char __tmp = __c;
  memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
}

inline void fill(char* __first, char* __last, const char& __c)
{
  char __tmp = __c;
  memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
}

template <class _Size>
inline unsigned char* fill_n(unsigned char* __first, _Size __n,
                             const unsigned char& __c)
{
  fill(__first, __first + __n, __c);
  return __first + __n;
}

template <class _Size>
inline signed char* fill_n(char* __first, _Size __n,
                           const signed char& __c)
{
  fill(__first, __first + __n, __c);
  return __first + __n;
}

template <class _Size>
inline char* fill_n(char* __first, _Size __n, const char& __c)
{
  fill(__first, __first + __n, __c);
  return __first + __n;
}





template <class _InputIter1, class _InputIter2>
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>
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)
{

                                                                 ;
                                                                 ;
                                                           ;

                                                           ;


  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;
}

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;
}

inline bool lexicographical_compare(const char* __first1, const char* __last1,
                                    const char* __first2, const char* __last2)
{

  return lexicographical_compare((const signed char*) __first1,
                                 (const signed char*) __last1,
                                 (const signed char*) __first2,
                                 (const signed char*) __last2);






}

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;
  }
}

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));
}

inline int
__lexicographical_compare_3way(const char* __first1, const char* __last1,
                               const char* __first2, const char* __last2)
{

  return __lexicographical_compare_3way(
                                (const signed char*) __first1,
                                (const signed char*) __last1,
                                (const signed char*) __first2,
                                (const signed char*) __last2);






}

template <class _InputIter1, class _InputIter2>
int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
                                 _InputIter2 __first2, _InputIter2 __last2)
{

                                                                 ;
                                                                 ;
                                                           ;

                                                           ;


  return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
}

}
# 86 "/usr/include/g++-v3/bits/stl_tree.h" 2 3
# 1 "/usr/include/g++-v3/bits/stl_alloc.h" 1 3
# 57 "/usr/include/g++-v3/bits/stl_alloc.h" 3
# 1 "/usr/include/g++-v3/bits/functexcept.h" 1 3
# 34 "/usr/include/g++-v3/bits/functexcept.h" 3
# 1 "/usr/include/g++-v3/exception_defines.h" 1 3
# 35 "/usr/include/g++-v3/bits/functexcept.h" 2 3

namespace std
{

  void
  __throw_bad_exception(void);


  void
  __throw_bad_alloc(void);


  void
  __throw_bad_cast(void);

  void
  __throw_bad_typeid(void);


  void
  __throw_logic_error(const char* __s);

  void
  __throw_domain_error(const char* __s);

  void
  __throw_invalid_argument(const char* __s);

  void
  __throw_length_error(const char* __s);

  void
  __throw_out_of_range(const char* __s);

  void
  __throw_runtime_error(const char* __s);

  void
  __throw_range_error(const char* __s);

  void
  __throw_overflow_error(const char* __s);

  void
  __throw_underflow_error(const char* __s);


  void
  __throw_ios_failure(const char* __s);
}
# 58 "/usr/include/g++-v3/bits/stl_alloc.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_cstddef.h" 1 3
# 59 "/usr/include/g++-v3/bits/stl_alloc.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_cstdlib.h" 1 3
# 60 "/usr/include/g++-v3/bits/stl_alloc.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_cstring.h" 1 3
# 61 "/usr/include/g++-v3/bits/stl_alloc.h" 2 3
# 1 "/usr/include/g++-v3/bits/std_cassert.h" 1 3
# 37 "/usr/include/g++-v3/bits/std_cassert.h" 3
# 1 "/usr/include/assert.h" 1 3
# 36 "/usr/include/assert.h" 3
# 1 "/usr/include/features.h" 1 3
# 37 "/usr/include/assert.h" 2 3
# 65 "/usr/include/assert.h" 3
extern "C" {


extern void __assert_fail (__const char *__assertion, __const char *__file,
                           unsigned int __line, __const char *__function)
     throw () __attribute__ ((__noreturn__));


extern void __assert_perror_fail (int __errnum, __const char *__file,
                                  unsigned int __line,
                                  __const char *__function)
     throw () __attribute__ ((__noreturn__));




extern void __assert (const char *__assertion, const char *__file, int __line)
     throw () __attribute__ ((__noreturn__));


}
# 38 "/usr/include/g++-v3/bits/std_cassert.h" 2 3
# 62 "/usr/include/g++-v3/bits/stl_alloc.h" 2 3





# 1 "/usr/include/g++-v3/bits/stl_threads.h" 1 3
# 62 "/usr/include/g++-v3/bits/stl_threads.h" 3
# 1 "/usr/include/g++-v3/i686-pc-linux-gnu/bits/gthr.h" 1 3
# 63 "/usr/include/g++-v3/bits/stl_threads.h" 2 3
# 80 "/usr/include/g++-v3/bits/stl_threads.h" 3
namespace std
{
# 95 "/usr/include/g++-v3/bits/stl_threads.h" 3
struct _Refcount_Base
{




  typedef size_t _RC_t;



   volatile _RC_t _M_ref_count;




  __gthread_mutex_t _M_ref_count_lock;
  _Refcount_Base(_RC_t __n) : _M_ref_count(__n)
    {

      __gthread_mutex_t __tmp = {0, 0, 0, PTHREAD_MUTEX_TIMED_NP, { 0, 0 }};
      _M_ref_count_lock = __tmp;





    }
# 141 "/usr/include/g++-v3/bits/stl_threads.h" 3
  void _M_incr() {
    __gthread_mutex_lock(&_M_ref_count_lock);
    ++_M_ref_count;
    __gthread_mutex_unlock(&_M_ref_count_lock);
  }
  _RC_t _M_decr() {
    __gthread_mutex_lock(&_M_ref_count_lock);
    volatile _RC_t __tmp = --_M_ref_count;
    __gthread_mutex_unlock(&_M_ref_count_lock);
    return __tmp;
  }
# 192 "/usr/include/g++-v3/bits/stl_threads.h" 3
};
# 313 "/usr/include/g++-v3/bits/stl_threads.h" 3
template <int __inst>
struct _STL_mutex_spin {
  enum { __low_max = 30, __high_max = 1000 };


  static unsigned __max;
  static unsigned __last;
};

template <int __inst>
unsigned _STL_mutex_spin<__inst>::__max = _STL_mutex_spin<__inst>::__low_max;

template <int __inst>
unsigned _STL_mutex_spin<__inst>::__last = 0;
# 340 "/usr/include/g++-v3/bits/stl_threads.h" 3
struct _STL_mutex_lock
{







  __gthread_mutex_t _M_lock;
  void _M_initialize() {
# 371 "/usr/include/g++-v3/bits/stl_threads.h" 3
  }
  void _M_acquire_lock() {



    __gthread_mutex_lock(&_M_lock);
  }
  void _M_release_lock() {



    __gthread_mutex_unlock(&_M_lock);
  }
# 482 "/usr/include/g++-v3/bits/stl_threads.h" 3
};
# 521 "/usr/include/g++-v3/bits/stl_threads.h" 3
struct _STL_auto_lock
{
  _STL_mutex_lock& _M_lock;

  _STL_auto_lock(_STL_mutex_lock& __lock) : _M_lock(__lock)
    { _M_lock._M_acquire_lock(); }
  ~_STL_auto_lock() { _M_lock._M_release_lock(); }

private:
  void operator=(const _STL_auto_lock&);
  _STL_auto_lock(const _STL_auto_lock&);
};

}
# 68 "/usr/include/g++-v3/bits/stl_alloc.h" 2 3
# 97 "/usr/include/g++-v3/bits/stl_alloc.h" 3
namespace std
{



template <int __inst>
class __malloc_alloc_template {

private:

  static void* _S_oom_malloc(size_t);
  static void* _S_oom_realloc(void*, size_t);
  static void (* __malloc_alloc_oom_handler)();

public:

  static void* allocate(size_t __n)
  {
    void* __result = malloc(__n);
    if (0 == __result) __result = _S_oom_malloc(__n);
    return __result;
  }

  static void deallocate(void* __p, size_t )
  {
    free(__p);
  }

  static void* reallocate(void* __p, size_t , size_t __new_sz)
  {
    void* __result = realloc(__p, __new_sz);
    if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
    return __result;
  }

  static void (* __set_malloc_handler(void (*__f)()))()
  {
    void (* __old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = __f;
    return(__old);
  }

};



template <int __inst>
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;

template <int __inst>
void*
__malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
{
    void (* __my_malloc_handler)();
    void* __result;

    for (;;) {
        __my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == __my_malloc_handler) { std::__throw_bad_alloc(); }
        (*__my_malloc_handler)();
        __result = malloc(__n);
        if (__result) return(__result);
    }
}

template <int __inst>
void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
{
    void (* __my_malloc_handler)();
    void* __result;

    for (;;) {
        __my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == __my_malloc_handler) { std::__throw_bad_alloc(); }
        (*__my_malloc_handler)();
        __result = realloc(__p, __n);
        if (__result) return(__result);
    }
}

typedef __malloc_alloc_template<0> malloc_alloc;

template<class _Tp, class _Alloc>
class simple_alloc {

public:
    static _Tp* allocate(size_t __n)
      { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
    static _Tp* allocate(void)
      { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
    static void deallocate(_Tp* __p, size_t __n)
      { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
    static void deallocate(_Tp* __p)
      { _Alloc::deallocate(__p, sizeof (_Tp)); }
};






template <class _Alloc>
class debug_alloc {

private:

  enum {_S_extra = 8};



public:

  static void* allocate(size_t __n)
  {
    char* __result = (char*)_Alloc::allocate(__n + (int) _S_extra);
    *(size_t*)__result = __n;
    return __result + (int) _S_extra;
  }

  static void deallocate(void* __p, size_t __n)
  {
    char* __real_p = (char*)__p - (int) _S_extra;
    (static_cast<void> ((*(size_t*)__real_p == __n) ? 0 : (__assert_fail ("*(size_t*)__real_p == __n", "/usr/include/g++-v3/bits/stl_alloc.h", 219, __PRETTY_FUNCTION__), 0)));
    _Alloc::deallocate(__real_p, __n + (int) _S_extra);
  }

  static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz)
  {
    char* __real_p = (char*)__p - (int) _S_extra;
    (static_cast<void> ((*(size_t*)__real_p == __old_sz) ? 0 : (__assert_fail ("*(size_t*)__real_p == __old_sz", "/usr/include/g++-v3/bits/stl_alloc.h", 226, __PRETTY_FUNCTION__), 0)));
    char* __result = (char*)
      _Alloc::reallocate(__real_p, __old_sz + (int) _S_extra,
                                   __new_sz + (int) _S_extra);
    *(size_t*)__result = __new_sz;
    return __result + (int) _S_extra;
  }

};
# 270 "/usr/include/g++-v3/bits/stl_alloc.h" 3
template <bool threads, int inst>
class __default_alloc_template {

private:


  enum {_ALIGN = 8};
  enum {_MAX_BYTES = 128};
  enum {_NFREELISTS = 16};
  static size_t
  _S_round_up(size_t __bytes)
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

  union _Obj {
        union _Obj* _M_free_list_link;
        char _M_client_data[1];
  };

  static _Obj* volatile _S_free_list[];

  static size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
  }


  static void* _S_refill(size_t __n);


  static char* _S_chunk_alloc(size_t __size, int& __nobjs);


  static char* _S_start_free;
  static char* _S_end_free;
  static size_t _S_heap_size;


    static _STL_mutex_lock _S_node_allocator_lock;





    class _Lock;
    friend class _Lock;
    class _Lock {
        public:
            _Lock() { { if (threads) _S_node_allocator_lock._M_acquire_lock(); }; }
            ~_Lock() { { if (threads) _S_node_allocator_lock._M_release_lock(); }; }
    };

public:


  static void* allocate(size_t __n)
  {
    void* __ret = 0;

    if (__n > (size_t) _MAX_BYTES) {
      __ret = malloc_alloc::allocate(__n);
    }
    else {
      _Obj* volatile* __my_free_list
          = _S_free_list + _S_freelist_index(__n);





      _Lock __lock_instance;

      _Obj* __result = *__my_free_list;
      if (__result == 0)
        __ret = _S_refill(_S_round_up(__n));
      else {
        *__my_free_list = __result -> _M_free_list_link;
        __ret = __result;
      }
    }

    return __ret;
  };


  static void deallocate(void* __p, size_t __n)
  {
    if (__n > (size_t) _MAX_BYTES)
      malloc_alloc::deallocate(__p, __n);
    else {
      _Obj* volatile* __my_free_list
          = _S_free_list + _S_freelist_index(__n);
      _Obj* __q = (_Obj*)__p;




      _Lock __lock_instance;

      __q -> _M_free_list_link = *__my_free_list;
      *__my_free_list = __q;

    }
  }

  static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);

} ;

typedef __default_alloc_template<true, 0> alloc;
typedef __default_alloc_template<false, 0> single_client_alloc;

template <bool __threads, int __inst>
inline bool operator==(const __default_alloc_template<__threads, __inst>&,
                       const __default_alloc_template<__threads, __inst>&)
{
  return true;
}

template <bool __threads, int __inst>
inline bool operator!=(const __default_alloc_template<__threads, __inst>&,
                       const __default_alloc_template<__threads, __inst>&)
{
  return false;
}







template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
                                                            int& __nobjs)
{
    char* __result;
    size_t __total_bytes = __size * __nobjs;
    size_t __bytes_left = _S_end_free - _S_start_free;

    if (__bytes_left >= __total_bytes) {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else if (__bytes_left >= __size) {
        __nobjs = (int)(__bytes_left/__size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } else {
        size_t __bytes_to_get =
          2 * __total_bytes + _S_round_up(_S_heap_size >> 4);

        if (__bytes_left > 0) {
            _Obj* volatile* __my_free_list =
                        _S_free_list + _S_freelist_index(__bytes_left);

            ((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
            *__my_free_list = (_Obj*)_S_start_free;
        }
        _S_start_free = (char*)malloc(__bytes_to_get);
        if (0 == _S_start_free) {
            size_t __i;
            _Obj* volatile* __my_free_list;
            _Obj* __p;



            for (__i = __size;
                 __i <= (size_t) _MAX_BYTES;
                 __i += (size_t) _ALIGN) {
                __my_free_list = _S_free_list + _S_freelist_index(__i);
                __p = *__my_free_list;
                if (0 != __p) {
                    *__my_free_list = __p -> _M_free_list_link;
                    _S_start_free = (char*)__p;
                    _S_end_free = _S_start_free + __i;
                    return(_S_chunk_alloc(__size, __nobjs));


                }
            }
            _S_end_free = 0;
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);



        }
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs));
    }
}





template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
    int __nobjs = 20;
    char* __chunk = _S_chunk_alloc(__n, __nobjs);
    _Obj* volatile* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;
    int __i;

    if (1 == __nobjs) return(__chunk);
    __my_free_list = _S_free_list + _S_freelist_index(__n);


      __result = (_Obj*)__chunk;
      *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
      for (__i = 1; ; __i++) {
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((char*)__next_obj + __n);
        if (__nobjs - 1 == __i) {
            __current_obj -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
      }
    return(__result);
}

template <bool threads, int inst>
void*
__default_alloc_template<threads, inst>::reallocate(void* __p,
                                                    size_t __old_sz,
                                                    size_t __new_sz)
{
    void* __result;
    size_t __copy_sz;

    if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
        return(realloc(__p, __new_sz));
    }
    if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
    __result = allocate(__new_sz);
    __copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
    memcpy(__result, __p, __copy_sz);
    deallocate(__p, __old_sz);
    return(__result);
}


    template <bool __threads, int __inst>
    _STL_mutex_lock
    __default_alloc_template<__threads, __inst>::_S_node_allocator_lock
        = { {0, 0, 0, PTHREAD_MUTEX_TIMED_NP, { 0, 0 }} };



template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;

template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;

template <bool __threads, int __inst>
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;

template <bool __threads, int __inst>
typename __default_alloc_template<__threads, __inst>::_Obj* volatile
__default_alloc_template<__threads, __inst> ::_S_free_list[
    __default_alloc_template<__threads, __inst>::_NFREELISTS
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
# 555 "/usr/include/g++-v3/bits/stl_alloc.h" 3
template <class _Tp>
class allocator {
  typedef alloc _Alloc;
public:
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef _Tp* pointer;
  typedef const _Tp* const_pointer;
  typedef _Tp& reference;
  typedef const _Tp& const_reference;
  typedef _Tp value_type;

  template <class _Tp1> struct rebind {
    typedef allocator<_Tp1> other;
  };

  allocator() throw() {}
  allocator(const allocator&) throw() {}
  template <class _Tp1> allocator(const allocator<_Tp1>&) throw() {}
  ~allocator() throw() {}

  pointer address(reference __x) const { return &__x; }
  const_pointer address(const_reference __x) const { return &__x; }



  _Tp* allocate(size_type __n, const void* = 0) {
    return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp)))
                    : 0;
  }


  void deallocate(pointer __p, size_type __n)
    { _Alloc::deallocate(__p, __n * sizeof(_Tp)); }

  size_type max_size() const throw()
    { return size_t(-1) / sizeof(_Tp); }

  void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
  void destroy(pointer __p) { __p->~_Tp(); }
};

template<>
class allocator<void> {
public:
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef void* pointer;
  typedef const void* const_pointer;
  typedef void value_type;

  template <class _Tp1> struct rebind {
    typedef allocator<_Tp1> other;
  };
};


template <class _T1, class _T2>
inline bool operator==(const allocator<_T1>&, const allocator<_T2>&)
{
  return true;
}

template <class _T1, class _T2>
inline bool operator!=(const allocator<_T1>&, const allocator<_T2>&)
{
  return false;
}
# 631 "/usr/include/g++-v3/bits/stl_alloc.h" 3
template <class _Tp, class _Alloc>
struct __allocator {
  _Alloc __underlying_alloc;

  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef _Tp* pointer;
  typedef const _Tp* const_pointer;
  typedef _Tp& reference;
  typedef const _Tp& const_reference;
  typedef _Tp value_type;

  template <class _Tp1> struct rebind {
    typedef __allocator<_Tp1, _Alloc> other;
  };

  __allocator() throw() {}
  __allocator(const __allocator& __a) throw()
    : __underlying_alloc(__a.__underlying_alloc) {}
  template <class _Tp1>
  __allocator(const __allocator<_Tp1, _Alloc>& __a) throw()
    : __underlying_alloc(__a.__underlying_alloc) {}
  ~__allocator() throw() {}

  pointer address(reference __x) const { return &__x; }
  const_pointer address(const_reference __x) const { return &__x; }


  _Tp* allocate(size_type __n, const void* = 0) {
    return __n != 0
        ? static_cast<_Tp*>(__underlying_alloc.allocate(__n * sizeof(_Tp)))
        : 0;
  }


  void deallocate(pointer __p, size_type __n)
    { __underlying_alloc.deallocate(__p, __n * sizeof(_Tp)); }

  size_type max_size() const throw()
    { return size_t(-1) / sizeof(_Tp); }

  void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
  void destroy(pointer __p) { __p->~_Tp(); }
};

template <class _Alloc>
class __allocator<void, _Alloc> {
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef void* pointer;
  typedef const void* const_pointer;
  typedef void value_type;

  template <class _Tp1> struct rebind {
    typedef __allocator<_Tp1, _Alloc> other;
  };
};

template <class _Tp, class _Alloc>
inline bool operator==(const __allocator<_Tp, _Alloc>& __a1,
                       const __allocator<_Tp, _Alloc>& __a2)
{
  return __a1.__underlying_alloc == __a2.__underlying_alloc;
}

template <class _Tp, class _Alloc>
inline bool operator!=(const __allocator<_Tp, _Alloc>& __a1,
                       const __allocator<_Tp, _Alloc>& __a2)
{
  return __a1.__underlying_alloc != __a2.__underlying_alloc;
}





template <int inst>
inline bool operator==(const __malloc_alloc_template<inst>&,
                       const __malloc_alloc_template<inst>&)
{
  return true;
}

template <int __inst>
inline bool operator!=(const __malloc_alloc_template<__inst>&,
                       const __malloc_alloc_template<__inst>&)
{
  return false;
}

template <class _Alloc>
inline bool operator==(const debug_alloc<_Alloc>&,
                       const debug_alloc<_Alloc>&) {
  return true;
}

template <class _Alloc>
inline bool operator!=(const debug_alloc<_Alloc>&,
                       const debug_alloc<_Alloc>&) {
  return false;
}
# 761 "/usr/include/g++-v3/bits/stl_alloc.h" 3
template <class _Tp, class _Allocator>
struct _Alloc_traits
{
  static const bool _S_instanceless = false;
  typedef typename _Allocator::template rebind<_Tp>::other allocator_type;
};

template <class _Tp, class _Allocator>
const bool _Alloc_traits<_Tp, _Allocator>::_S_instanceless;



template <class _Tp, class _Tp1>
struct _Alloc_traits<_Tp, allocator<_Tp1> >
{
  static const bool _S_instanceless = true;
  typedef simple_alloc<_Tp, alloc> _Alloc_type;
  typedef allocator<_Tp> allocator_type;
};



template <class _Tp, int __inst>
struct _Alloc_traits<_Tp, __malloc_alloc_template<__inst> >
{
  static const bool _S_instanceless = true;
  typedef simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
  typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
};


template <class _Tp, bool __threads, int __inst>
struct _Alloc_traits<_Tp, __default_alloc_template<__threads, __inst> >
{
  static const bool _S_instanceless = true;
  typedef simple_alloc<_Tp, __default_alloc_template<__threads, __inst> >
          _Alloc_type;
  typedef __allocator<_Tp, __default_alloc_template<__threads, __inst> >
          allocator_type;
};


template <class _Tp, class _Alloc>
struct _Alloc_traits<_Tp, debug_alloc<_Alloc> >
{
  static const bool _S_instanceless = true;
  typedef simple_alloc<_Tp, debug_alloc<_Alloc> > _Alloc_type;
  typedef __allocator<_Tp, debug_alloc<_Alloc> > allocator_type;
};




template <class _Tp, class _Tp1, int __inst>
struct _Alloc_traits<_Tp,
                     __allocator<_Tp1, __malloc_alloc_template<__inst> > >
{
  static const bool _S_instanceless = true;
  typedef simple_alloc<_Tp, __malloc_alloc_template<__inst> > _Alloc_type;
  typedef __allocator<_Tp, __malloc_alloc_template<__inst> > allocator_type;
};


template <class _Tp, class _Tp1, bool __thr, int __inst>
struct _Alloc_traits<_Tp,
                      __allocator<_Tp1,
                                  __default_alloc_template<__thr, __inst> > >
{
  static const bool _S_instanceless = true;
  typedef simple_alloc<_Tp, __default_alloc_template<__thr,__inst> >
          _Alloc_type;
  typedef __allocator<_Tp, __default_alloc_template<__thr,__inst> >
          allocator_type;
};


template <class _Tp, class _Tp1, class _Alloc>
struct _Alloc_traits<_Tp, __allocator<_Tp1, debug_alloc<_Alloc> > >
{
  static const bool _S_instanceless = true;
  typedef simple_alloc<_Tp, debug_alloc<_Alloc> > _Alloc_type;
  typedef __allocator<_Tp, debug_alloc<_Alloc> > allocator_type;
};

}
# 87 "/usr/include/g++-v3/bits/stl_tree.h" 2 3
# 1 "/usr/include/g++-v3/bits/stl_construct.h" 1 3
# 63 "/usr/include/g++-v3/bits/stl_construct.h" 3
# 1 "/usr/include/g++-v3/new" 1 3
# 64 "/usr/include/g++-v3/bits/stl_construct.h" 2 3

namespace std
{
# 76 "/usr/include/g++-v3/bits/stl_construct.h" 3
template <class _T1, class _T2>
inline void _Construct(_T1* __p, const _T2& __value) {
new ((void*) __p) _T1(__value);
}

template <class _T1>
inline void _Construct(_T1* __p) {
  new ((void*) __p) _T1();
}

template <class _Tp>
inline void _Destroy(_Tp* __pointer) {
  __pointer->~_Tp();
}

template <class _ForwardIterator>
void
__destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type)
{
  for ( ; __first != __last; ++__first)
    destroy(&*__first);
}

template <class _ForwardIterator>
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}

template <class _ForwardIterator, class _Tp>
inline void
__destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp*)
{
  typedef typename __type_traits<_Tp>::has_trivial_destructor
          _Trivial_destructor;
  __destroy_aux(__first, __last, _Trivial_destructor());
}

template <class _ForwardIterator>
inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
  __destroy(__first, __last, __value_type(__first));
}

inline void _Destroy(char*, char*) {}
inline void _Destroy(int*, int*) {}
inline void _Destroy(long*, long*) {}
inline void _Destroy(float*, float*) {}
inline void _Destroy(double*, double*) {}
inline void _Destroy(wchar_t*, wchar_t*) {}




template <class _T1, class _T2>
inline void construct(_T1* __p, const _T2& __value) {
  _Construct(__p, __value);
}

template <class _T1>
inline void construct(_T1* __p) {
  _Construct(__p);
}

template <class _Tp>
inline void destroy(_Tp* __pointer) {
  _Destroy(__pointer);
}

template <class _ForwardIterator>
inline void destroy(_ForwardIterator __first, _ForwardIterator __last) {
  _Destroy(__first, __last);
}

}
# 88 "/usr/include/g++-v3/bits/stl_tree.h" 2 3
# 1 "/usr/include/g++-v3/bits/stl_function.h" 1 3
# 63 "/usr/include/g++-v3/bits/stl_function.h" 3
namespace std
{

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 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; }
};

template <class _Tp>
struct multiplies : public binary_function<_Tp,_Tp,_Tp> {
  _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x * __y; }
};

template <class _Tp>
struct divides : public binary_function<_Tp,_Tp,_Tp> {
  _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x / __y; }
};



template <class _Tp> inline _Tp identity_element(plus<_Tp>) {
  return _Tp(0);
}
template <class _Tp> inline _Tp identity_element(multiplies<_Tp>) {
  return _Tp(1);
}

template <class _Tp>
struct modulus : public binary_function<_Tp,_Tp,_Tp>
{
  _Tp operator()(const _Tp& __x, const _Tp& __y) const { return __x % __y; }
};

template <class _Tp>
struct negate : public unary_function<_Tp,_Tp>
{
  _Tp operator()(const _Tp& __x) const { return -__x; }
};

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 not_equal_to : public binary_function<_Tp,_Tp,bool>
{
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x != __y; }
};

template <class _Tp>
struct greater : 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>
{
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x < __y; }
};

template <class _Tp>
struct greater_equal : public binary_function<_Tp,_Tp,bool>
{
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x >= __y; }
};

template <class _Tp>
struct less_equal : public binary_function<_Tp,_Tp,bool>
{
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x <= __y; }
};

template <class _Tp>
struct logical_and : public binary_function<_Tp,_Tp,bool>
{
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x && __y; }
};

template <class _Tp>
struct logical_or : public binary_function<_Tp,_Tp,bool>
{
  bool operator()(const _Tp& __x, const _Tp& __y) const { return __x || __y; }
};

template <class _Tp>
struct logical_not : public unary_function<_Tp,bool>
{
  bool operator()(const _Tp& __x) const { return !__x; }
};

template <class _Predicate>
class unary_negate
  : public unary_function<typename _Predicate::argument_type, bool> {
protected:
  _Predicate _M_pred;
public:
  explicit unary_negate(const _Predicate& __x) : _M_pred(__x) {}
  bool operator()(const typename _Predicate::argument_type& __x) const {
    return !_M_pred(__x);
  }
};

template <class _Predicate>
inline unary_negate<_Predicate>
not1(const _Predicate& __pred)
{
  return unary_negate<_Predicate>(__pred);
}

template <class _Predicate>
class binary_negate
  : public binary_function<typename _Predicate::first_argument_type,
                           typename _Predicate::second_argument_type,
                           bool> {
protected:
  _Predicate _M_pred;
public:
  explicit binary_negate(const _Predicate& __x) : _M_pred(__x) {}
  bool operator()(const typename _Predicate::first_argument_type& __x,
                  const typename _Predicate::second_argument_type& __y) const
  {
    return !_M_pred(__x, __y);
  }
};

template <class _Predicate>
inline binary_negate<_Predicate>
not2(const _Predicate& __pred)
{
  return binary_negate<_Predicate>(__pred);
}

template <class _Operation>
class binder1st
  : public unary_function<typename _Operation::second_argument_type,
                          typename _Operation::result_type> {
protected:
  _Operation op;
  typename _Operation::first_argument_type value;
public:
  binder1st(const _Operation& __x,
            const typename _Operation::first_argument_type& __y)
      : op(__x), value(__y) {}
  typename _Operation::result_type
  operator()(const typename _Operation::second_argument_type& __x) const {
    return op(value, __x);
  }


  typename _Operation::result_type
  operator()(typename _Operation::second_argument_type& __x) const {
    return op(value, __x);
  }

};

template <class _Operation, class _Tp>
inline binder1st<_Operation>
bind1st(const _Operation& __fn, const _Tp& __x)
{
  typedef typename _Operation::first_argument_type _Arg1_type;
  return binder1st<_Operation>(__fn, _Arg1_type(__x));
}

template <class _Operation>
class binder2nd
  : public unary_function<typename _Operation::first_argument_type,
                          typename _Operation::result_type> {
protected:
  _Operation op;
  typename _Operation::second_argument_type value;
public:
  binder2nd(const _Operation& __x,
            const typename _Operation::second_argument_type& __y)
      : op(__x), value(__y) {}
  typename _Operation::result_type
  operator()(const typename _Operation::first_argument_type& __x) const {
    return op(__x, value);
  }


  typename _Operation::result_type
  operator()(typename _Operation::first_argument_type& __x) const {
    return op(__x, value);
  }

};

template <class _Operation, class _Tp>
inline binder2nd<_Operation>
bind2nd(const _Operation& __fn, const _Tp& __x)
{
  typedef typename _Operation::second_argument_type _Arg2_type;
  return binder2nd<_Operation>(__fn, _Arg2_type(__x));
}



template <class _Operation1, class _Operation2>
class unary_compose
  : public unary_function<typename _Operation2::argument_type,
                          typename _Operation1::result_type>
{
protected:
  _Operation1 _M_fn1;
  _Operation2 _M_fn2;
public:
  unary_compose(const _Operation1& __x, const _Operation2& __y)
    : _M_fn1(__x), _M_fn2(__y) {}
  typename _Operation1::result_type
  operator()(const typename _Operation2::argument_type& __x) const {
    return _M_fn1(_M_fn2(__x));
  }
};

template <class _Operation1, class _Operation2>
inline unary_compose<_Operation1,_Operation2>
compose1(const _Operation1& __fn1, const _Operation2& __fn2)
{
  return unary_compose<_Operation1,_Operation2>(__fn1, __fn2);
}

template <class _Operation1, class _Operation2, class _Operation3>
class binary_compose
  : public unary_function<typename _Operation2::argument_type,
                          typename _Operation1::result_type> {
protected:
  _Operation1 _M_fn1;
  _Operation2 _M_fn2;
  _Operation3 _M_fn3;
public:
  binary_compose(const _Operation1& __x, const _Operation2& __y,
                 const _Operation3& __z)
    : _M_fn1(__x), _M_fn2(__y), _M_fn3(__z) { }
  typename _Operation1::result_type
  operator()(const typename _Operation2::argument_type& __x) const {
    return _M_fn1(_M_fn2(__x), _M_fn3(__x));
  }
};

template <class _Operation1, class _Operation2, class _Operation3>
inline binary_compose<_Operation1, _Operation2, _Operation3>
compose2(const _Operation1& __fn1, const _Operation2& __fn2,
         const _Operation3& __fn3)
{
  return binary_compose<_Operation1,_Operation2,_Operation3>
    (__fn1, __fn2, __fn3);
}

template <class _Arg, class _Result>
class pointer_to_unary_function : public unary_function<_Arg, _Result> {
protected:
  _Result (*_M_ptr)(_Arg);
public:
  pointer_to_unary_function() {}
  explicit pointer_to_unary_function(_Result (*__x)(_Arg)) : _M_ptr(__x) {}
  _Result operator()(_Arg __x) const { return _M_ptr(__x); }
};

template <class _Arg, class _Result>
inline pointer_to_unary_function<_Arg, _Result> ptr_fun(_Result (*__x)(_Arg))
{
  return pointer_to_unary_function<_Arg, _Result>(__x);
}

template <class _Arg1, class _Arg2, class _Result>
class pointer_to_binary_function :
  public binary_function<_Arg1,_Arg2,_Result> {
protected:
    _Result (*_M_ptr)(_Arg1, _Arg2);
public:
    pointer_to_binary_function() {}
    explicit pointer_to_binary_function(_Result (*__x)(_Arg1, _Arg2))
      : _M_ptr(__x) {}
    _Result operator()(_Arg1 __x, _Arg2 __y) const {
      return _M_ptr(__x, __y);
    }
};

template <class _Arg1, class _Arg2, class _Result>
inline pointer_to_binary_function<_Arg1,_Arg2,_Result>
ptr_fun(_Result (*__x)(_Arg1, _Arg2)) {
  return pointer_to_binary_function<_Arg1,_Arg2,_Result>(__x);
}


template <class _Tp>
struct _Identity : public unary_function<_Tp,_Tp> {
  _Tp& operator()(_Tp& __x) const { return __x; }
  const _Tp& operator()(const _Tp& __x) const { return __x; }
};

template <class _Tp> struct identity : public _Identity<_Tp> {};


template <class _Pair>
struct _Select1st : public unary_function<_Pair, typename _Pair::first_type> {
  typename _Pair::first_type& operator()(_Pair& __x) const {
    return __x.first;
  }
  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>
{
  typename _Pair::second_type& operator()(_Pair& __x) const {
    return __x.second;
  }
  const typename _Pair::second_type& operator()(const _Pair& __x) const {
    return __x.second;
  }
};

template <class _Pair> struct select1st : public _Select1st<_Pair> {};
template <class _Pair> struct select2nd : public _Select2nd<_Pair> {};


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 _Arg1, class _Arg2>
struct project1st : public _Project1st<_Arg1, _Arg2> {};

template <class _Arg1, class _Arg2>
struct project2nd : public _Project2nd<_Arg1, _Arg2> {};





template <class _Result>
struct _Constant_void_fun {
  typedef _Result result_type;
  result_type _M_val;

  _Constant_void_fun(const result_type& __v) : _M_val(__v) {}
  const result_type& operator()() const { return _M_val; }
};

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 _Result>
struct constant_void_fun : public _Constant_void_fun<_Result> {
  constant_void_fun(const _Result& __v) : _Constant_void_fun<_Result>(__v) {}
};


template <class _Result,
          class _Argument = _Result>
struct constant_unary_fun : public _Constant_unary_fun<_Result, _Argument>
{
  constant_unary_fun(const _Result& __v)
    : _Constant_unary_fun<_Result, _Argument>(__v) {}
};


template <class _Result,
          class _Arg1 = _Result,
          class _Arg2 = _Arg1>
struct constant_binary_fun
  : public _Constant_binary_fun<_Result, _Arg1, _Arg2>
{
  constant_binary_fun(const _Result& __v)
    : _Constant_binary_fun<_Result, _Arg1, _Arg2>(__v) {}
};

template <class _Result>
inline constant_void_fun<_Result> constant0(const _Result& __val)
{
  return constant_void_fun<_Result>(__val);
}

template <class _Result>
inline constant_unary_fun<_Result,_Result> constant1(const _Result& __val)
{
  return constant_unary_fun<_Result,_Result>(__val);
}

template <class _Result>
inline constant_binary_fun<_Result,_Result,_Result>
constant2(const _Result& __val)
{
  return constant_binary_fun<_Result,_Result,_Result>(__val);
}



class subtractive_rng : public unary_function<unsigned int, unsigned int> {
private:
  unsigned int _M_table[55];
  size_t _M_index1;
  size_t _M_index2;
public:
  unsigned int operator()(unsigned int __limit) {
    _M_index1 = (_M_index1 + 1) % 55;
    _M_index2 = (_M_index2 + 1) % 55;
    _M_table[_M_index1] = _M_table[_M_index1] - _M_table[_M_index2];
    return _M_table[_M_index1] % __limit;
  }

  void _M_initialize(unsigned int __seed)
  {
    unsigned int __k = 1;
    _M_table[54] = __seed;
    size_t __i;
    for (__i = 0; __i < 54; __i++) {
        size_t __ii = (21 * (__i + 1) % 55) - 1;
        _M_table[__ii] = __k;
        __k = __seed - __k;
        __seed = _M_table[__ii];
    }
    for (int __loop = 0; __loop < 4; __loop++) {
        for (__i = 0; __i < 55; __i++)
            _M_table[__i] = _M_table[__i] - _M_table[(1 + __i + 30) % 55];
    }
    _M_index1 = 0;
    _M_index2 = 31;
  }

  subtractive_rng(unsigned int __seed) { _M_initialize(__seed); }
  subtractive_rng() { _M_initialize(161803398u); }
};
# 562 "/usr/include/g++-v3/bits/stl_function.h" 3
template <class _Ret, class _Tp>
class mem_fun_t : public unary_function<_Tp*,_Ret> {
public:
  explicit mem_fun_t(_Ret (_Tp::*__pf)()) : _M_f(__pf) {}
  _Ret operator()(_Tp* __p) const { return (__p->*_M_f)(); }
private:
  _Ret (_Tp::*_M_f)();
};

template <class _Ret, class _Tp>
class const_mem_fun_t : public unary_function<const _Tp*,_Ret> {
public:
  explicit const_mem_fun_t(_Ret (_Tp::*__pf)() const) : _M_f(__pf) {}
  _Ret operator()(const _Tp* __p) const { return (__p->*_M_f)(); }
private:
  _Ret (_Tp::*_M_f)() const;
};


template <class _Ret, class _Tp>
class mem_fun_ref_t : public unary_function<_Tp,_Ret> {
public:
  explicit mem_fun_ref_t(_Ret (_Tp::*__pf)()) : _M_f(__pf) {}
  _Ret operator()(_Tp& __r) const { return (__r.*_M_f)(); }
private:
  _Ret (_Tp::*_M_f)();
};

template <class _Ret, class _Tp>
class const_mem_fun_ref_t : public unary_function<_Tp,_Ret> {
public:
  explicit const_mem_fun_ref_t(_Ret (_Tp::*__pf)() const) : _M_f(__pf) {}
  _Ret operator()(const _Tp& __r) const { return (__r.*_M_f)(); }
private:
  _Ret (_Tp::*_M_f)() const;
};

template <class _Ret, class _Tp, class _Arg>
class mem_fun1_t : public binary_function<_Tp*,_Arg,_Ret> {
public:
  explicit mem_fun1_t(_Ret (_Tp::*__pf)(_Arg)) : _M_f(__pf) {}
  _Ret operator()(_Tp* __p, _Arg __x) const { return (__p->*_M_f)(__x); }
private:
  _Ret (_Tp::*_M_f)(_Arg);
};

template <class _Ret, class _Tp, class _Arg>
class const_mem_fun1_t : public binary_function<const _Tp*,_Arg,_Ret> {
public:
  explicit const_mem_fun1_t(_Ret (_Tp::*__pf)(_Arg) const) : _M_f(__pf) {}
  _Ret operator()(const _Tp* __p, _Arg __x) const
    { return (__p->*_M_f)(__x); }
private:
  _Ret (_Tp::*_M_f)(_Arg) const;
};

template <class _Ret, class _Tp, class _Arg>
class mem_fun1_ref_t : public binary_function<_Tp,_Arg,_Ret> {
public:
  explicit mem_fun1_ref_t(_Ret (_Tp::*__pf)(_Arg)) : _M_f(__pf) {}
  _Ret operator()(_Tp& __r, _Arg __x) const { return (__r.*_M_f)(__x); }
private:
  _Ret (_Tp::*_M_f)(_Arg);
};

template <class _Ret, class _Tp, class _Arg>
class const_mem_fun1_ref_t : public binary_function<_Tp,_Arg,_Ret> {
public:
  explicit const_mem_fun1_ref_t(_Ret (_Tp::*__pf)(_Arg) const) : _M_f(__pf) {}
  _Ret operator()(const _Tp& __r, _Arg __x) const { return (__r.*_M_f)(__x); }
private:
  _Ret (_Tp::*_M_f)(_Arg) const;
};

template <class _Tp>
class mem_fun_t<void, _Tp> : public unary_function<_Tp*,void> {
public:
  explicit mem_fun_t(void (_Tp::*__pf)()) : _M_f(__pf) {}
  void operator()(_Tp* __p) const { (__p->*_M_f)(); }
private:
  void (_Tp::*_M_f)();
};

template <class _Tp>
class const_mem_fun_t<void, _Tp> : public unary_function<const _Tp*,void> {
public:
  explicit const_mem_fun_t(void (_Tp::*__pf)() const) : _M_f(__pf) {}
  void operator()(const _Tp* __p) const { (__p->*_M_f)(); }
private:
  void (_Tp::*_M_f)() const;
};

template <class _Tp>
class mem_fun_ref_t<void, _Tp> : public unary_function<_Tp,void> {
public:
  explicit mem_fun_ref_t(void (_Tp::*__pf)()) : _M_f(__pf) {}
  void operator()(_Tp& __r) const { (__r.*_M_f)(); }
private:
  void (_Tp::*_M_f)();
};

template <class _Tp>
class const_mem_fun_ref_t<void, _Tp> : public unary_function<_Tp,void> {
public:
  explicit const_mem_fun_ref_t(void (_Tp::*__pf)() const) : _M_f(__pf) {}
  void operator()(const _Tp& __r) const { (__r.*_M_f)(); }
private:
  void (_Tp::*_M_f)() const;
};

template <class _Tp, class _Arg>
class mem_fun1_t<void, _Tp, _Arg> : public binary_function<_Tp*,_Arg,void> {
public:
  explicit mem_fun1_t(void (_Tp::*__pf)(_Arg)) : _M_f(__pf) {}
  void operator()(_Tp* __p, _Arg __x) const { (__p->*_M_f)(__x); }
private:
  void (_Tp::*_M_f)(_Arg);
};

template <class _Tp, class _Arg>
class const_mem_fun1_t<void, _Tp, _Arg>
  : public binary_function<const _Tp*,_Arg,void> {
public:
  explicit const_mem_fun1_t(void (_Tp::*__pf)(_Arg) const) : _M_f(__pf) {}
  void operator()(const _Tp* __p, _Arg __x) const { (__p->*_M_f)(__x); }
private:
  void (_Tp::*_M_f)(_Arg) const;
};

template <class _Tp, class _Arg>
class mem_fun1_ref_t<void, _Tp, _Arg>
  : public binary_function<_Tp,_Arg,void> {
public:
  explicit mem_fun1_ref_t(void (_Tp::*__pf)(_Arg)) : _M_f(__pf) {}
  void operator()(_Tp& __r, _Arg __x) const { (__r.*_M_f)(__x); }
private:
  void (_Tp::*_M_f)(_Arg);
};

template <class _Tp, class _Arg>
class const_mem_fun1_ref_t<void, _Tp, _Arg>
  : public binary_function<_Tp,_Arg,void> {
public:
  explicit const_mem_fun1_ref_t(void (_Tp::*__pf)(_Arg) const) : _M_f(__pf) {}
  void operator()(const _Tp& __r, _Arg __x) const { (__r.*_M_f)(__x); }
private:
  void (_Tp::*_M_f)(_Arg) const;
};







template <class _Ret, class _Tp>
inline mem_fun_t<_Ret,_Tp> mem_fun(_Ret (_Tp::*__f)())
  { return mem_fun_t<_Ret,_Tp>(__f); }

template <class _Ret, class _Tp>
inline const_mem_fun_t<_Ret,_Tp> mem_fun(_Ret (_Tp::*__f)() const)
  { return const_mem_fun_t<_Ret,_Tp>(__f); }

template <class _Ret, class _Tp>
inline mem_fun_ref_t<_Ret,_Tp> mem_fun_ref(_Ret (_Tp::*__f)())
  { return mem_fun_ref_t<_Ret,_Tp>(__f); }

template <class _Ret, class _Tp>
inline const_mem_fun_ref_t<_Ret,_Tp> mem_fun_ref(_Ret (_Tp::*__f)() const)
  { return const_mem_fun_ref_t<_Ret,_Tp>(__f); }

template <class _Ret, class _Tp, class _Arg>
inline mem_fun1_t<_Ret,_Tp,_Arg> mem_fun(_Ret (_Tp::*__f)(_Arg))
  { return mem_fun1_t<_Ret,_Tp,_Arg>(__f); }

template <class _Ret, class _Tp, class _Arg>
inline const_mem_fun1_t<_Ret,_Tp,_Arg> mem_fun(_Ret (_Tp::*__f)(_Arg) const)
  { return const_mem_fun1_t<_Ret,_Tp,_Arg>(__f); }

template <class _Ret, class _Tp, class _Arg>
inline mem_fun1_ref_t<_Ret,_Tp,_Arg> mem_fun_ref(_Ret (_Tp::*__f)(_Arg))
  { return mem_fun1_ref_t<_Ret,_Tp,_Arg>(__f); }

template <class _Ret, class _Tp, class _Arg>
inline const_mem_fun1_ref_t<_Ret,_Tp,_Arg>
mem_fun_ref(_Ret (_Tp::*__f)(_Arg) const)
  { return const_mem_fun1_ref_t<_Ret,_Tp,_Arg>(__f); }

template <class _Ret, class _Tp, class _Arg>
inline mem_fun1_t<_Ret,_Tp,_Arg> mem_fun1(_Ret (_Tp::*__f)(_Arg))
  { return mem_fun1_t<_Ret,_Tp,_Arg>(__f); }

template <class _Ret, class _Tp, class _Arg>
inline const_mem_fun1_t<_Ret,_Tp,_Arg> mem_fun1(_Ret (_Tp::*__f)(_Arg) const)
  { return const_mem_fun1_t<_Ret,_Tp,_Arg>(__f); }

template <class _Ret, class _Tp, class _Arg>
inline mem_fun1_ref_t<_Ret,_Tp,_Arg> mem_fun1_ref(_Ret (_Tp::*__f)(_Arg))
  { return mem_fun1_ref_t<_Ret,_Tp,_Arg>(__f); }

template <class _Ret, class _Tp, class _Arg>
inline const_mem_fun1_ref_t<_Ret,_Tp,_Arg>
mem_fun1_ref(_Ret (_Tp::*__f)(_Arg) const)
  { return const_mem_fun1_ref_t<_Ret,_Tp,_Arg>(__f); }

}
# 89 "/usr/include/g++-v3/bits/stl_tree.h" 2 3

namespace std
{

typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false;
const _Rb_tree_Color_type _S_rb_tree_black = true;

struct _Rb_tree_node_base
{
  typedef _Rb_tree_Color_type _Color_type;
  typedef _Rb_tree_node_base* _Base_ptr;

  _Color_type _M_color;
  _Base_ptr _M_parent;
  _Base_ptr _M_left;
  _Base_ptr _M_right;

  static _Base_ptr _S_minimum(_Base_ptr __x)
  {
    while (__x->_M_left != 0) __x = __x->_M_left;
    return __x;
  }

  static _Base_ptr _S_maximum(_Base_ptr __x)
  {
    while (__x->_M_right != 0) __x = __x->_M_right;
    return __x;
  }
};

template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{
  typedef _Rb_tree_node<_Value>* _Link_type;
  _Value _M_value_field;
};


struct _Rb_tree_base_iterator
{
  typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
  typedef bidirectional_iterator_tag iterator_category;
  typedef ptrdiff_t difference_type;
  _Base_ptr _M_node;

  void _M_increment()
  {
    if (_M_node->_M_right != 0) {
      _M_node = _M_node->_M_right;
      while (_M_node->_M_left != 0)
        _M_node = _M_node->_M_left;
    }
    else {
      _Base_ptr __y = _M_node->_M_parent;
      while (_M_node == __y->_M_right) {
        _M_node = __y;
        __y = __y->_M_parent;
      }
      if (_M_node->_M_right != __y)
        _M_node = __y;
    }
  }

  void _M_decrement()
  {
    if (_M_node->_M_color == _S_rb_tree_red &&
        _M_node->_M_parent->_M_parent == _M_node)
      _M_node = _M_node->_M_right;
    else if (_M_node->_M_left != 0) {
      _Base_ptr __y = _M_node->_M_left;
      while (__y->_M_right != 0)
        __y = __y->_M_right;
      _M_node = __y;
    }
    else {
      _Base_ptr __y = _M_node->_M_parent;
      while (_M_node == __y->_M_left) {
        _M_node = __y;
        __y = __y->_M_parent;
      }
      _M_node = __y;
    }
  }
};

template <class _Value, class _Ref, class _Ptr>
struct _Rb_tree_iterator : public _Rb_tree_base_iterator
{
  typedef _Value value_type;
  typedef _Ref reference;
  typedef _Ptr pointer;
  typedef _Rb_tree_iterator<_Value, _Value&, _Value*>
    iterator;
  typedef _Rb_tree_iterator<_Value, const _Value&, const _Value*>
    const_iterator;
  typedef _Rb_tree_iterator<_Value, _Ref, _Ptr>
    _Self;
  typedef _Rb_tree_node<_Value>* _Link_type;

  _Rb_tree_iterator() {}
  _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
  _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }

  reference operator*() const { return _Link_type(_M_node)->_M_value_field; }
  pointer operator->() const { return &(operator*()); }

  _Self& operator++() { _M_increment(); return *this; }
  _Self operator++(int) {
    _Self __tmp = *this;
    _M_increment();
    return __tmp;
  }

  _Self& operator--() { _M_decrement(); return *this; }
  _Self operator--(int) {
    _Self __tmp = *this;
    _M_decrement();
    return __tmp;
  }
};

template <class _Value, class _Ref, class _Ptr>
inline bool operator==(const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __x,
                       const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __y) {
  return __x._M_node == __y._M_node;
}

template <class _Value>
inline bool operator==(const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __x,
                       const _Rb_tree_iterator<_Value, _Value&, _Value*>& __y) {
  return __x._M_node == __y._M_node;
}

template <class _Value>
inline bool operator==(const _Rb_tree_iterator<_Value, _Value&, _Value*>& __x,
                       const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __y) {
  return __x._M_node == __y._M_node;
}

template <class _Value, class _Ref, class _Ptr>
inline bool operator!=(const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __x,
                       const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __y) {
  return __x._M_node != __y._M_node;
}

template <class _Value>
inline bool operator!=(const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __x,
                       const _Rb_tree_iterator<_Value, _Value&, _Value*>& __y) {
  return __x._M_node != __y._M_node;
}

template <class _Value>
inline bool operator!=(const _Rb_tree_iterator<_Value, _Value&, _Value*>& __x,
                       const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __y) {
  return __x._M_node != __y._M_node;
}

inline void
_Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
  _Rb_tree_node_base* __y = __x->_M_right;
  __x->_M_right = __y->_M_left;
  if (__y->_M_left !=0)
    __y->_M_left->_M_parent = __x;
  __y->_M_parent = __x->_M_parent;

  if (__x == __root)
    __root = __y;
  else if (__x == __x->_M_parent->_M_left)
    __x->_M_parent->_M_left = __y;
  else
    __x->_M_parent->_M_right = __y;
  __y->_M_left = __x;
  __x->_M_parent = __y;
}

inline void
_Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
  _Rb_tree_node_base* __y = __x->_M_left;
  __x->_M_left = __y->_M_right;
  if (__y->_M_right != 0)
    __y->_M_right->_M_parent = __x;
  __y->_M_parent = __x->_M_parent;

  if (__x == __root)
    __root = __y;
  else if (__x == __x->_M_parent->_M_right)
    __x->_M_parent->_M_right = __y;
  else
    __x->_M_parent->_M_left = __y;
  __y->_M_right = __x;
  __x->_M_parent = __y;
}

inline void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
  __x->_M_color = _S_rb_tree_red;
  while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
    if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
      _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
      if (__y && __y->_M_color == _S_rb_tree_red) {
        __x->_M_parent->_M_color = _S_rb_tree_black;
        __y->_M_color = _S_rb_tree_black;
        __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
        __x = __x->_M_parent->_M_parent;
      }
      else {
        if (__x == __x->_M_parent->_M_right) {
          __x = __x->_M_parent;
          _Rb_tree_rotate_left(__x, __root);
        }
        __x->_M_parent->_M_color = _S_rb_tree_black;
        __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
        _Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);
      }
    }
    else {
      _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
      if (__y && __y->_M_color == _S_rb_tree_red) {
        __x->_M_parent->_M_color = _S_rb_tree_black;
        __y->_M_color = _S_rb_tree_black;
        __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
        __x = __x->_M_parent->_M_parent;
      }
      else {
        if (__x == __x->_M_parent->_M_left) {
          __x = __x->_M_parent;
          _Rb_tree_rotate_right(__x, __root);
        }
        __x->_M_parent->_M_color = _S_rb_tree_black;
        __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
        _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
      }
    }
  }
  __root->_M_color = _S_rb_tree_black;
}

inline _Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z,
                             _Rb_tree_node_base*& __root,
                             _Rb_tree_node_base*& __leftmost,
                             _Rb_tree_node_base*& __rightmost)
{
  _Rb_tree_node_base* __y = __z;
  _Rb_tree_node_base* __x = 0;
  _Rb_tree_node_base* __x_parent = 0;
  if (__y->_M_left == 0)
    __x = __y->_M_right;
  else
    if (__y->_M_right == 0)
      __x = __y->_M_left;
    else {
      __y = __y->_M_right;
      while (__y->_M_left != 0)
        __y = __y->_M_left;
      __x = __y->_M_right;
    }
  if (__y != __z) {
    __z->_M_left->_M_parent = __y;
    __y->_M_left = __z->_M_left;
    if (__y != __z->_M_right) {
      __x_parent = __y->_M_parent;
      if (__x) __x->_M_parent = __y->_M_parent;
      __y->_M_parent->_M_left = __x;
      __y->_M_right = __z->_M_right;
      __z->_M_right->_M_parent = __y;
    }
    else
      __x_parent = __y;
    if (__root == __z)
      __root = __y;
    else if (__z->_M_parent->_M_left == __z)
      __z->_M_parent->_M_left = __y;
    else
      __z->_M_parent->_M_right = __y;
    __y->_M_parent = __z->_M_parent;
    std::swap(__y->_M_color, __z->_M_color);
    __y = __z;

  }
  else {
    __x_parent = __y->_M_parent;
    if (__x) __x->_M_parent = __y->_M_parent;
    if (__root == __z)
      __root = __x;
    else
      if (__z->_M_parent->_M_left == __z)
        __z->_M_parent->_M_left = __x;
      else
        __z->_M_parent->_M_right = __x;
    if (__leftmost == __z)
      if (__z->_M_right == 0)
        __leftmost = __z->_M_parent;

      else
        __leftmost = _Rb_tree_node_base::_S_minimum(__x);
    if (__rightmost == __z)
      if (__z->_M_left == 0)
        __rightmost = __z->_M_parent;

      else
        __rightmost = _Rb_tree_node_base::_S_maximum(__x);
  }
  if (__y->_M_color != _S_rb_tree_red) {
    while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
      if (__x == __x_parent->_M_left) {
        _Rb_tree_node_base* __w = __x_parent->_M_right;
        if (__w->_M_color == _S_rb_tree_red) {
          __w->_M_color = _S_rb_tree_black;
          __x_parent->_M_color = _S_rb_tree_red;
          _Rb_tree_rotate_left(__x_parent, __root);
          __w = __x_parent->_M_right;
        }
        if ((__w->_M_left == 0 ||
             __w->_M_left->_M_color == _S_rb_tree_black) &&
            (__w->_M_right == 0 ||
             __w->_M_right->_M_color == _S_rb_tree_black)) {
          __w->_M_color = _S_rb_tree_red;
          __x = __x_parent;
          __x_parent = __x_parent->_M_parent;
        } else {
          if (__w->_M_right == 0 ||
              __w->_M_right->_M_color == _S_rb_tree_black) {
            if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
            __w->_M_color = _S_rb_tree_red;
            _Rb_tree_rotate_right(__w, __root);
            __w = __x_parent->_M_right;
          }
          __w->_M_color = __x_parent->_M_color;
          __x_parent->_M_color = _S_rb_tree_black;
          if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
          _Rb_tree_rotate_left(__x_parent, __root);
          break;
        }
      } else {
        _Rb_tree_node_base* __w = __x_parent->_M_left;
        if (__w->_M_color == _S_rb_tree_red) {
          __w->_M_color = _S_rb_tree_black;
          __x_parent->_M_color = _S_rb_tree_red;
          _Rb_tree_rotate_right(__x_parent, __root);
          __w = __x_parent->_M_left;
        }
        if ((__w->_M_right == 0 ||
             __w->_M_right->_M_color == _S_rb_tree_black) &&
            (__w->_M_left == 0 ||
             __w->_M_left->_M_color == _S_rb_tree_black)) {
          __w->_M_color = _S_rb_tree_red;
          __x = __x_parent;
          __x_parent = __x_parent->_M_parent;
        } else {
          if (__w->_M_left == 0 ||
              __w->_M_left->_M_color == _S_rb_tree_black) {
            if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
            __w->_M_color = _S_rb_tree_red;
            _Rb_tree_rotate_left(__w, __root);
            __w = __x_parent->_M_left;
          }
          __w->_M_color = __x_parent->_M_color;
          __x_parent->_M_color = _S_rb_tree_black;
          if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
          _Rb_tree_rotate_right(__x_parent, __root);
          break;
        }
      }
    if (__x) __x->_M_color = _S_rb_tree_black;
  }
  return __y;
}







template <class _Tp, class _Alloc, bool _S_instanceless>
class _Rb_tree_alloc_base {
public:
  typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
  allocator_type get_allocator() const { return _M_node_allocator; }

  _Rb_tree_alloc_base(const allocator_type& __a)
    : _M_node_allocator(__a), _M_header(0) {}

protected:
  typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type
           _M_node_allocator;
  _Rb_tree_node<_Tp>* _M_header;

  _Rb_tree_node<_Tp>* _M_get_node()
    { return _M_node_allocator.allocate(1); }
  void _M_put_node(_Rb_tree_node<_Tp>* __p)
    { _M_node_allocator.deallocate(__p, 1); }
};


template <class _Tp, class _Alloc>
class _Rb_tree_alloc_base<_Tp, _Alloc, true> {
public:
  typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }

  _Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {}

protected:
  _Rb_tree_node<_Tp>* _M_header;

  typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type
          _Alloc_type;

  _Rb_tree_node<_Tp>* _M_get_node()
    { return _Alloc_type::allocate(1); }
  void _M_put_node(_Rb_tree_node<_Tp>* __p)
    { _Alloc_type::deallocate(__p, 1); }
};

template <class _Tp, class _Alloc>
struct _Rb_tree_base
  : public _Rb_tree_alloc_base<_Tp, _Alloc,
                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
  typedef _Rb_tree_alloc_base<_Tp, _Alloc,
                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
          _Base;
  typedef typename _Base::allocator_type allocator_type;

  _Rb_tree_base(const allocator_type& __a)
    : _Base(__a) { _M_header = _M_get_node(); }
  ~_Rb_tree_base() { _M_put_node(_M_header); }

};


template <class _Key, class _Value, class _KeyOfValue, class _Compare,
          class _Alloc = allocator<_Value> >
class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc> {
  typedef _Rb_tree_base<_Value, _Alloc> _Base;
protected:
  typedef _Rb_tree_node_base* _Base_ptr;
  typedef _Rb_tree_node<_Value> _Rb_tree_node;
  typedef _Rb_tree_Color_type _Color_type;
public:
  typedef _Key key_type;
  typedef _Value value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef _Rb_tree_node* _Link_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;

  typedef typename _Base::allocator_type allocator_type;
  allocator_type get_allocator() const { return _Base::get_allocator(); }

protected:
  using _Base::_M_get_node;
  using _Base::_M_put_node;
  using _Base::_M_header;

protected:

  _Link_type _M_create_node(const value_type& __x)
  {
    _Link_type __tmp = _M_get_node();
    try {
      construct(&__tmp->_M_value_field, __x);
    }
    catch(...) { _M_put_node(__tmp); throw; };
    return __tmp;
  }

  _Link_type _M_clone_node(_Link_type __x)
  {
    _Link_type __tmp = _M_create_node(__x->_M_value_field);
    __tmp->_M_color = __x->_M_color;
    __tmp->_M_left = 0;
    __tmp->_M_right = 0;
    return __tmp;
  }

  void destroy_node(_Link_type __p)
  {
    destroy(&__p->_M_value_field);
    _M_put_node(__p);
  }

protected:
  size_type _M_node_count;
  _Compare _M_key_compare;

  _Link_type& _M_root() const
    { return (_Link_type&) _M_header->_M_parent; }
  _Link_type& _M_leftmost() const
    { return (_Link_type&) _M_header->_M_left; }
  _Link_type& _M_rightmost() const
    { return (_Link_type&) _M_header->_M_right; }

  static _Link_type& _S_left(_Link_type __x)
    { return (_Link_type&)(__x->_M_left); }
  static _Link_type& _S_right(_Link_type __x)
    { return (_Link_type&)(__x->_M_right); }
  static _Link_type& _S_parent(_Link_type __x)
    { return (_Link_type&)(__x->_M_parent); }
  static reference _S_value(_Link_type __x)
    { return __x->_M_value_field; }
  static const _Key& _S_key(_Link_type __x)
    { return _KeyOfValue()(_S_value(__x)); }
  static _Color_type& _S_color(_Link_type __x)
    { return (_Color_type&)(__x->_M_color); }

  static _Link_type& _S_left(_Base_ptr __x)
    { return (_Link_type&)(__x->_M_left); }
  static _Link_type& _S_right(_Base_ptr __x)
    { return (_Link_type&)(__x->_M_right); }
  static _Link_type& _S_parent(_Base_ptr __x)
    { return (_Link_type&)(__x->_M_parent); }
  static reference _S_value(_Base_ptr __x)
    { return ((_Link_type)__x)->_M_value_field; }
  static const _Key& _S_key(_Base_ptr __x)
    { return _KeyOfValue()(_S_value(_Link_type(__x)));}
  static _Color_type& _S_color(_Base_ptr __x)
    { return (_Color_type&)(_Link_type(__x)->_M_color); }

  static _Link_type _S_minimum(_Link_type __x)
    { return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); }

  static _Link_type _S_maximum(_Link_type __x)
    { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }

public:
  typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
  typedef _Rb_tree_iterator<value_type, const_reference, const_pointer>
          const_iterator;

  typedef reverse_iterator<const_iterator> const_reverse_iterator;
  typedef reverse_iterator<iterator> reverse_iterator;

private:
  iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
  _Link_type _M_copy(_Link_type __x, _Link_type __p);
  void _M_erase(_Link_type __x);

public:

  _Rb_tree()
    : _Base(allocator_type()), _M_node_count(0), _M_key_compare()
    { _M_empty_initialize(); }

  _Rb_tree(const _Compare& __comp)
    : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp)
    { _M_empty_initialize(); }

  _Rb_tree(const _Compare& __comp, const allocator_type& __a)
    : _Base(__a), _M_node_count(0), _M_key_compare(__comp)
    { _M_empty_initialize(); }

  _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
    : _Base(__x.get_allocator()),
      _M_node_count(0), _M_key_compare(__x._M_key_compare)
  {
    if (__x._M_root() == 0)
      _M_empty_initialize();
    else {
      _S_color(_M_header) = _S_rb_tree_red;
      _M_root() = _M_copy(__x._M_root(), _M_header);
      _M_leftmost() = _S_minimum(_M_root());
      _M_rightmost() = _S_maximum(_M_root());
    }
    _M_node_count = __x._M_node_count;
  }
  ~_Rb_tree() { clear(); }
  _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>&
  operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x);

private:
  void _M_empty_initialize() {
    _S_color(_M_header) = _S_rb_tree_red;

    _M_root() = 0;
    _M_leftmost() = _M_header;
    _M_rightmost() = _M_header;
  }

public:

  _Compare key_comp() const { return _M_key_compare; }
  iterator begin() { return _M_leftmost(); }
  const_iterator begin() const { return _M_leftmost(); }
  iterator end() { return _M_header; }
  const_iterator end() const { return _M_header; }
  reverse_iterator rbegin() { return reverse_iterator(end()); }
  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(end());
  }
  reverse_iterator rend() { return reverse_iterator(begin()); }
  const_reverse_iterator rend() const {
    return const_reverse_iterator(begin());
  }
  bool empty() const { return _M_node_count == 0; }
  size_type size() const { return _M_node_count; }
  size_type max_size() const { return size_type(-1); }

  void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) {
    std::swap(_M_header, __t._M_header);
    std::swap(_M_node_count, __t._M_node_count);
    std::swap(_M_key_compare, __t._M_key_compare);
  }

public:

  pair<iterator,bool> insert_unique(const value_type& __x);
  iterator insert_equal(const value_type& __x);

  iterator insert_unique(iterator __position, const value_type& __x);
  iterator insert_equal(iterator __position, const value_type& __x);

  template <class _InputIterator>
  void insert_unique(_InputIterator __first, _InputIterator __last);
  template <class _InputIterator>
  void insert_equal(_InputIterator __first, _InputIterator __last);

  void erase(iterator __position);
  size_type erase(const key_type& __x);
  void erase(iterator __first, iterator __last);
  void erase(const key_type* __first, const key_type* __last);
  void clear() {
    if (_M_node_count != 0) {
      _M_erase(_M_root());
      _M_leftmost() = _M_header;
      _M_root() = 0;
      _M_rightmost() = _M_header;
      _M_node_count = 0;
    }
  }

public:

  iterator find(const key_type& __x);
  const_iterator find(const key_type& __x) const;
  size_type count(const key_type& __x) const;
  iterator lower_bound(const key_type& __x);
  const_iterator lower_bound(const key_type& __x) const;
  iterator upper_bound(const key_type& __x);
  const_iterator upper_bound(const key_type& __x) const;
  pair<iterator,iterator> equal_range(const key_type& __x);
  pair<const_iterator, const_iterator> equal_range(const key_type& __x) const;

public:

  bool __rb_verify() const;
};

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
inline bool
operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
  return __x.size() == __y.size() &&
         equal(__x.begin(), __x.end(), __y.begin());
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
inline bool
operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
          const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
  return lexicographical_compare(__x.begin(), __x.end(),
                                 __y.begin(), __y.end());
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
inline bool
operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  return !(__x == __y);
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
inline bool
operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
          const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  return __y < __x;
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
inline bool
operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  return !(__y < __x);
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
inline bool
operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
  return !(__x < __y);
}


template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
inline void
swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x,
     _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
{
  __x.swap(__y);
}


template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>&
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x)
{
  if (this != &__x) {

    clear();
    _M_node_count = 0;
    _M_key_compare = __x._M_key_compare;
    if (__x._M_root() == 0) {
      _M_root() = 0;
      _M_leftmost() = _M_header;
      _M_rightmost() = _M_header;
    }
    else {
      _M_root() = _M_copy(__x._M_root(), _M_header);
      _M_leftmost() = _S_minimum(_M_root());
      _M_rightmost() = _S_maximum(_M_root());
      _M_node_count = __x._M_node_count;
    }
  }
  return *this;
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v)
{
  _Link_type __x = (_Link_type) __x_;
  _Link_type __y = (_Link_type) __y_;
  _Link_type __z;

  if (__y == _M_header || __x != 0 ||
      _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) {
    __z = _M_create_node(__v);
    _S_left(__y) = __z;

    if (__y == _M_header) {
      _M_root() = __z;
      _M_rightmost() = __z;
    }
    else if (__y == _M_leftmost())
      _M_leftmost() = __z;
  }
  else {
    __z = _M_create_node(__v);
    _S_right(__y) = __z;
    if (__y == _M_rightmost())
      _M_rightmost() = __z;
  }
  _S_parent(__z) = __y;
  _S_left(__z) = 0;
  _S_right(__z) = 0;
  _Rb_tree_rebalance(__z, _M_header->_M_parent);
  ++_M_node_count;
  return iterator(__z);
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::insert_equal(const _Value& __v)
{
  _Link_type __y = _M_header;
  _Link_type __x = _M_root();
  while (__x != 0) {
    __y = __x;
    __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
            _S_left(__x) : _S_right(__x);
  }
  return _M_insert(__x, __y, __v);
}


template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
     bool>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::insert_unique(const _Value& __v)
{
  _Link_type __y = _M_header;
  _Link_type __x = _M_root();
  bool __comp = true;
  while (__x != 0) {
    __y = __x;
    __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
    __x = __comp ? _S_left(__x) : _S_right(__x);
  }
  iterator __j = iterator(__y);
  if (__comp)
    if (__j == begin())
      return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
    else
      --__j;
  if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
    return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
  return pair<iterator,bool>(__j, false);
}


template <class _Key, class _Val, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>
  ::insert_unique(iterator __position, const _Val& __v)
{
  if (__position._M_node == _M_header->_M_left) {
    if (size() > 0 &&
       _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
      return _M_insert(__position._M_node, __position._M_node, __v);

    else
      return insert_unique(__v).first;
  } else if (__position._M_node == _M_header) {
    if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
      return _M_insert(0, _M_rightmost(), __v);
    else
      return insert_unique(__v).first;
  } else {
    iterator __before = __position;
    --__before;
    if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v))
        && _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) {
      if (_S_right(__before._M_node) == 0)
        return _M_insert(0, __before._M_node, __v);
      else
        return _M_insert(__position._M_node, __position._M_node, __v);

    } else
      return insert_unique(__v).first;
  }
}

template <class _Key, class _Val, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>
  ::insert_equal(iterator __position, const _Val& __v)
{
  if (__position._M_node == _M_header->_M_left) {
    if (size() > 0 &&
        !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)))
      return _M_insert(__position._M_node, __position._M_node, __v);

    else
      return insert_equal(__v);
  } else if (__position._M_node == _M_header) {
    if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
      return _M_insert(0, _M_rightmost(), __v);
    else
      return insert_equal(__v);
  } else {
    iterator __before = __position;
    --__before;
    if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))
        && !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) {
      if (_S_right(__before._M_node) == 0)
        return _M_insert(0, __before._M_node, __v);
      else
        return _M_insert(__position._M_node, __position._M_node, __v);

    } else
      return insert_equal(__v);
  }
}

template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
  template<class _II>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
  ::insert_equal(_II __first, _II __last)
{
  for ( ; __first != __last; ++__first)
    insert_equal(*__first);
}

template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
  template<class _II>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
  ::insert_unique(_II __first, _II __last) {
  for ( ; __first != __last; ++__first)
    insert_unique(*__first);
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
inline void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::erase(iterator __position)
{
  _Link_type __y =
    (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
                                              _M_header->_M_parent,
                                              _M_header->_M_left,
                                              _M_header->_M_right);
  destroy_node(__y);
  --_M_node_count;
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
{
  pair<iterator,iterator> __p = equal_range(__x);
  size_type __n = 0;
  distance(__p.first, __p.second, __n);
  erase(__p.first, __p.second);
  return __n;
}

template <class _Key, class _Val, class _KoV, class _Compare, class _Alloc>
typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
_Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>
  ::_M_copy(_Link_type __x, _Link_type __p)
{

  _Link_type __top = _M_clone_node(__x);
  __top->_M_parent = __p;

  try {
    if (__x->_M_right)
      __top->_M_right = _M_copy(_S_right(__x), __top);
    __p = __top;
    __x = _S_left(__x);

    while (__x != 0) {
      _Link_type __y = _M_clone_node(__x);
      __p->_M_left = __y;
      __y->_M_parent = __p;
      if (__x->_M_right)
        __y->_M_right = _M_copy(_S_right(__x), __y);
      __p = __y;
      __x = _S_left(__x);
    }
  }
  catch(...) { _M_erase(__top); throw; };

  return __top;
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::_M_erase(_Link_type __x)
{

  while (__x != 0) {
    _M_erase(_S_right(__x));
    _Link_type __y = _S_left(__x);
    destroy_node(__x);
    __x = __y;
  }
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::erase(iterator __first, iterator __last)
{
  if (__first == begin() && __last == end())
    clear();
  else
    while (__first != __last) erase(__first++);
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::erase(const _Key* __first, const _Key* __last)
{
  while (__first != __last) erase(*__first++);
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
{
  _Link_type __y = _M_header;
  _Link_type __x = _M_root();

  while (__x != 0)
    if (!_M_key_compare(_S_key(__x), __k))
      __y = __x, __x = _S_left(__x);
    else
      __x = _S_right(__x);

  iterator __j = iterator(__y);
  return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
     end() : __j;
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) const
{
  _Link_type __y = _M_header;
  _Link_type __x = _M_root();

  while (__x != 0) {
    if (!_M_key_compare(_S_key(__x), __k))
      __y = __x, __x = _S_left(__x);
    else
      __x = _S_right(__x);
  }
  const_iterator __j = const_iterator(__y);
  return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
    end() : __j;
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::count(const _Key& __k) const
{
  pair<const_iterator, const_iterator> __p = equal_range(__k);
  size_type __n = 0;
  distance(__p.first, __p.second, __n);
  return __n;
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::lower_bound(const _Key& __k)
{
  _Link_type __y = _M_header;
  _Link_type __x = _M_root();

  while (__x != 0)
    if (!_M_key_compare(_S_key(__x), __k))
      __y = __x, __x = _S_left(__x);
    else
      __x = _S_right(__x);

  return iterator(__y);
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::lower_bound(const _Key& __k) const
{
  _Link_type __y = _M_header;
  _Link_type __x = _M_root();

  while (__x != 0)
    if (!_M_key_compare(_S_key(__x), __k))
      __y = __x, __x = _S_left(__x);
    else
      __x = _S_right(__x);

  return const_iterator(__y);
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::upper_bound(const _Key& __k)
{
  _Link_type __y = _M_header;
  _Link_type __x = _M_root();

   while (__x != 0)
     if (_M_key_compare(__k, _S_key(__x)))
       __y = __x, __x = _S_left(__x);
     else
       __x = _S_right(__x);

   return iterator(__y);
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::upper_bound(const _Key& __k) const
{
  _Link_type __y = _M_header;
  _Link_type __x = _M_root();

   while (__x != 0)
     if (_M_key_compare(__k, _S_key(__x)))
       __y = __x, __x = _S_left(__x);
     else
       __x = _S_right(__x);

   return const_iterator(__y);
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
inline
pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator,
     typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::equal_range(const _Key& __k)
{
  return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k));
}

template <class _Key, class _Value, class _KoV, class _Compare, class _Alloc>
inline
pair<typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator,
     typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator>
_Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>
  ::equal_range(const _Key& __k) const
{
  return pair<const_iterator,const_iterator>(lower_bound(__k),
                                             upper_bound(__k));
}

inline int
__black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
{
  if (__node == 0)
    return 0;
  int __sum = 0;
  do {
    if (__node->_M_color == _S_rb_tree_black)
      ++__sum;
    if (__node == __root)
      break;
    __node = __node->_M_parent;
  } while (1);
  return __sum;
}

template <class _Key, class _Value, class _KeyOfValue,
          class _Compare, class _Alloc>
bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
{
  if (_M_node_count == 0 || begin() == end())
    return _M_node_count == 0 && begin() == end() &&
      _M_header->_M_left == _M_header && _M_header->_M_right == _M_header;

  int __len = __black_count(_M_leftmost(), _M_root());
  for (const_iterator __it = begin(); __it != end(); ++__it) {
    _Link_type __x = (_Link_type) __it._M_node;
    _Link_type __L = _S_left(__x);
    _Link_type __R = _S_right(__x);

    if (__x->_M_color == _S_rb_tree_red)
      if ((__L && __L->_M_color == _S_rb_tree_red) ||
          (__R && __R->_M_color == _S_rb_tree_red))
        return false;

    if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
      return false;
    if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
      return false;

    if (!__L && !__R && __black_count(__x, _M_root()) != __len)
      return false;
  }

  if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
    return false;
  if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
    return false;

  return true;
}




template <class _Key, class _Value, class _KeyOfValue, class _Compare,
          class _Alloc = allocator<_Value> >
struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>
{
  typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
  typedef typename _Base::allocator_type allocator_type;

  rb_tree(const _Compare& __comp = _Compare(),
          const allocator_type& __a = allocator_type())
    : _Base(__comp, __a) {}

  ~rb_tree() {}
};

}
# 63 "/usr/include/g++-v3/bits/std_map.h" 2 3

# 1 "/usr/include/g++-v3/bits/stl_map.h" 1 3
# 63 "/usr/include/g++-v3/bits/stl_map.h" 3
# 1 "/usr/include/g++-v3/bits/concept_check.h" 1 3
# 64 "/usr/include/g++-v3/bits/stl_map.h" 2 3

namespace std
{

template <class _Key, class _Tp, class _Compare = less<_Key>,
          class _Alloc = allocator<pair<const _Key, _Tp> > >
class map
{

                                                      ;
                                                                               ;

public:

  typedef _Key key_type;
  typedef _Tp data_type;
  typedef _Tp mapped_type;
  typedef pair<const _Key, _Tp> value_type;
  typedef _Compare key_compare;

  class value_compare
    : public binary_function<value_type, value_type, bool> {
  friend class map<_Key,_Tp,_Compare,_Alloc>;
  protected :
    _Compare comp;
    value_compare(_Compare __c) : comp(__c) {}
  public:
    bool operator()(const value_type& __x, const value_type& __y) const {
      return comp(__x.first, __y.first);
    }
  };

private:
  typedef _Rb_tree<key_type, value_type,
                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
  _Rep_type _M_t;
public:
  typedef typename _Rep_type::pointer pointer;
  typedef typename _Rep_type::const_pointer const_pointer;
  typedef typename _Rep_type::reference reference;
  typedef typename _Rep_type::const_reference const_reference;
  typedef typename _Rep_type::iterator iterator;
  typedef typename _Rep_type::const_iterator const_iterator;
  typedef typename _Rep_type::reverse_iterator reverse_iterator;
  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  typedef typename _Rep_type::size_type size_type;
  typedef typename _Rep_type::difference_type difference_type;
  typedef typename _Rep_type::allocator_type allocator_type;



  map() : _M_t(_Compare(), allocator_type()) {}
  explicit map(const _Compare& __comp,
               const allocator_type& __a = allocator_type())
    : _M_t(__comp, __a) {}

  template <class _InputIterator>
  map(_InputIterator __first, _InputIterator __last)
    : _M_t(_Compare(), allocator_type())
    { _M_t.insert_unique(__first, __last); }

  template <class _InputIterator>
  map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
      const allocator_type& __a = allocator_type())
    : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
  map(const map<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}

  map<_Key,_Tp,_Compare,_Alloc>&
  operator=(const map<_Key, _Tp, _Compare, _Alloc>& __x)
  {
    _M_t = __x._M_t;
    return *this;
  }



  key_compare key_comp() const { return _M_t.key_comp(); }
  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
  allocator_type get_allocator() const { return _M_t.get_allocator(); }

  iterator begin() { return _M_t.begin(); }
  const_iterator begin() const { return _M_t.begin(); }
  iterator end() { return _M_t.end(); }
  const_iterator end() const { return _M_t.end(); }
  reverse_iterator rbegin() { return _M_t.rbegin(); }
  const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
  reverse_iterator rend() { return _M_t.rend(); }
  const_reverse_iterator rend() const { return _M_t.rend(); }
  bool empty() const { return _M_t.empty(); }
  size_type size() const { return _M_t.size(); }
  size_type max_size() const { return _M_t.max_size(); }
  _Tp& operator[](const key_type& __k) {
    iterator __i = lower_bound(__k);

    if (__i == end() || key_comp()(__k, (*__i).first))
      __i = insert(__i, value_type(__k, _Tp()));
    return (*__i).second;
  }
  void swap(map<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }



  pair<iterator,bool> insert(const value_type& __x)
    { return _M_t.insert_unique(__x); }
  iterator insert(iterator position, const value_type& __x)
    { return _M_t.insert_unique(position, __x); }
  template <class _InputIterator>
  void insert(_InputIterator __first, _InputIterator __last) {
    _M_t.insert_unique(__first, __last);
  }

  void erase(iterator __position) { _M_t.erase(__position); }
  size_type erase(const key_type& __x) { return _M_t.erase(__x); }
  void erase(iterator __first, iterator __last)
    { _M_t.erase(__first, __last); }
  void clear() { _M_t.clear(); }



  iterator find(const key_type& __x) { return _M_t.find(__x); }
  const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
  size_type count(const key_type& __x) const {
    return _M_t.find(__x) == _M_t.end() ? 0 : 1;
  }
  iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
  const_iterator lower_bound(const key_type& __x) const {
    return _M_t.lower_bound(__x);
  }
  iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
  const_iterator upper_bound(const key_type& __x) const {
    return _M_t.upper_bound(__x);
  }

  pair<iterator,iterator> equal_range(const key_type& __x) {
    return _M_t.equal_range(__x);
  }
  pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
    return _M_t.equal_range(__x);
  }

  template <class _K1, class _T1, class _C1, class _A1>
  friend bool operator== (const map<_K1, _T1, _C1, _A1>&,
                          const map<_K1, _T1, _C1, _A1>&);
  template <class _K1, class _T1, class _C1, class _A1>
  friend bool operator< (const map<_K1, _T1, _C1, _A1>&,
                         const map<_K1, _T1, _C1, _A1>&);
};

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
  return __x._M_t == __y._M_t;
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x,
                      const map<_Key,_Tp,_Compare,_Alloc>& __y) {
  return __x._M_t < __y._M_t;
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
  return !(__x == __y);
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x,
                      const map<_Key,_Tp,_Compare,_Alloc>& __y) {
  return __y < __x;
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
  return !(__y < __x);
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x,
                       const map<_Key,_Tp,_Compare,_Alloc>& __y) {
  return !(__x < __y);
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline void swap(map<_Key,_Tp,_Compare,_Alloc>& __x,
                 map<_Key,_Tp,_Compare,_Alloc>& __y) {
  __x.swap(__y);
}

}
# 65 "/usr/include/g++-v3/bits/std_map.h" 2 3
# 1 "/usr/include/g++-v3/bits/stl_multimap.h" 1 3
# 63 "/usr/include/g++-v3/bits/stl_multimap.h" 3
# 1 "/usr/include/g++-v3/bits/concept_check.h" 1 3
# 64 "/usr/include/g++-v3/bits/stl_multimap.h" 2 3

namespace std
{



template <class _Key, class _Tp,
          class _Compare = less<_Key>,
          class _Alloc = allocator<pair<const _Key, _Tp> > >
class multimap;

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
                       const multimap<_Key,_Tp,_Compare,_Alloc>& __y);

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
                      const multimap<_Key,_Tp,_Compare,_Alloc>& __y);

template <class _Key, class _Tp, class _Compare, class _Alloc>
class multimap
{

                                                      ;
                                                                               ;

public:



  typedef _Key key_type;
  typedef _Tp data_type;
  typedef _Tp mapped_type;
  typedef pair<const _Key, _Tp> value_type;
  typedef _Compare key_compare;

  class value_compare : public binary_function<value_type, value_type, bool> {
  friend class multimap<_Key,_Tp,_Compare,_Alloc>;
  protected:
    _Compare comp;
    value_compare(_Compare __c) : comp(__c) {}
  public:
    bool operator()(const value_type& __x, const value_type& __y) const {
      return comp(__x.first, __y.first);
    }
  };

private:
  typedef _Rb_tree<key_type, value_type,
                  _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
  _Rep_type _M_t;
public:
  typedef typename _Rep_type::pointer pointer;
  typedef typename _Rep_type::const_pointer const_pointer;
  typedef typename _Rep_type::reference reference;
  typedef typename _Rep_type::const_reference const_reference;
  typedef typename _Rep_type::iterator iterator;
  typedef typename _Rep_type::const_iterator const_iterator;
  typedef typename _Rep_type::reverse_iterator reverse_iterator;
  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  typedef typename _Rep_type::size_type size_type;
  typedef typename _Rep_type::difference_type difference_type;
  typedef typename _Rep_type::allocator_type allocator_type;



  multimap() : _M_t(_Compare(), allocator_type()) { }
  explicit multimap(const _Compare& __comp,
                    const allocator_type& __a = allocator_type())
    : _M_t(__comp, __a) { }

  template <class _InputIterator>
  multimap(_InputIterator __first, _InputIterator __last)
    : _M_t(_Compare(), allocator_type())
    { _M_t.insert_equal(__first, __last); }

  template <class _InputIterator>
  multimap(_InputIterator __first, _InputIterator __last,
           const _Compare& __comp,
           const allocator_type& __a = allocator_type())
    : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
  multimap(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) : _M_t(__x._M_t) { }

  multimap<_Key,_Tp,_Compare,_Alloc>&
  operator=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x) {
    _M_t = __x._M_t;
    return *this;
  }



  key_compare key_comp() const { return _M_t.key_comp(); }
  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
  allocator_type get_allocator() const { return _M_t.get_allocator(); }

  iterator begin() { return _M_t.begin(); }
  const_iterator begin() const { return _M_t.begin(); }
  iterator end() { return _M_t.end(); }
  const_iterator end() const { return _M_t.end(); }
  reverse_iterator rbegin() { return _M_t.rbegin(); }
  const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
  reverse_iterator rend() { return _M_t.rend(); }
  const_reverse_iterator rend() const { return _M_t.rend(); }
  bool empty() const { return _M_t.empty(); }
  size_type size() const { return _M_t.size(); }
  size_type max_size() const { return _M_t.max_size(); }
  void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }



  iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
  iterator insert(iterator __position, const value_type& __x) {
    return _M_t.insert_equal(__position, __x);
  }
  template <class _InputIterator>
  void insert(_InputIterator __first, _InputIterator __last) {
    _M_t.insert_equal(__first, __last);
  }
  void erase(iterator __position) { _M_t.erase(__position); }
  size_type erase(const key_type& __x) { return _M_t.erase(__x); }
  void erase(iterator __first, iterator __last)
    { _M_t.erase(__first, __last); }
  void clear() { _M_t.clear(); }



  iterator find(const key_type& __x) { return _M_t.find(__x); }
  const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
  size_type count(const key_type& __x) const { return _M_t.count(__x); }
  iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
  const_iterator lower_bound(const key_type& __x) const {
    return _M_t.lower_bound(__x);
  }
  iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
  const_iterator upper_bound(const key_type& __x) const {
    return _M_t.upper_bound(__x);
  }
   pair<iterator,iterator> equal_range(const key_type& __x) {
    return _M_t.equal_range(__x);
  }
  pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
    return _M_t.equal_range(__x);
  }

  template <class _K1, class _T1, class _C1, class _A1>
  friend bool operator== (const multimap<_K1, _T1, _C1, _A1>&,
                          const multimap<_K1, _T1, _C1, _A1>&);
  template <class _K1, class _T1, class _C1, class _A1>
  friend bool operator< (const multimap<_K1, _T1, _C1, _A1>&,
                         const multimap<_K1, _T1, _C1, _A1>&);
};

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
                       const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
  return __x._M_t == __y._M_t;
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
                      const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
  return __x._M_t < __y._M_t;
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator!=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
                       const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
  return !(__x == __y);
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator>(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
                      const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
  return __y < __x;
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator<=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
                       const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
  return !(__y < __x);
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline bool operator>=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x,
                       const multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
  return !(__x < __y);
}

template <class _Key, class _Tp, class _Compare, class _Alloc>
inline void swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x,
                 multimap<_Key,_Tp,_Compare,_Alloc>& __y) {
  __x.swap(__y);
}

}
# 66 "/usr/include/g++-v3/bits/std_map.h" 2 3
# 32 "/usr/include/g++-v3/map" 2 3
# 2 "try.cc" 2

int
main()
{
  std::map<int, int> theMap;

  return 0;
}

>Fix:
	Use --save-temps ;)
>Release-Note:
>Audit-Trail:
>Unformatted:


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]