// deque standard header
#ifndef _DEQUE_
#define _DEQUE_

#pragma info(none)
#ifndef __CHKHDR__
#  pragma report(level, E)
#endif
#pragma info(restore)

#if __IBMCPP__ < 400
#error This file to be used only with IBM VisualAge C++ v4 and later compilers.
#endif /* __IBMCPP__ */

#pragma namemangling(ansi)

   /********************************************************************/
   /*  <deque> header file                                             */
   /*                                                                  */
   /*  IBM VisualAge C++ Professional, Version 4.0                     */
   /*    Licensed Materials - Property of IBM                          */
   /*                                                                  */
   /*  5801-AAR and Other Materials                                    */
   /*                                                                  */
   /*  (c) Copyright IBM Corp 1991, 2000. All rights reserved.         */
   /*                                                                  */
   /*                                                                  */
   /*  US Government Users Restricted Rights - Use, duplication        */
   /*  or disclosure restricted by GSA ADP Schedule Contract with      */
   /*  IBM Corp.                                                       */
   /*                                                                  */
   /*  Dinkum C++ Library                                              */
   /*  Copyright (c) 1998.  Licensed to IBM Corp. and its suppliers.   */
   /*                                                                  */
   /********************************************************************/

#include <memory>
#include <stdexcept>
_STD_BEGIN
#define _DEQUEMAPSIZ    8       /* at least 5 */
#define _DEQUESIZ (4096 < sizeof (_Ty) ? \
        1 : 4096 / sizeof (_Ty))

                // TEMPLATE CLASS _Deque_map
template<class _Ty, class _A>
        class _Deque_map {
protected:
        _Deque_map(_A _Al)
                : _Almap(_Al) {}
        typedef typename _A::template
                rebind<_Ty>::other::pointer _Tptr;
        typename _A::template rebind<_Tptr>::other _Almap;
        };

                // TEMPLATE CLASS _Deque_val
template<class _Ty, class _A>
        class _Deque_val : public _Deque_map<_Ty, _A> {
protected:
        _Deque_val(_A _Al = _A())
                : _Deque_map<_Ty, _A>(_Al), _Alval(_Al) {}
        typedef typename _A::template
                rebind<_Ty>::other _Alty;
        _Alty _Alval;
        };

                // TEMPLATE CLASS deque
template<class _Ty, class _Ax _TDEF(allocator<_Ty>) >
        class deque
                : public _Deque_val<_Ty, _Ax> {
public:
        typedef deque<_Ty, _Ax> _Myt;
        typedef _Deque_val<_Ty, _Ax> _Mybase;
        typedef typename _Mybase::_Alty _A;
        typedef _A allocator_type;
        typedef typename _A::size_type size_type;
        typedef typename _A::difference_type _Dift;
        typedef _Dift difference_type;
        typedef typename _A::pointer _Tptr;
        typedef typename _A::const_pointer _Ctptr;
        typedef _Tptr pointer;
        typedef _Ctptr const_pointer;
        typedef _POINTER_X(_Tptr, _A) _Mapptr;
        typedef typename _A::reference _Reft;
        typedef _Tptr pointer;
        typedef _Ctptr const_pointer;
        typedef _Reft reference;
        typedef typename _A::const_reference const_reference;
        typedef typename _A::value_type value_type;
                // CLASS iterator
        class const_iterator;
        class iterator : public _Ranit<_Ty, _Dift, _Tptr, _Reft> {
        public:
                typedef _Ranit<_Ty, _Dift, _Tptr, _Reft> _Mybase;
                typedef typename _Mybase::iterator_category
                        iterator_category;
                typedef typename _Mybase::value_type value_type;
                typedef typename _Mybase::difference_type
                        difference_type;
                typedef typename _Mybase::pointer pointer;
                typedef typename _Mybase::reference reference;
                friend class deque<_Ty, _A>;
                friend class const_iterator;
                iterator()
                        : _First(0), _Last(0), _Next(0), _Map(0) {}
                iterator(_Tptr _P, _Mapptr _M)
                        : _First(*_M), _Last(*_M + _DEQUESIZ),
                                _Next(_P), _Map(_M) {}
                reference operator*() const
                        {return (*_Next); }
                _Tptr operator->() const
                        {return (&**this); }
                iterator& operator++()
                        {if (_Next != _Last && ++_Next == _Last
                                && _Map[1] != 0)
                                {_First = *++_Map;
                                _Last = _First + _DEQUESIZ;
                                _Next = _First; }
                        return (*this); }
                iterator operator++(int)
                        {iterator _Tmp = *this;
                        ++*this;
                        return (_Tmp); }
                iterator& operator--()
                        {if (_Next != _First)
                                --_Next;
                        else if (_Map[-1] != 0)
                                {_First = *--_Map;
                                _Last = _First + _DEQUESIZ;
                                _Next = _Last - 1; }
                        return (*this); }
                iterator operator--(int)
                        {iterator _Tmp = *this;
                        --*this;
                        return (_Tmp); }
                iterator& operator+=(difference_type _N)
                        {_Add(_N);
                        return (*this); }
                iterator& operator-=(difference_type _N)
                        {return (*this += -_N); }
                iterator operator+(difference_type _N) const
                        {iterator _Tmp = *this;
                        return (_Tmp += _N); }
                iterator operator-(difference_type _N) const
                        {iterator _Tmp = *this;
                        return (_Tmp -= _N); }
                difference_type operator-(const iterator& _X) const
                        {return (_Map == _X._Map ? _Next - _X._Next
                                : _DEQUESIZ * (_Map - _X._Map - 1)
                                + (_Next - _First) + (_X._Last - _X._Next)); }
                reference operator[](difference_type _N) const
                        {return (*(*this + _N)); }
                bool operator==(const iterator& _X) const
                        {return (_Next == _X._Next); }
                bool operator!=(const iterator& _X) const
                        {return (!(*this == _X)); }
                bool operator<(const iterator& _X) const
                        {return (_Map < _X._Map
                                || _Map == _X._Map && _Next < _X._Next); }
                bool operator<=(const iterator& _X) const
                        {return (!(_X < *this)); }
                bool operator>(const iterator& _X) const
                        {return (_X < *this); }
                bool operator>=(const iterator& _X) const
                        {return (!(*this < _X)); }
        protected:
                void _Add(difference_type _N);
        _PROTECTED:
                _Tptr _First, _Last, _Next;
                _Mapptr _Map;
                };
                // CLASS const_iterator
        class const_iterator
                : public _Ranit<_Ty, _Dift, _Ctptr, const_reference> {
        public:
                typedef _Ranit<_Ty, _Dift, _Ctptr, const_reference>
                        _Mybase;
                typedef typename _Mybase::iterator_category
                        iterator_category;
                typedef typename _Mybase::value_type value_type;
                typedef typename _Mybase::difference_type
                        difference_type;
                typedef typename _Mybase::pointer pointer;
                typedef typename _Mybase::reference reference;
                friend class deque<_Ty, _A>;
                const_iterator()
                        : _First(0), _Last(0), _Next(0), _Map(0) {}
                const_iterator(_Tptr _P, _Mapptr _M)
                        : _First(*_M), _Last(*_M + _DEQUESIZ),
                                _Next(_P), _Map(_M) {}
                const_iterator(const iterator& _X)
                        : _First(_X._First), _Last(_X._Last),
                                _Next(_X._Next), _Map(_X._Map) {}
                const_reference operator*() const
                        {return (*_Next); }
                _Ctptr operator->() const
                        {return (&**this); }
                const_iterator& operator++()
                        {if (_Next != _Last && ++_Next == _Last
                                && _Map[1] != 0)
                                {_First = *++_Map;
                                _Last = _First + _DEQUESIZ;
                                _Next = _First; }
                        return (*this); }
                const_iterator operator++(int)
                        {const_iterator _Tmp = *this;
                        ++*this;
                        return (_Tmp); }
                const_iterator& operator--()
                        {if (_Next != _First)
                                --_Next;
                        else if (_Map[-1] != 0)
                                {_First = *--_Map;
                                _Last = _First + _DEQUESIZ;
                                _Next = _Last - 1; }
                        return (*this); }
                const_iterator operator--(int)
                        {const_iterator _Tmp = *this;
                        --*this;
                        return (_Tmp); }
                const_iterator& operator+=(difference_type _N)
                        {_Add(_N);
                        return (*this); }
                const_iterator& operator-=(difference_type _N)
                        {return (*this += -_N); }
                const_iterator operator+(difference_type _N) const
                        {const_iterator _Tmp = *this;
                        return (_Tmp += _N); }
                const_iterator operator-(difference_type _N) const
                        {const_iterator _Tmp = *this;
                        return (_Tmp -= _N); }
                difference_type operator-(
                        const const_iterator& _X) const
                        {return (_Map == _X._Map ? _Next - _X._Next
                                : _DEQUESIZ * (_Map - _X._Map - 1)
                                + (_Next - _First) + (_X._Last - _X._Next)); }
                const_reference operator[](difference_type _N) const
                        {return (*(*this + _N)); }
                bool operator==(const const_iterator& _X) const
                        {return (_Next == _X._Next); }
                bool operator!=(const const_iterator& _X) const
                        {return (!(*this == _X)); }
                bool operator<(const const_iterator& _X) const
                        {return (_Map < _X._Map
                                || _Map == _X._Map && _Next < _X._Next); }
                bool operator<=(const const_iterator& _X) const
                        {return (!(_X < *this)); }
                bool operator>(const const_iterator& _X) const
                        {return (_X < *this); }
                bool operator>=(const const_iterator& _X) const
                        {return (!(*this < _X)); }
        protected:
                void _Add(difference_type _N);
        _PROTECTED:
                _Tptr _First, _Last, _Next;
                _Mapptr _Map;
                };
        typedef typename std::reverse_iterator<iterator>
                reverse_iterator;
        typedef typename std::reverse_iterator<const_iterator>
                const_reverse_iterator;

        deque()
                : _Mybase(), _First(), _Last(),
                        _Map(0), _Mapsize(0), _Size(0)
                {}
        explicit deque(const _A& _Al)
                : _Mybase(_Al), _First(), _Last(),
                        _Map(0), _Mapsize(0), _Size(0)
                {}
        explicit deque(size_type _N)
                : _Mybase(), _First(), _Last(),
                        _Map(0), _Mapsize(0), _Size(0)
                {insert(begin(), _N, _Ty()); }
        deque(size_type _N, const _Ty& _V)
                : _Mybase(), _First(), _Last(),
                        _Map(0), _Mapsize(0), _Size(0)
                {insert(begin(), _N, _V); }
        deque(size_type _N, const _Ty& _V, const _A& _Al)
                : _Mybase(_Al), _First(), _Last(),
                        _Map(0), _Mapsize(0), _Size(0)
                {insert(begin(), _N, _V); }
        deque(const _Myt& _X)
                : _Mybase(_X._Alval), _First(), _Last(),
                        _Map(0), _Mapsize(0), _Size(0)
                {insert(begin(), _X.begin(), _X.end()); }
        template<class _It>
                deque(_It _F, _It _L)
                : _Mybase(), _First(), _Last(),
                        _Map(0), _Mapsize(0), _Size(0)
                {_Construct(_F, _L, _Iter_cat(_F)); }
        template<class _It>
                deque(_It _F, _It _L, const _A& _Al)
                : _Mybase(_Al), _First(), _Last(),
                        _Map(0), _Mapsize(0), _Size(0)
                {_Construct(_F, _L, _Iter_cat(_F)); }
        template<class _It>
                void _Construct(_It _F, _It _L, _Int_iterator_tag)
                {insert(begin(), (size_type)_F, (_Ty)_L); }
        template<class _It>
                void _Construct(_It _F, _It _L, input_iterator_tag)
                {insert(begin(), _F, _L); }
        ~deque()
                {while (!empty())
                        pop_front(); }
        _Myt& operator=(const _Myt& _X)
                {if (this != &_X)
                        {iterator _S;
                        if (_X.size() <= size())
                                {_S = copy(_X.begin(), _X.end(), begin());
                                erase(_S, end()); }
                        else
                                {const_iterator _Sx = _X.begin() + size();
                                _S = copy(_X.begin(), _Sx, begin());
                                insert(end(), _Sx, _X.end()); }}
                return (*this); }
        iterator begin()
                {return (_First); }
        const_iterator begin() const
                {return ((const_iterator)_First); }
        iterator end()
                {return (_Last); }
        const_iterator end() const
                {return ((const_iterator)_Last); }
        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())); }
        void resize(size_type _N)
                {resize(_N, _Ty()); }
        void resize(size_type _N, _Ty _X)
                {if (size() < _N)
                        insert(end(), _N - size(), _X);
                else if (_N < size())
                        erase(begin() + _N, end()); }
        size_type size() const
                {return (_Size); }
        size_type max_size() const
                {return (_Mybase::_Alval.max_size()); }
        bool empty() const
                {return (size() == 0); }
        allocator_type get_allocator() const
                {return (_Mybase::_Alval); }
        const_reference at(size_type _P) const
                {if (size() <= _P)
                        _Xran();
                return (*(begin() + _P)); }
        reference at(size_type _P)
                {if (size() <= _P)
                        _Xran();
                return (*(begin() + _P)); }
        const_reference operator[](size_type _P) const
                {return (*(begin() + _P)); }
        reference operator[](size_type _P)
                {return (*(begin() + _P)); }
        reference front()
                {return (*begin()); }
        const_reference front() const
                {return (*begin()); }
        reference back()
                {return (*(end() - 1)); }
        const_reference back() const
                {return (*(end() - 1)); }
        void push_front(const _Ty& _X);
        void pop_front()
                {if (!empty())
                        {_Mybase::_Alval.destroy(_First._Next);
                        _Popfront(); }}
        void push_back(const _Ty& _X);
        void pop_back()
                {if (!empty())
                        {iterator _P = _Last - 1;
                        _Mybase::_Alval.destroy(_P._Next);
                        _Popback(); }}
        template<class _It>
                void assign(_It _F, _It _L)
                {_Assign(_F, _L, _Iter_cat(_F)); }
        template<class _It>
                void _Assign(_It _F, _It _L, _Int_iterator_tag)
                {assign((size_type)_F, (_Ty)_L); }
        template<class _It>
                void _Assign(_It _F, _It _L, input_iterator_tag)
                {erase(begin(), end());
                insert(begin(), _F, _L); }
        void assign(size_type _N, const _Ty& _X)
                {_Ty _Tx = _X;
                erase(begin(), end());
                insert(begin(), _N, _Tx); }
        iterator insert(iterator _P, const _Ty& _X);
        void insert(iterator _P, size_type _M, const _Ty& _X);
        template<class _It>
                void insert(iterator _P, _It _F, _It _L)
                {_Insert(_P, _F, _L, _Iter_cat(_F)); }
        template<class _It>
                void _Insert(iterator _P, _It _F, _It _L,
                        _Int_iterator_tag)
                {insert(_P, (size_type)_F, (_Ty)_L); }
        template<class _It>
                void _Insert(iterator _P, _It _F, _It _L,
                        input_iterator_tag)
                {size_type _Off = _P - begin();
                for (; _F != _L; ++_F, ++_Off)
                        insert(begin() + _Off, *_F); }
        template<class _It>
                void _Insert(iterator _P, _It _F, _It _L,
                        bidirectional_iterator_tag);
        iterator erase(iterator _P)
                {return (erase(_P, _P + 1)); }
        iterator erase(iterator _F, iterator _L)
                {size_type _N = _L - _F;
                size_type _M = _F - begin();
                if (_M < (size_type)(end() - _L))
                        {copy_backward(begin(), _F, _L);
                        for (; 0 < _N; --_N)
                                pop_front(); }
                else
                        {copy(_L, end(), _F);
                        for (; 0 < _N; --_N)
                                pop_back(); }
                return (_M == 0 ? begin() : begin() + _M); }
        void clear()
                {while(!empty())
                        pop_back(); }
        void swap(_Myt& _X)
                {if (_Mybase::_Alval == _X._Alval)
                        {std::swap(_First, _X._First);
                        std::swap(_Last, _X._Last);
                        std::swap(_Map, _X._Map);
                        std::swap(_Mapsize, _X._Mapsize);
                        std::swap(_Size, _X._Size); }
                else
                        {_Myt _Ts = *this; *this = _X, _X = _Ts; }}
protected:
        void _Buyback();
        void _Buyfront();
        void _Freelast()
                {_Freeptr(_First._Map - 1);
                _Freeptr(_First._Map);
                _Freeptr(_First._Map + 1);
                _First = iterator();
                _Last = _First;
                _Freemap(); }
        void _Popfront()
                {_Mapptr _M = _First._Map;
                ++_First;
                --_Size;
                if (empty())
                        _Freelast();
                else if (_M != _First._Map)
                        {_Freeptr(_M);
                        _Setptr(_M, 0); }}
        void _Popback()
                {_Mapptr _M = _Last._Map;
                --_Last;
                --_Size;
                if (empty())
                        _Freelast();
                else if (_M != _Last._Map)
                        {_Freeptr(_M);
                        _Setptr(_M, 0); }}
        void _Xlen() const
                {_THROW(length_error, ""); }
        void _Xran() const
                {_THROW(out_of_range, ""); }
        void _Freemap()
                {_Mybase::_Almap.deallocate(_Map, _Mapsize); }
        void _Freeptr(_Mapptr _M)
                {_Mybase::_Alval.deallocate(*_M, _DEQUESIZ);
                _Mybase::_Almap.destroy(_M); }
        void _Getmap(_Tptr _P, int _Off)
                {_Mapsize = _DEQUEMAPSIZ;
                _Map = _Mybase::_Almap.allocate(_Mapsize, (void *)0);
                size_type _N = _Mapsize / 2;
                _Setptr(_Map + _N - 1, 0);
                _Setptr(_Map + _N, _P);
                _Setptr(_Map + _N + 1, 0);
                _First = iterator(_P + (_DEQUESIZ / 2 + _Off),
                        _Map + _N);
                _Last = _First; }
        _Mapptr _Growmap(size_type _Oldsize);
        void _Setptr(_Mapptr _M, _Tptr _P)
                {_Mybase::_Almap.construct(_M, _P); }
        iterator _First, _Last;
        _Mapptr _Map;
        size_type _Mapsize, _Size;
        };

                // deque TEMPLATE OPERATORS
template<class _Ty, class _A> inline
        void swap(deque<_Ty, _A>& _X, deque<_Ty, _A>& _Y)
        {_X.swap(_Y); }

template<class _Ty, class _A> inline
        bool operator==(const deque<_Ty, _A>& _X,
                const deque<_Ty, _A>& _Y)
        {return (_X.size() == _Y.size()
                && equal(_X.begin(), _X.end(), _Y.begin())); }
template<class _Ty, class _A> inline
        bool operator!=(const deque<_Ty, _A>& _X,
                const deque<_Ty, _A>& _Y)
        {return (!(_X == _Y)); }
template<class _Ty, class _A> inline
        bool operator<(const deque<_Ty, _A>& _X,
                const deque<_Ty, _A>& _Y)
        {return (lexicographical_compare(_X.begin(), _X.end(),
                _Y.begin(), _Y.end())); }
template<class _Ty, class _A> inline
        bool operator<=(const deque<_Ty, _A>& _X,
                const deque<_Ty, _A>& _Y)
        {return (!(_Y < _X)); }
template<class _Ty, class _A> inline
        bool operator>(const deque<_Ty, _A>& _X,
                const deque<_Ty, _A>& _Y)
        {return (_Y < _X); }
template<class _Ty, class _A> inline
        bool operator>=(const deque<_Ty, _A>& _X,
                const deque<_Ty, _A>& _Y)
        {return (!(_X < _Y)); }

template<class _Ty, class _Ax>
inline void deque<_Ty, _Ax>::iterator::_Add(difference_type _N)
        {difference_type _Off = _N + _Next - _First;
        difference_type _Moff = (0 <= _Off)
                ? _Off / _DEQUESIZ
                : 0 - ((_DEQUESIZ - 1 - _Off) / _DEQUESIZ);
        if (_Moff == 0)
                _Next += _N;
        else
                {_Map += _Moff;
                if (_Map[0] != 0)
                        {_First = _Map[0];
                        _Next = _First
                        + (_Off - _Moff * _DEQUESIZ); }
                else if (_Moff < 0)
                        {_First = _Map[1];
                        _Next = _First; }
                else
                        {_First = _Map[-1];
                        _Next = _First + _DEQUESIZ; }
                _Last = _First + _DEQUESIZ; }}


template<class _Ty, class _Ax>
inline void deque<_Ty, _Ax>::const_iterator::_Add(difference_type _N)
        {difference_type _Off = _N + _Next - _First;
        difference_type _Moff = (0 <= _Off)
                ? _Off / _DEQUESIZ
                : 0 - ((_DEQUESIZ - 1 - _Off) / _DEQUESIZ);
        if (_Moff == 0)
                _Next += _N;
        else
                {_Map += _Moff;
                if (_Map[0] != 0)
                        {_First = _Map[0];
                        _Next = _First
                                + (_Off - _Moff * _DEQUESIZ); }
                else if (_Moff < 0)
                        {_First = _Map[1];
                        _Next = _First; }
                else
                        {_First = _Map[-1];
                        _Next = _First + _DEQUESIZ; }
                _Last = _First + _DEQUESIZ; }}


template<class _Ty, class _Ax>
inline void deque<_Ty, _Ax>::push_front(const _Ty& _X)
        {if (max_size() - 1 <= _Size)
                _Xlen();
        if (empty() || _First._Next == _First._First)
                _Buyfront();
        --_First;
        _TRY_BEGIN
        _Mybase::_Alval.construct(_First._Next, _X);
        _CATCH_ALL
        _Popfront();
        _RERAISE;
        _CATCH_END
        ++_Size; }

template<class _Ty, class _Ax>
inline void deque<_Ty, _Ax>::push_back(const _Ty& _X)
        {if (max_size() - 1 <= _Size)
                _Xlen();
        if (empty() || _Last._Next == _Last._Last)
                _Buyback();
        ++_Last;
        _TRY_BEGIN
        iterator _P = _Last - 1;
        _Mybase::_Alval.construct(_P._Next, _X);
        _CATCH_ALL
        _Popback();
        _RERAISE;
        _CATCH_END
        ++_Size; }

template<class _Ty, class _Ax>
inline typename deque<_Ty, _Ax>::iterator deque<_Ty, _Ax>::insert(iterator _P, const _Ty& _X)
        {if (_P == begin())
                {push_front(_X);
                return (begin()); }
        else if (_P == end())
                {push_back(_X);
                return (end() - 1); }
        else
                {iterator _S;
                size_type _Off = _P - begin();
                _Ty _Tx = _X;
                if (_Off < size() / 2)
                        {push_front(front());
                        _S = begin() + _Off;
                        copy(begin() + 2, _S + 1, begin() + 1); }
                else
                        {push_back(back());
                        _S = begin() + _Off;
                        copy_backward(_S, end() - 2, end() - 1); }
                *_S = _Tx;
                return (_S); }}

template<class _Ty, class _Ax>
inline void deque<_Ty, _Ax>::insert(iterator _P, size_type _M, const _Ty& _X)
        {iterator _S;
        size_type _I;
        size_type _Off = _P - begin();
        size_type _Rem = _Size - _Off;
        if (_Off < _Rem)
                if (_Off < _M)
                        {for (_I = _M - _Off; 0 < _I; --_I)
                                push_front(_X);
                        for (_I = _Off; 0 < _I; --_I)
                                push_front(begin()[_M - 1]);
                        _S = begin() + _M;
                        fill(_S, _S + _Off, _X); }
                else
                        {for (_I = _M; 0 < _I; --_I)
                                push_front(begin()[_M - 1]);
                        _S = begin() + _M;
                        _Ty _Tx = _X;
                        copy(_S + _M, _S + _Off, _S);
                        fill(begin() + _Off, _S + _Off, _Tx); }
        else
                if (_Rem < _M)
                        {for (_I = _M - _Rem; 0 < _I; --_I)
                                push_back(_X);
                        for (_I = 0; _I < _Rem; ++_I)
                                push_back(begin()[_Off + _I]);
                        _S = begin() + _Off;
                        fill(_S, _S + _Rem, _X); }
                else
                        {for (_I = 0; _I < _M; ++_I)
                                push_back(begin()[_Off + _Rem - _M + _I]);
                        _S = begin() + _Off;
                        _Ty _Tx = _X;
                        copy_backward(_S, _S + _Rem - _M, _S + _Rem);
                        fill(_S, _S + _M, _Tx); }}

template<class _Ty, class _Ax>  template<class _It>
inline void deque<_Ty, _Ax>::_Insert(iterator _P, _It _F, _It _L, bidirectional_iterator_tag)
        {size_type _M = 0;
        _Distance(_F, _L, _M);
        size_type _I;
        size_type _Off = _P - begin();
        size_type _Rem = _Size - _Off;
        if (_Off < _Rem)
                if (_Off < _M)
                        {_It _Qx = _F;
                        advance(_Qx, _M - _Off);
                        for (_It _Q = _Qx; _F != _Q; )
                                push_front(*--_Q);
                        for (_I = _Off; 0 < _I; --_I)
                                push_front(begin()[_M - 1]);
                        copy(_Qx, _L, begin() + _M); }
                else
                        {for (_I = _M; 0 < _I; --_I)
                                push_front(begin()[_M - 1]);
                        iterator _S = begin() + _M;
                        copy(_S + _M, _S + _Off, _S);
                        copy(_F, _L, begin() + _Off); }
        else
                if (_Rem < _M)
                        {_It _Qx = _F;
                        advance(_Qx, _Rem);
                        for (_It _Q = _Qx; _Q != _L; ++_Q)
                                push_back(*_Q);
                        for (_I = 0; _I < _Rem; ++_I)
                                push_back(begin()[_Off + _I]);
                        copy(_F, _Qx, begin() + _Off); }
                else
                        {for (_I = 0; _I < _M; ++_I)
                                push_back(begin()[_Off + _Rem - _M + _I]);
                        iterator _S = begin() + _Off;
                        copy_backward(_S, _S + _Rem - _M, _S + _Rem);
                        copy(_F, _L, _S); }}

template<class _Ty, class _Ax>
inline void deque<_Ty, _Ax>::_Buyback()
        {_Tptr _P = _Mybase::_Alval.allocate(_DEQUESIZ, (void *)0);
        _TRY_BEGIN
        if (empty())
                _Getmap(_P, 0);
        else if (_Last._Map < _Map + (_Mapsize - 2))
                {_Setptr(++_Last._Map, _P);
                _Setptr(_Last._Map + 1, 0);
                _Last = iterator(_P, _Last._Map); }
        else
                {difference_type _I = _Last._Map - _First._Map + 1;
                _Mapptr _M = _Growmap(_I);
                _Setptr(_M + _I, _P);
                _Setptr(_M + _I + 1, 0);
                _First = iterator(_First._Next, _M);
                _Last = iterator(_P, _M + _I); }
        _CATCH_ALL
        _Mybase::_Alval.deallocate(_P, _DEQUESIZ);
        _RERAISE;
        _CATCH_END }

template<class _Ty, class _Ax>
inline void deque<_Ty, _Ax>::_Buyfront()
        {_Tptr _P = _Mybase::_Alval.allocate(_DEQUESIZ, (void *)0);
        _TRY_BEGIN
        if (empty())
                _Getmap(_P, 1);
        else if (_Map + 1 < _First._Map)
                {_Setptr(--_First._Map - 1, 0);
                _Setptr(_First._Map, _P);
                _First = iterator(_P + _DEQUESIZ, _First._Map); }
        else
                {difference_type _I = _Last._Map - _First._Map + 1;
                _Mapptr _M = _Growmap(_I);
                _Setptr(--_M - 1, 0);
                _Setptr(_M, _P);
                _First = iterator(_P + _DEQUESIZ, _M);
                _Last = iterator(_Last._Next, _M + _I); }
        _CATCH_ALL
        _Mybase::_Alval.deallocate(_P, _DEQUESIZ);
        _RERAISE;
        _CATCH_END }

template<class _Ty, class _Ax>
inline typename deque<_Ty, _Ax>::_Mapptr deque<_Ty, _Ax>::_Growmap(size_type _Oldsize)
        {size_type _Newsize = 2 * _Oldsize + 2;
        if (_Newsize < _DEQUEMAPSIZ)
                _Newsize = _DEQUEMAPSIZ;
        _Mapptr _Mo, _Mt, _Mx;
        if (_Newsize <= _Mapsize && _Mapsize / 4 < _Newsize)
                {_Mx = _Map + _Mapsize / 4;
                if (_Mx < _First._Map - 1)
                        for (_Mo = _First._Map - 1, _Mt = _Mx;
                                _Mo != _Last._Map + 2; ++_Mo, ++_Mt)
                                {_Mybase::_Almap.construct(_Mt, *_Mo);
                                _Mybase::_Almap.destroy(_Mo); }
                else
                        for (_Mo = _Last._Map + 2,
                                _Mt = _Mx + _Oldsize + 2;
                                _Mo != _First._Map - 1; )
                                {_Mybase::_Almap.construct(--_Mt, *--_Mo);
                                _Mybase::_Almap.destroy(_Mo); }}
        else
                {_Mapptr _M = _Mybase::_Almap.allocate(_Newsize,
                              (void *)0);
                _Mx = _M + _Newsize / 4;
                for (_Mo = _First._Map - 1, _Mt = _Mx;
                        _Mo != _Last._Map + 2; ++_Mo, ++_Mt)
                        {_Mybase::_Almap.construct(_Mt, *_Mo);
                        _Mybase::_Almap.destroy(_Mo); }
                _Mybase::_Almap.deallocate(_Map, _Mapsize);
                _Map = _M;
                _Mapsize = _Newsize; }
        return (_Mx + 1); }

_STD_END

#pragma namemangling()

#pragma info(none)
#ifndef __CHKHDR__
#  pragma report(pop)
#endif
#pragma info(restore)

#endif /* _DEQUE_ */

/*
 * Copyright (c) 1995-1998 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
 */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
V2.3:0081 */
