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++/3606: Internal compiler error in pop_binding, at cp/decl.c:1193



>Number:         3606
>Category:       c++
>Synopsis:       template causes compilation of illegal code to generate ICE
>Confidential:   no
>Severity:       critical
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          ice-on-illegal-code
>Submitter-Id:   net
>Arrival-Date:   Sun Jul 08 00:06:00 PDT 2001
>Closed-Date:
>Last-Modified:
>Originator:     Paul J. Lucas
>Release:        3.0
>Organization:
>Environment:
>Description:
Internal compiler error in pop_binding, at cp/decl.c:1193
>How-To-Repeat:
/*
**	This program, when compiled with g++ 3.0 (powerpc/linux), elicits:
**
**	  bug.c:31: Internal compiler error in pop_binding, at cp/decl.c:1193
**
**	The "typedef int const_iterator;" should produce an error (since the
**	type has been multiply defined), but not an internal compiler error.
**
**	I stumbled across this because, without the typedef, the original code
**	this came from complained that D::const_iterator" wasn't a type later
**	on -- that's wrong too since it was defined -- so I threw the typedef
**	in to see what the compiler would do.
**
**	The bug goes away if struct D is not a template.
*/

#include <list>

struct B {
	typedef std::list< int > L;

	struct iterator : L::iterator { };
	struct const_iterator : L::const_iterator { };
};

template< class T >	// remove this and the ICE goes away
struct D : B {
	struct iterator : B::iterator { };
	struct const_iterator : B::const_iterator { };
	typedef int const_iterator;
};

////////// The End ////////////////////////////////////////////////////////////

Here is the preprocessor output for completeness:

# 18 "bug.c"
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/list" 1 3
# 31 "/usr/local/packages/gcc-3.0/include/g++-v3/list" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_list.h" 1 3
# 31 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_list.h" 3

# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 1 3
# 35 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++config.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++config.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/os_defines.h" 1 3
# 37 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/os_defines.h" 3
# 1 "/usr/include/features.h" 1 3
# 249 "/usr/include/features.h" 3
# 1 "/usr/include/sys/cdefs.h" 1 3
# 250 "/usr/include/features.h" 2 3
# 277 "/usr/include/features.h" 3
# 1 "/usr/include/gnu/stubs.h" 1 3
# 278 "/usr/include/features.h" 2 3
# 38 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/os_defines.h" 2 3
# 35 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++config.h" 2 3
# 36 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3

# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_pair.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/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);
}

template <class _T1, class _T2>


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



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

}
# 38 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3


# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/type_traits.h" 1 3
# 19 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/type_traits.h" 3

# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++config.h" 1 3
# 21 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/type_traits.h" 2 3
# 57 "/usr/local/packages/gcc-3.0/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;
# 81 "/usr/local/packages/gcc-3.0/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;
};
# 41 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3

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

namespace std
{
  using ::ptrdiff_t;
  using ::size_t;
}
# 38 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstring.h" 2 3
# 40 "/usr/local/packages/gcc-3.0/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/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/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 * __dest, __const void * __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 ();



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




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




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

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


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

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[6];


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


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


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





extern char *__strdup (__const char *__s) throw ();
extern char *strdup (__const char *__s) throw ();






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

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




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




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


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

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

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



extern char *__strcasestr (__const char *__haystack, __const char *__needle) throw ();

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




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 ();
# 194 "/usr/include/string.h" 3
extern void * memmem (__const void * __haystack, size_t __haystacklen, __const void * __needle, size_t __needlelen) throw ();




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




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




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



extern char *__strerror_r (int __errnum, char *__buf, size_t __buflen) 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 ();


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


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



extern int __ffs (int __i) throw () __attribute__ ((const));
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 ();
extern int strcasecmp (__const char *__s1, __const char *__s2) throw ();


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






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


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






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





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


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 ();
# 350 "/usr/include/string.h" 3
}
# 41 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstring.h" 2 3
# 66 "/usr/local/packages/gcc-3.0/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); }
}
# 43 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_climits.h" 1 3
# 38 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_climits.h" 3
# 1 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/limits.h" 1 3
# 11 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/limits.h" 3
# 1 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/syslimits.h" 1 3






# 1 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/limits.h" 1 3
# 130 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/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



# 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
# 27 "/usr/include/bits/local_lim.h" 3
# 1 "/usr/include/linux/limits.h" 1 3
# 28 "/usr/include/bits/local_lim.h" 2 3
# 127 "/usr/include/bits/posix1_lim.h" 2 3
# 31 "/usr/include/limits.h" 2 3



# 1 "/usr/include/bits/posix2_lim.h" 1 3
# 35 "/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
# 39 "/usr/include/limits.h" 2 3
# 131 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/limits.h" 2 3
# 8 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/syslimits.h" 2 3
# 12 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/limits.h" 2 3
# 39 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_climits.h" 2 3
# 44 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdlib.h" 1 3
# 37 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdlib.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++config.h" 1 3
# 38 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdlib.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstddef.h" 1 3
# 39 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdlib.h" 2 3
# 41 "/usr/local/packages/gcc-3.0/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/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stddef.h" 1 3
# 34 "/usr/include/stdlib.h" 2 3

extern "C" {





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



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

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

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



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



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 ();
# 132 "/usr/include/stdlib.h" 3
__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 ();
# 157 "/usr/include/stdlib.h" 3
# 1 "/usr/include/xlocale.h" 1 3
# 158 "/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 ();
# 196 "/usr/include/stdlib.h" 3
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 ();
# 333 "/usr/include/stdlib.h" 3
extern char *l64a (long int __n) throw ();


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


# 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/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/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 long int __rlim_t;
typedef __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 long int __swblk_t;

typedef long int __clock_t;


typedef unsigned long int __fd_mask;
# 100 "/usr/include/bits/types.h" 3
typedef struct
  {



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





  } __fd_set;


typedef int __key_t;


typedef unsigned short int __ipc_pid_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_long __ino64_t;


typedef __loff_t __off64_t;


typedef int __t_scalar_t;
typedef unsigned int __t_uscalar_t;


typedef int __intptr_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
{
  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
{
  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 unsigned long int pthread_t;
# 151 "/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;






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


typedef __clock_t clock_t;







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


typedef __time_t time_t;
# 122 "/usr/include/sys/types.h" 2 3


# 1 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stddef.h" 1 3
# 125 "/usr/include/sys/types.h" 2 3



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



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

extern "C" {





struct timeval;

typedef __fd_mask fd_mask;


typedef __fd_set fd_set;
# 74 "/usr/include/sys/select.h" 3
extern int __select (int __nfds, __fd_set *__readfds, __fd_set *__writefds, __fd_set *__exceptfds, struct timeval *__timeout) throw ();


extern int select (int __nfds, __fd_set *__readfds, __fd_set *__writefds, __fd_set *__exceptfds, struct timeval *__timeout) throw ();
# 87 "/usr/include/sys/select.h" 3
extern int pselect (int __nfds, __fd_set *__readfds, __fd_set *__writefds, __fd_set *__exceptfds, const struct timespec *__timeout, const __sigset_t *__sigmask) throw ();





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


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





typedef __blkcnt_t blkcnt_t;
typedef __fsblkcnt_t fsblkcnt_t;
typedef __fsfilcnt_t fsfilcnt_t;







typedef __blkcnt64_t blkcnt64_t;
typedef __fsblkcnt64_t fsblkcnt64_t;
typedef __fsfilcnt64_t fsfilcnt64_t;


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






extern int32_t random (void) throw ();


extern void srandom (unsigned int __seed) throw ();





extern void * initstate (unsigned int __seed, void * __statebuf, size_t __statelen) throw ();




extern void * setstate (void * __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, void * __restrict __statebuf, size_t __statelen, struct random_data *__restrict __buf) throw ();




extern int setstate_r (void * __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 a[3];
    unsigned short int c;
    unsigned short int old_x[3];
    int init;
  };



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 ();
# 474 "/usr/include/stdlib.h" 3
extern void * malloc (size_t __size) throw ();

extern void * calloc (size_t __nmemb, size_t __size) throw ();





extern void * realloc (void * __ptr, size_t __size) throw ();

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/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stddef.h" 1 3
# 26 "/usr/include/alloca.h" 2 3

extern "C" {





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





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




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




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 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 (__const char *__string) throw ();





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



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






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






extern int mkstemp (char *__template) throw ();




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






extern char *canonicalize_file_name (__const char *__name) throw ();
# 595 "/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__));
# 651 "/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 ();
# 695 "/usr/include/stdlib.h" 3
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 ();
# 718 "/usr/include/stdlib.h" 3
extern int rpmatch (__const char *__response) throw ();
# 729 "/usr/include/stdlib.h" 3
extern int getsubopt (char **__restrict __optionp, __const char *__const *__restrict __tokens, char **__restrict __valuep) throw ();
# 738 "/usr/include/stdlib.h" 3
extern void setkey (__const char *__key) 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 ();





}
# 42 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdlib.h" 2 3
# 73 "/usr/local/packages/gcc-3.0/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/local/packages/gcc-3.0/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;
}
# 45 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstddef.h" 1 3
# 46 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/new" 1 3
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/new" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/cstddef" 1 3
# 35 "/usr/local/packages/gcc-3.0/include/g++-v3/new" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/exception" 1 3
# 34 "/usr/local/packages/gcc-3.0/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__));

  bool uncaught_exception() throw();
}

}
# 36 "/usr/local/packages/gcc-3.0/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);
}


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; }
}
# 47 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3

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

# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++config.h" 1 3
# 40 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_iosfwd.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stringfwd.h" 1 3
# 38 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stringfwd.h" 3

# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++config.h" 1 3
# 40 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stringfwd.h" 2 3

namespace std
{
  template<class _CharT>
    struct char_traits;

  template<> class char_traits<char>;




  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;



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

# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++io.h" 1 3
# 35 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++io.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/cstdio" 1 3
# 31 "/usr/local/packages/gcc-3.0/include/g++-v3/cstdio" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdio.h" 1 3
# 37 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdio.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++config.h" 1 3
# 38 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdio.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstddef.h" 1 3
# 39 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdio.h" 2 3
# 41 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdio.h" 3
# 1 "/usr/include/stdio.h" 1 3
# 27 "/usr/include/stdio.h" 3
# 1 "/usr/include/features.h" 1 3
# 28 "/usr/include/stdio.h" 2 3

extern "C" {



# 1 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stddef.h" 1 3
# 34 "/usr/include/stdio.h" 2 3




# 1 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stdarg.h" 1 3
# 43 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stdarg.h" 3
typedef __builtin_va_list __gnuc_va_list;
# 110 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stdarg.h" 3
typedef __gnuc_va_list va_list;
# 39 "/usr/include/stdio.h" 2 3

# 1 "/usr/include/bits/types.h" 1 3
# 41 "/usr/include/stdio.h" 2 3







typedef struct _IO_FILE FILE;
# 57 "/usr/include/stdio.h" 3
# 1 "/usr/include/libio.h" 1 3
# 30 "/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/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stddef.h" 1 3
# 312 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stddef.h" 3
typedef unsigned int wint_t;
# 15 "/usr/include/_G_config.h" 2 3
# 35 "/usr/include/_G_config.h" 3
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__)));
# 31 "/usr/include/libio.h" 2 3
# 48 "/usr/include/libio.h" 3
# 1 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stdarg.h" 1 3
# 49 "/usr/include/libio.h" 2 3
# 154 "/usr/include/libio.h" 3
struct _IO_jump_t; struct _IO_FILE;
# 164 "/usr/include/libio.h" 3
typedef void _IO_lock_t;





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



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

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;
# 233 "/usr/include/libio.h" 3
  __off64_t _offset;

  int _unused2[16];

};





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_;
# 260 "/usr/include/libio.h" 3
typedef struct
{
  __ssize_t (*read) (struct _IO_FILE *, void *, __ssize_t);
  __ssize_t (*write) (struct _IO_FILE *, const void *, __ssize_t);
  __off_t (*seek) (struct _IO_FILE *, __off_t, int);
  int (*close) (struct _IO_FILE *);
} _IO_cookie_io_functions_t;


struct _IO_cookie_file
{
  struct _IO_FILE file;
  const void *vtable;
  void *cookie;
  _IO_cookie_io_functions_t io_functions;
};




extern "C" {


extern int __underflow (_IO_FILE *) throw ();
extern int __uflow (_IO_FILE *) throw ();
extern int __overflow (_IO_FILE *, int) throw ();
# 302 "/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 ();
# 328 "/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 ();


}
# 58 "/usr/include/stdio.h" 2 3



typedef __off_t fpos_t;




typedef __off64_t fpos64_t;
# 110 "/usr/include/stdio.h" 3
# 1 "/usr/include/bits/stdio_lim.h" 1 3
# 111 "/usr/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 ();
# 136 "/usr/include/stdio.h" 3
extern FILE *tmpfile64 (void) throw ();


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




extern char *tmpnam_r (char *__s) throw ();
# 156 "/usr/include/stdio.h" 3
extern char *tempnam (__const char *__dir, __const char *__pfx) throw ();




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 ();
# 199 "/usr/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 *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 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 ();
# 409 "/usr/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 ();
# 489 "/usr/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 ();
# 523 "/usr/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 ();
# 610 "/usr/include/stdio.h" 3
extern void flockfile (FILE *__stream) throw ();



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


extern void funlockfile (FILE *__stream) throw ();
# 634 "/usr/include/stdio.h" 3
}
# 42 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdio.h" 2 3
# 86 "/usr/local/packages/gcc-3.0/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/local/packages/gcc-3.0/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/local/packages/gcc-3.0/include/g++-v3/cstdio" 2 3
# 36 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++io.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/cstddef" 1 3
# 37 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++io.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/gthr.h" 1 3
# 102 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/gthr.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/gthr-single.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/gthr-single.h" 3
typedef int __gthread_mutex_t;
# 211 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/gthr-single.h" 3
static inline int
__gthread_active_p (void)
{
  return 0;
}

static inline int
__gthread_mutex_lock (__gthread_mutex_t * )
{
  return 0;
}

static inline int
__gthread_mutex_trylock (__gthread_mutex_t * )
{
  return 0;
}

static inline int
__gthread_mutex_unlock (__gthread_mutex_t * )
{
  return 0;
}
# 103 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/gthr.h" 2 3
# 38 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++io.h" 2 3

namespace std
{

  typedef long streamoff;
  typedef ptrdiff_t streamsize;



  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/local/packages/gcc-3.0/include/g++-v3/bits/fpos.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cwchar.h" 1 3
# 37 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cwchar.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++config.h" 1 3
# 38 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cwchar.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstddef.h" 1 3
# 39 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cwchar.h" 2 3
# 42 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cwchar.h" 3
# 1 "/usr/include/wchar.h" 1 3
# 27 "/usr/include/wchar.h" 3
# 1 "/usr/include/features.h" 1 3
# 28 "/usr/include/wchar.h" 2 3



# 1 "/usr/include/stdio.h" 1 3
# 32 "/usr/include/wchar.h" 2 3






# 1 "/usr/local/packages/gcc-3.0/lib/gcc-lib/powerpc-unknown-linux-gnu/3.0/include/stddef.h" 1 3
# 39 "/usr/include/wchar.h" 2 3
# 53 "/usr/include/wchar.h" 3
typedef struct
{
  int count;
  wint_t value;
} mbstate_t;
# 77 "/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 ();

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




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
# 113 "/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 ();
# 136 "/usr/include/wchar.h" 3
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 ();



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

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



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



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

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


extern wchar_t *wcsstr (__const wchar_t *__haystack, __const wchar_t *__needle) throw ();
# 174 "/usr/include/wchar.h" 3
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 ();
extern size_t wcslen (__const wchar_t *__s) throw ();



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




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


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



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 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 ();
# 247 "/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 ();
# 277 "/usr/include/wchar.h" 3
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 ();
# 355 "/usr/include/wchar.h" 3
# 1 "/usr/include/xlocale.h" 1 3
# 356 "/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 __nptr, 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 ();
# 482 "/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 ();
# 502 "/usr/include/wchar.h" 3
}
# 43 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cwchar.h" 2 3
# 57 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cwchar.h" 3
namespace std
{
  using ::mbstate_t;
}
# 41 "/usr/local/packages/gcc-3.0/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;



}
# 42 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_iosfwd.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/functexcept.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/functexcept.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/exception_defines.h" 1 3
# 35 "/usr/local/packages/gcc-3.0/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/local/packages/gcc-3.0/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;
# 129 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_iosfwd.h" 3
}
# 49 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_iterator_base_types.h" 1 3
# 40 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_iterator_base_types.h" 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;
};
# 140 "/usr/local/packages/gcc-3.0/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); }

}
# 50 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_iterator_base_funcs.h" 1 3
# 40 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_iterator_base_funcs.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/concept_check.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/concept_check.h" 3

# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/c++config.h" 1 3
# 36 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/concept_check.h" 2 3
# 41 "/usr/local/packages/gcc-3.0/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));
}

}
# 51 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_iterator.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/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);
}
# 193 "/usr/local/packages/gcc-3.0/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;
};
# 417 "/usr/local/packages/gcc-3.0/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+(__normal_iterator<_Iterator, _Container>::difference_type __n,
          const __normal_iterator<_Iterator, _Container>& __i)
{ return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }

}
# 52 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_algobase.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/concept_check.h" 1 3
# 53 "/usr/local/packages/gcc-3.0/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;
}
# 137 "/usr/local/packages/gcc-3.0/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 unsigned char*) __first1,
                                 (const unsigned char*) __last1,
                                 (const unsigned char*) __first2,
                                 (const unsigned 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 unsigned char*) __first1,
                                        (const unsigned char*) __last1,
                                        (const unsigned char*) __first2,
                                        (const unsigned 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);
}

}
# 33 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_list.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_alloc.h" 1 3
# 28 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_alloc.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/functexcept.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/functexcept.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/exception_defines.h" 1 3
# 35 "/usr/local/packages/gcc-3.0/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);
}
# 29 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_alloc.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstddef.h" 1 3
# 30 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_alloc.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstdlib.h" 1 3
# 31 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_alloc.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstring.h" 1 3
# 32 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_alloc.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cassert.h" 1 3
# 37 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cassert.h" 3
# 1 "/usr/include/assert.h" 1 3
# 35 "/usr/include/assert.h" 3
# 1 "/usr/include/features.h" 1 3
# 36 "/usr/include/assert.h" 2 3
# 58 "/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__));

}
# 38 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cassert.h" 2 3
# 33 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_alloc.h" 2 3





# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_threads.h" 1 3
# 33 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_threads.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/powerpc-unknown-linux-gnu/bits/gthr.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_threads.h" 2 3
# 51 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_threads.h" 3
namespace std
{
# 66 "/usr/local/packages/gcc-3.0/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;
      _M_ref_count_lock = __tmp;





    }
# 112 "/usr/local/packages/gcc-3.0/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;
  }
# 163 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_threads.h" 3
};
# 284 "/usr/local/packages/gcc-3.0/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;
# 311 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_threads.h" 3
struct _STL_mutex_lock
{







  __gthread_mutex_t _M_lock;
  void _M_initialize() {
# 342 "/usr/local/packages/gcc-3.0/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);
  }
# 453 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_threads.h" 3
};
# 492 "/usr/local/packages/gcc-3.0/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&);
};

}
# 39 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_alloc.h" 2 3
# 68 "/usr/local/packages/gcc-3.0/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;
    ((void) ((*(size_t*)__real_p == __n) ? 0 : (__assert_fail ("*(size_t*)__real_p == __n", "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_alloc.h", 190, __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;
    ((void) ((*(size_t*)__real_p == __old_sz) ? 0 : (__assert_fail ("*(size_t*)__real_p == __old_sz", "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_alloc.h", 197, __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;
  }

};
# 241 "/usr/local/packages/gcc-3.0/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 };



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, };
# 526 "/usr/local/packages/gcc-3.0/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;
}
# 602 "/usr/local/packages/gcc-3.0/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;
}
# 732 "/usr/local/packages/gcc-3.0/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;
};

}
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_list.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_construct.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_construct.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/new" 1 3
# 35 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_construct.h" 2 3

namespace std
{
# 47 "/usr/local/packages/gcc-3.0/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);
}

}
# 35 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_list.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_uninitialized.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_uninitialized.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_cstring.h" 1 3
# 35 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_uninitialized.h" 2 3

namespace std
{





template <class _InputIter, class _ForwardIter>
inline _ForwardIter
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
                         _ForwardIter __result,
                         __true_type)
{
  return copy(__first, __last, __result);
}

template <class _InputIter, class _ForwardIter>
_ForwardIter
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
                         _ForwardIter __result,
                         __false_type)
{
  _ForwardIter __cur = __result;
  try {
    for ( ; __first != __last; ++__first, ++__cur)
      _Construct(&*__cur, *__first);
    return __cur;
  }
  catch(...) { _Destroy(__result, __cur); throw; };
}


template <class _InputIter, class _ForwardIter, class _Tp>
inline _ForwardIter
__uninitialized_copy(_InputIter __first, _InputIter __last,
                     _ForwardIter __result, _Tp*)
{
  typedef typename __type_traits<_Tp>::is_POD_type _Is_POD;
  return __uninitialized_copy_aux(__first, __last, __result, _Is_POD());
}

template <class _InputIter, class _ForwardIter>
inline _ForwardIter
  uninitialized_copy(_InputIter __first, _InputIter __last,
                     _ForwardIter __result)
{
  return __uninitialized_copy(__first, __last, __result,
                              __value_type(__result));
}

inline char* uninitialized_copy(const char* __first, const char* __last,
                                char* __result) {
  memmove(__result, __first, __last - __first);
  return __result + (__last - __first);
}

inline wchar_t*
uninitialized_copy(const wchar_t* __first, const wchar_t* __last,
                   wchar_t* __result)
{
  memmove(__result, __first, sizeof(wchar_t) * (__last - __first));
  return __result + (__last - __first);
}



template <class _InputIter, class _Size, class _ForwardIter>
pair<_InputIter, _ForwardIter>
__uninitialized_copy_n(_InputIter __first, _Size __count,
                       _ForwardIter __result,
                       input_iterator_tag)
{
  _ForwardIter __cur = __result;
  try {
    for ( ; __count > 0 ; --__count, ++__first, ++__cur)
      _Construct(&*__cur, *__first);
    return pair<_InputIter, _ForwardIter>(__first, __cur);
  }
  catch(...) { _Destroy(__result, __cur); throw; };
}

template <class _RandomAccessIter, class _Size, class _ForwardIter>
inline pair<_RandomAccessIter, _ForwardIter>
__uninitialized_copy_n(_RandomAccessIter __first, _Size __count,
                       _ForwardIter __result,
                       random_access_iterator_tag) {
  _RandomAccessIter __last = __first + __count;
  return pair<_RandomAccessIter, _ForwardIter>(
                 __last,
                 uninitialized_copy(__first, __last, __result));
}

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

template <class _InputIter, class _Size, class _ForwardIter>
inline pair<_InputIter, _ForwardIter>
uninitialized_copy_n(_InputIter __first, _Size __count,
                     _ForwardIter __result) {
  return __uninitialized_copy_n(__first, __count, __result,
                                __iterator_category(__first));
}



template <class _ForwardIter, class _Tp>
inline void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last,
                         const _Tp& __x, __true_type)
{
  fill(__first, __last, __x);
}

template <class _ForwardIter, class _Tp>
void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last,
                         const _Tp& __x, __false_type)
{
  _ForwardIter __cur = __first;
  try {
    for ( ; __cur != __last; ++__cur)
      _Construct(&*__cur, __x);
  }
  catch(...) { _Destroy(__first, __cur); throw; };
}

template <class _ForwardIter, class _Tp, class _Tp1>
inline void __uninitialized_fill(_ForwardIter __first,
                                 _ForwardIter __last, const _Tp& __x, _Tp1*)
{
  typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
  __uninitialized_fill_aux(__first, __last, __x, _Is_POD());

}

template <class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first,
                               _ForwardIter __last,
                               const _Tp& __x)
{
  __uninitialized_fill(__first, __last, __x, __value_type(__first));
}



template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n,
                           const _Tp& __x, __true_type)
{
  return fill_n(__first, __n, __x);
}

template <class _ForwardIter, class _Size, class _Tp>
_ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n,
                           const _Tp& __x, __false_type)
{
  _ForwardIter __cur = __first;
  try {
    for ( ; __n > 0; --__n, ++__cur)
      _Construct(&*__cur, __x);
    return __cur;
  }
  catch(...) { _Destroy(__first, __cur); throw; };
}

template <class _ForwardIter, class _Size, class _Tp, class _Tp1>
inline _ForwardIter
__uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x, _Tp1*)
{
  typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
  return __uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
}

template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
{
  return __uninitialized_fill_n(__first, __n, __x, __value_type(__first));
}
# 231 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_uninitialized.h" 3
template <class _InputIter1, class _InputIter2, class _ForwardIter>
inline _ForwardIter
__uninitialized_copy_copy(_InputIter1 __first1, _InputIter1 __last1,
                          _InputIter2 __first2, _InputIter2 __last2,
                          _ForwardIter __result)
{
  _ForwardIter __mid = uninitialized_copy(__first1, __last1, __result);
  try {
    return uninitialized_copy(__first2, __last2, __mid);
  }
  catch(...) { _Destroy(__result, __mid); throw; };
}




template <class _ForwardIter, class _Tp, class _InputIter>
inline _ForwardIter
__uninitialized_fill_copy(_ForwardIter __result, _ForwardIter __mid,
                          const _Tp& __x,
                          _InputIter __first, _InputIter __last)
{
  uninitialized_fill(__result, __mid, __x);
  try {
    return uninitialized_copy(__first, __last, __mid);
  }
  catch(...) { _Destroy(__result, __mid); throw; };
}




template <class _InputIter, class _ForwardIter, class _Tp>
inline void
__uninitialized_copy_fill(_InputIter __first1, _InputIter __last1,
                          _ForwardIter __first2, _ForwardIter __last2,
                          const _Tp& __x)
{
  _ForwardIter __mid2 = uninitialized_copy(__first1, __last1, __first2);
  try {
    uninitialized_fill(__mid2, __last2, __x);
  }
  catch(...) { _Destroy(__first2, __mid2); throw; };
}

}
# 36 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_list.h" 2 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_list.h" 1 3
# 34 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_list.h" 3
# 1 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/concept_check.h" 1 3
# 35 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_list.h" 2 3

namespace std
{

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};

template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data;
};

struct _List_iterator_base {
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef bidirectional_iterator_tag iterator_category;

  _List_node_base* _M_node;

  _List_iterator_base(_List_node_base* __x) : _M_node(__x) {}
  _List_iterator_base() {}

  void _M_incr() { _M_node = _M_node->_M_next; }
  void _M_decr() { _M_node = _M_node->_M_prev; }

  bool operator==(const _List_iterator_base& __x) const {
    return _M_node == __x._M_node;
  }
  bool operator!=(const _List_iterator_base& __x) const {
    return _M_node != __x._M_node;
  }
};

template<class _Tp, class _Ref, class _Ptr>
struct _List_iterator : public _List_iterator_base {
  typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
  typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
  typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;

  typedef _Tp value_type;
  typedef _Ptr pointer;
  typedef _Ref reference;
  typedef _List_node<_Tp> _Node;

  _List_iterator(_Node* __x) : _List_iterator_base(__x) {}
  _List_iterator() {}
  _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {}

  reference operator*() const { return ((_Node*) _M_node)->_M_data; }
  pointer operator->() const { return &(operator*()); }

  _Self& operator++() {
    this->_M_incr();
    return *this;
  }
  _Self operator++(int) {
    _Self __tmp = *this;
    this->_M_incr();
    return __tmp;
  }
  _Self& operator--() {
    this->_M_decr();
    return *this;
  }
  _Self operator--(int) {
    _Self __tmp = *this;
    this->_M_decr();
    return __tmp;
  }
};
# 118 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/stl_list.h" 3
template <class _Tp, class _Allocator, bool _IsStatic>
class _List_alloc_base {
public:
  typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
          allocator_type;
  allocator_type get_allocator() const { return _Node_allocator; }

  _List_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}

protected:
  _List_node<_Tp>* _M_get_node()
   { return _Node_allocator.allocate(1); }
  void _M_put_node(_List_node<_Tp>* __p)
    { _Node_allocator.deallocate(__p, 1); }

protected:
  typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
           _Node_allocator;
  _List_node<_Tp>* _M_node;
};



template <class _Tp, class _Allocator>
class _List_alloc_base<_Tp, _Allocator, true> {
public:
  typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
          allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }

  _List_alloc_base(const allocator_type&) {}

protected:
  typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
          _Alloc_type;
  _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); }
  void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); }

protected:
  _List_node<_Tp>* _M_node;
};

template <class _Tp, class _Alloc>
class _List_base
  : public _List_alloc_base<_Tp, _Alloc,
                            _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
public:
  typedef _List_alloc_base<_Tp, _Alloc,
                           _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
          _Base;
  typedef typename _Base::allocator_type allocator_type;

  _List_base(const allocator_type& __a) : _Base(__a) {
    _M_node = _M_get_node();
    _M_node->_M_next = _M_node;
    _M_node->_M_prev = _M_node;
  }
  ~_List_base() {
    clear();
    _M_put_node(_M_node);
  }

  void clear();
};


template <class _Tp, class _Alloc>
void
_List_base<_Tp,_Alloc>::clear()
{
  _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next;
  while (__cur != _M_node) {
    _List_node<_Tp>* __tmp = __cur;
    __cur = (_List_node<_Tp>*) __cur->_M_next;
    _Destroy(&__tmp->_M_data);
    _M_put_node(__tmp);
  }
  _M_node->_M_next = _M_node;
  _M_node->_M_prev = _M_node;
}

template <class _Tp, class _Alloc = allocator<_Tp> >
class list : protected _List_base<_Tp, _Alloc>
{

                                                      ;

  typedef _List_base<_Tp, _Alloc> _Base;
protected:
  typedef void* _Void_pointer;

public:
  typedef _Tp value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef _List_node<_Tp> _Node;
  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(); }

public:
  typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
  typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;

  typedef reverse_iterator<const_iterator> const_reverse_iterator;
  typedef reverse_iterator<iterator> reverse_iterator;

protected:
  using _Base::_M_node;
  using _Base::_M_put_node;
  using _Base::_M_get_node;

protected:
  _Node* _M_create_node(const _Tp& __x)
  {
    _Node* __p = _M_get_node();
    try {
      _Construct(&__p->_M_data, __x);
    }
    catch(...) { _M_put_node(__p); throw; };
    return __p;
  }

  _Node* _M_create_node()
  {
    _Node* __p = _M_get_node();
    try {
      _Construct(&__p->_M_data);
    }
    catch(...) { _M_put_node(__p); throw; };
    return __p;
  }

public:
  explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}

  iterator begin() { return (_Node*)(_M_node->_M_next); }
  const_iterator begin() const { return (_Node*)(_M_node->_M_next); }

  iterator end() { return _M_node; }
  const_iterator end() const { return _M_node; }

  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->_M_next == _M_node; }
  size_type size() const {
    size_type __result = 0;
    distance(begin(), end(), __result);
    return __result;
  }
  size_type max_size() const { return size_type(-1); }

  reference front() { return *begin(); }
  const_reference front() const { return *begin(); }
  reference back() { return *(--end()); }
  const_reference back() const { return *(--end()); }

  void swap(list<_Tp, _Alloc>& __x) { std::swap(_M_node, __x._M_node); }

  iterator insert(iterator __position, const _Tp& __x) {
    _Node* __tmp = _M_create_node(__x);
    __tmp->_M_next = __position._M_node;
    __tmp->_M_prev = __position._M_node->_M_prev;
    __position._M_node->_M_prev->_M_next = __tmp;
    __position._M_node->_M_prev = __tmp;
    return __tmp;
  }
  iterator insert(iterator __position) { return insert(__position, _Tp()); }


  template<class _Integer>
  void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
                          __true_type) {
    _M_fill_insert(__pos, (size_type) __n, (_Tp) __x);
  }

  template <class _InputIterator>
  void _M_insert_dispatch(iterator __pos,
                          _InputIterator __first, _InputIterator __last,
                          __false_type);

  template <class _InputIterator>
  void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    _M_insert_dispatch(__pos, __first, __last, _Integral());
  }

  void insert(iterator __pos, size_type __n, const _Tp& __x)
    { _M_fill_insert(__pos, __n, __x); }
  void _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x);

  void push_front(const _Tp& __x) { insert(begin(), __x); }
  void push_front() {insert(begin());}
  void push_back(const _Tp& __x) { insert(end(), __x); }
  void push_back() {insert(end());}

  iterator erase(iterator __position) {
    _List_node_base* __next_node = __position._M_node->_M_next;
    _List_node_base* __prev_node = __position._M_node->_M_prev;
    _Node* __n = (_Node*) __position._M_node;
    __prev_node->_M_next = __next_node;
    __next_node->_M_prev = __prev_node;
    _Destroy(&__n->_M_data);
    _M_put_node(__n);
    return iterator((_Node*) __next_node);
  }
  iterator erase(iterator __first, iterator __last);
  void clear() { _Base::clear(); }

  void resize(size_type __new_size, const _Tp& __x);
  void resize(size_type __new_size) { this->resize(__new_size, _Tp()); }

  void pop_front() { erase(begin()); }
  void pop_back() {
    iterator __tmp = end();
    erase(--__tmp);
  }
  list(size_type __n, const _Tp& __value,
       const allocator_type& __a = allocator_type())
    : _Base(__a)
    { insert(begin(), __n, __value); }
  explicit list(size_type __n)
    : _Base(allocator_type())
    { insert(begin(), __n, _Tp()); }



  template <class _InputIterator>
  list(_InputIterator __first, _InputIterator __last,
       const allocator_type& __a = allocator_type())
    : _Base(__a)
    { insert(begin(), __first, __last); }

  list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator())
    { insert(begin(), __x.begin(), __x.end()); }

  ~list() { }

  list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x);

public:





  void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }

  void _M_fill_assign(size_type __n, const _Tp& __val);

  template <class _InputIterator>
  void assign(_InputIterator __first, _InputIterator __last) {
    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    _M_assign_dispatch(__first, __last, _Integral());
  }

  template <class _Integer>
  void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
    { _M_fill_assign((size_type) __n, (_Tp) __val); }

  template <class _InputIterator>
  void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
                          __false_type);

protected:
  void transfer(iterator __position, iterator __first, iterator __last) {
    if (__position != __last) {

      __last._M_node->_M_prev->_M_next = __position._M_node;
      __first._M_node->_M_prev->_M_next = __last._M_node;
      __position._M_node->_M_prev->_M_next = __first._M_node;


      _List_node_base* __tmp = __position._M_node->_M_prev;
      __position._M_node->_M_prev = __last._M_node->_M_prev;
      __last._M_node->_M_prev = __first._M_node->_M_prev;
      __first._M_node->_M_prev = __tmp;
    }
  }

public:
  void splice(iterator __position, list& __x) {
    if (!__x.empty())
      this->transfer(__position, __x.begin(), __x.end());
  }
  void splice(iterator __position, list&, iterator __i) {
    iterator __j = __i;
    ++__j;
    if (__position == __i || __position == __j) return;
    this->transfer(__position, __i, __j);
  }
  void splice(iterator __position, list&, iterator __first, iterator __last) {
    if (__first != __last)
      this->transfer(__position, __first, __last);
  }
  void remove(const _Tp& __value);
  void unique();
  void merge(list& __x);
  void reverse();
  void sort();

  template <class _Predicate> void remove_if(_Predicate);
  template <class _BinaryPredicate> void unique(_BinaryPredicate);
  template <class _StrictWeakOrdering> void merge(list&, _StrictWeakOrdering);
  template <class _StrictWeakOrdering> void sort(_StrictWeakOrdering);
};

template <class _Tp, class _Alloc>
inline bool
operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
{
  typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
  const_iterator __end1 = __x.end();
  const_iterator __end2 = __y.end();

  const_iterator __i1 = __x.begin();
  const_iterator __i2 = __y.begin();
  while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
    ++__i1;
    ++__i2;
  }
  return __i1 == __end1 && __i2 == __end2;
}

template <class _Tp, class _Alloc>
inline bool operator<(const list<_Tp,_Alloc>& __x,
                      const list<_Tp,_Alloc>& __y)
{
  return lexicographical_compare(__x.begin(), __x.end(),
                                 __y.begin(), __y.end());
}

template <class _Tp, class _Alloc>
inline bool operator!=(const list<_Tp,_Alloc>& __x,
                       const list<_Tp,_Alloc>& __y) {
  return !(__x == __y);
}

template <class _Tp, class _Alloc>
inline bool operator>(const list<_Tp,_Alloc>& __x,
                      const list<_Tp,_Alloc>& __y) {
  return __y < __x;
}

template <class _Tp, class _Alloc>
inline bool operator<=(const list<_Tp,_Alloc>& __x,
                       const list<_Tp,_Alloc>& __y) {
  return !(__y < __x);
}

template <class _Tp, class _Alloc>
inline bool operator>=(const list<_Tp,_Alloc>& __x,
                       const list<_Tp,_Alloc>& __y) {
  return !(__x < __y);
}

template <class _Tp, class _Alloc>
inline void
swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
{
  __x.swap(__y);
}

template <class _Tp, class _Alloc> template <class _InputIter>
void
list<_Tp, _Alloc>::_M_insert_dispatch(iterator __position,
                                      _InputIter __first, _InputIter __last,
                                      __false_type)
{
  for ( ; __first != __last; ++__first)
    insert(__position, *__first);
}

template <class _Tp, class _Alloc>
void
list<_Tp, _Alloc>::_M_fill_insert(iterator __position,
                                  size_type __n, const _Tp& __x)
{
  for ( ; __n > 0; --__n)
    insert(__position, __x);
}

template <class _Tp, class _Alloc>
typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first,
                                                             iterator __last)
{
  while (__first != __last)
    erase(__first++);
  return __last;
}

template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x)
{
  iterator __i = begin();
  size_type __len = 0;
  for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
    ;
  if (__len == __new_size)
    erase(__i, end());
  else
    insert(end(), __new_size - __len, __x);
}

template <class _Tp, class _Alloc>
list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x)
{
  if (this != &__x) {
    iterator __first1 = begin();
    iterator __last1 = end();
    const_iterator __first2 = __x.begin();
    const_iterator __last2 = __x.end();
    while (__first1 != __last1 && __first2 != __last2)
      *__first1++ = *__first2++;
    if (__first2 == __last2)
      erase(__first1, __last1);
    else
      insert(__last1, __first2, __last2);
  }
  return *this;
}

template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
  iterator __i = begin();
  for ( ; __i != end() && __n > 0; ++__i, --__n)
    *__i = __val;
  if (__n > 0)
    insert(end(), __n, __val);
  else
    erase(__i, end());
}

template <class _Tp, class _Alloc> template <class _InputIter>
void
list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2,
                                      __false_type)
{
  iterator __first1 = begin();
  iterator __last1 = end();
  for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
    *__first1 = *__first2;
  if (__first2 == __last2)
    erase(__first1, __last1);
  else
    insert(__last1, __first2, __last2);
}

template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::remove(const _Tp& __value)
{
  iterator __first = begin();
  iterator __last = end();
  while (__first != __last) {
    iterator __next = __first;
    ++__next;
    if (*__first == __value) erase(__first);
    __first = __next;
  }
}

template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::unique()
{
  iterator __first = begin();
  iterator __last = end();
  if (__first == __last) return;
  iterator __next = __first;
  while (++__next != __last) {
    if (*__first == *__next)
      erase(__next);
    else
      __first = __next;
    __next = __first;
  }
}

template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x)
{
  iterator __first1 = begin();
  iterator __last1 = end();
  iterator __first2 = __x.begin();
  iterator __last2 = __x.end();
  while (__first1 != __last1 && __first2 != __last2)
    if (*__first2 < *__first1) {
      iterator __next = __first2;
      transfer(__first1, __first2, ++__next);
      __first2 = __next;
    }
    else
      ++__first1;
  if (__first2 != __last2) transfer(__last1, __first2, __last2);
}

inline void __List_base_reverse(_List_node_base* __p)
{
  _List_node_base* __tmp = __p;
  do {
    std::swap(__tmp->_M_next, __tmp->_M_prev);
    __tmp = __tmp->_M_prev;
  } while (__tmp != __p);
}

template <class _Tp, class _Alloc>
inline void list<_Tp, _Alloc>::reverse()
{
  __List_base_reverse(this->_M_node);
}

template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::sort()
{

  if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
    list<_Tp, _Alloc> __carry;
    list<_Tp, _Alloc> __counter[64];
    int __fill = 0;
    while (!empty()) {
      __carry.splice(__carry.begin(), *this, begin());
      int __i = 0;
      while(__i < __fill && !__counter[__i].empty()) {
        __counter[__i].merge(__carry);
        __carry.swap(__counter[__i++]);
      }
      __carry.swap(__counter[__i]);
      if (__i == __fill) ++__fill;
    }

    for (int __i = 1; __i < __fill; ++__i)
      __counter[__i].merge(__counter[__i-1]);
    swap(__counter[__fill-1]);
  }
}

template <class _Tp, class _Alloc> template <class _Predicate>
void list<_Tp, _Alloc>::remove_if(_Predicate __pred)
{
  iterator __first = begin();
  iterator __last = end();
  while (__first != __last) {
    iterator __next = __first;
    ++__next;
    if (__pred(*__first)) erase(__first);
    __first = __next;
  }
}

template <class _Tp, class _Alloc> template <class _BinaryPredicate>
void list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred)
{
  iterator __first = begin();
  iterator __last = end();
  if (__first == __last) return;
  iterator __next = __first;
  while (++__next != __last) {
    if (__binary_pred(*__first, *__next))
      erase(__next);
    else
      __first = __next;
    __next = __first;
  }
}

template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x,
                              _StrictWeakOrdering __comp)
{
  iterator __first1 = begin();
  iterator __last1 = end();
  iterator __first2 = __x.begin();
  iterator __last2 = __x.end();
  while (__first1 != __last1 && __first2 != __last2)
    if (__comp(*__first2, *__first1)) {
      iterator __next = __first2;
      transfer(__first1, __first2, ++__next);
      __first2 = __next;
    }
    else
      ++__first1;
  if (__first2 != __last2) transfer(__last1, __first2, __last2);
}

template <class _Tp, class _Alloc> template <class _StrictWeakOrdering>
void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
{

  if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
    list<_Tp, _Alloc> __carry;
    list<_Tp, _Alloc> __counter[64];
    int __fill = 0;
    while (!empty()) {
      __carry.splice(__carry.begin(), *this, begin());
      int __i = 0;
      while(__i < __fill && !__counter[__i].empty()) {
        __counter[__i].merge(__carry, __comp);
        __carry.swap(__counter[__i++]);
      }
      __carry.swap(__counter[__i]);
      if (__i == __fill) ++__fill;
    }

    for (int __i = 1; __i < __fill; ++__i)
      __counter[__i].merge(__counter[__i-1], __comp);
    swap(__counter[__fill-1]);
  }
}

}
# 37 "/usr/local/packages/gcc-3.0/include/g++-v3/bits/std_list.h" 2 3
# 32 "/usr/local/packages/gcc-3.0/include/g++-v3/list" 2 3
# 19 "bug.c" 2

struct B {
        typedef std::list< int > L;

        struct iterator : L::iterator { };
        struct const_iterator : L::const_iterator { };
};

template< class T >
struct D : B {
        struct iterator : B::iterator { };
        struct const_iterator : B::const_iterator { };
        typedef int const_iterator;
};

>Fix:
>Release-Note:
>Audit-Trail:
>Unformatted:
 >System: Linux powerbook 2.2.17 #2 Wed Nov 22 16:34:45 PST 2000 ppc unknown
 >Architecture: ppc
 host: powerpc-unknown-linux-gnu
 build: powerpc-unknown-linux-gnu
 target: powerpc-unknown-linux-gnu
 configured with: ./configure --prefix=/usr/local/packages/gcc-3.0 --enable-languages=c++


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