/**
*       Sean Vogel
*       11 -28 -2012
*       Just a linked list
*/
#ifndef SV_LINK_LIST
#define SV_LINK_LIST
 #define NULL 0
#include <limits>
 
namespace sv
{
        template <class T>
        class list
        {
                class node
                {      
                public:
                        node *prev,
                                *next;
 
                        T data;
 
                        node() : prev(NULL), next(NULL), data(NULL){}
                        node(const T& t) : prev(NULL), next(NULL), data(t){}
                };
 
                node *_front,
                        *_back;
                unsigned int _size;
 
        public:
                class iterator
                {
                        node* _node;
                public:
                        iterator() : _node(NULL){}
                        iterator(node* n) : _node(n){}
                        iterator(const iterator& it) : _node(it._node){}
                        T& operator*(){ if(_node)return _node->data; }
                        T& operator->(){ if(_node)return _node->data; }
                        iterator& operator++()
                        {
                                if(_node)
                                {
                                        _node = _node->next;
                                }
                                return *this;
                        }
                        iterator operator++(int)
                        {
                                iterator it(*this);
                                ++(*this);
                                return it;
                        }
                        iterator& operator--()
                        {
                                if(_node)
                                {
                                        _node = _node->prev;
                                }
                                return *this;
                        }
                        iterator& operator--(int)
                        {
                                iterator it(*this);
                                --(*this);
                                return it;
                        }
                        bool operator!=(const iterator& it) const { return (this->_node != it._node); }
 
                        iterator& operator=(const iterator& it)
                        {
                                _node = it._node;
                                return *this;
                        }
                };             
 
                //constructors
                list() : _front(NULL), _back(NULL), _size(NULL){}
                list(unsigned int , const T& t = T()){}
                list(const list<T>&);
                template < class InputIterator >
        list(InputIterator first, InputIterator last);
                ~list();
 
                //iterators
                iterator begin();
                iterator end();
                //iterator rbegin();
                //iterator rend();
 
                //operators
                list<T>& operator=(const list<T>&);
 
                //element access
                T& front();
                T& back();
 
                //capacity
                bool empty() const;
                unsigned int size() const;
                unsigned int max_size() const;
                void resize(unsigned int, const T& t);
 
                //modifiers
                void push_front(const T&);
                void pop_front();
                void push_back(const T&);
                void pop_back();
                //iterator insert(iterator pos, const T&);
                //void insert(iterator pos, unsigned int size, const T&);
                //void insert(iterator position, InputIterator first, InputIterator last);
                //iterator erase(iterator position);
                //iterator erase(iterator first, iterator last);
                //void swap(list<T>& lst);
                void clear();
                //void assign(size_type n, const T& u);
                //void assign(InputIterator first, InputIterator last);
 
                //operations
                //void remove(const T& value);
                //template <class Predicate>
                //void remove_if(Predicate pred);
                //void sort(list<T>& lst);
                //void merge(list<T>& lst):
                //void splice(iterator position, list<T,Allocator>& x);
                //void splice(iterator position, list<T,Allocator>& x, iterator i);
                //void splice(iterator position, list<T,Allocator>& x, iterator first, iterator last);
                //void unique();
                //template <class BinaryPredicate>
                //void unique(BinaryPredicate binary_pred);
                //void reverse();
        };
 
        template <class T>
        typename list<T>::iterator list<T>::begin()
        {
                return iterator(_front);
        }
 
        template <class T>
        typename list<T>::iterator list<T>::end()
        {
                return iterator(_back->next);
        }
 
        /*template <class T>
        typename list<T>::iterator list<T>::rbegin()
        {
                return iterator(_back);
        }
 
        template <class T>
        typename list<T>::iterator list<T>::rend()
        {
                return iterator(_front->prev);
        }*/
 
        template <class T>
        list<T>::list(const list<T>& lst) : _front(NULL), _back(NULL), _size(NULL)
        {
                if(!lst.empty())
                {
                        node* n = lst._front;                  
                        while(n)
                        {
                                push_back(n->data);
                                n = n->next;                                           
                        }
                }
        }
 
        template <class T>
        list<T>& list<T>::operator=(const list<T>& lst)
        {
                if(this != &lst && !lst.empty())
                {
                        clear();
 
                        node* n = lst._front;                  
                        while(n)
                        {
                                push_back(n->data);
                                n = n->next;                                           
                        }
                }
                return this;
        }
 
        template <class T>
        list<T>::~list()
        {
                clear();
        }
 
        template <class T>
        bool list<T>::empty()const {return !_front;}
 
        template <class T>
        unsigned int list<T>::size()const{return _size;}
 
        template <class T>
        unsigned int list<T>::max_size()const {return std::numeric_limits<T>::max();}
 
        template <class T>
        void list<T>::resize(unsigned int sz, const T& t = T())
        {
                while(sz > _size)
                {
                        push_back(t);
                }
        }
 
        template <class T>
        T& list<T>::front()
        {
                if(_front)
                        return _front->data;
        }
 
        template <class T>
        T& list<T>::back()
        {
                if(_back)
                        return _back->data;
        }
 
        template <class T>
        void list<T>::push_front(const T& t)
        {                      
                node* n = new node(t);
 
                if(_front)
                {
                        n->next = _front;
                        _front->prev = n;
                        _front = n;
                }
                else
                {
                        _back = _front = n;
                }
                ++_size;
        }
 
        template <class T>
        void list<T>::pop_front()
        {
                if(front)
                {
                        node* n = _front->next;
                        delete _front;
                        _front = n;
                        --_size;
                }              
        }
 
        template <class T>
        void list<T>::push_back(const T& t)
        {
                node* n = new node(t);
 
                if(_back)
                {
                        n->prev = _back;
                        _back->next = n;
                        _back = n;
                }
                else
                {
                        _front = _back = n;                    
                }
                ++_size;
        }
 
        template <class T>
        void list<T>::pop_back()
        {
                if(back)
                {
                        node* n = _back->prev;
                        delete _back;
                        _back = n;
                        --_size;
                }              
        }
 
        template <class T>
        void list<T>::clear()
        {
                node* n;
                while(_front)
                {
                        n = _front->next;
                        delete _front;
                        _front = n;
                        --_size;
                }
                _front = _back = NULL;
        }
}
#endif
#include <iostream>
int main()
{
        sv::list<int> lst;
        for(int i = 0; i < 10; ++i)
                lst.push_front(i + 1);
        lst.resize(20, 9333);
        if(!lst.empty())
                std::cout<<"front= " << lst.front()<<" back= "<<lst.back()<<" size= "<<lst.size()<<std::endl;
        {
        sv::list<int> lst2 = lst;
        if(!lst2.empty())
                std::cout<<"front= " << lst2.front()<<" back= "<<lst2.back()<<" size= "<<lst2.size()<<std::endl;
        }
 
        sv::list<int>::iterator it;
        sv::list<int>::iterator end = lst.end();
        for(it=lst.begin(); it != lst.end(); it++)
                std::cout<<*it<<std::endl;
 
        //std::cout<<l.max_size()<<std::endl;
        //std::cout<<lst.max_size()<<std::endl;
}

LyoqCiogICAgICAgU2VhbiBWb2dlbAoqICAgICAgIDExIC0yOCAtMjAxMgoqICAgICAgIEp1c3QgYSBsaW5rZWQgbGlzdAoqLwojaWZuZGVmIFNWX0xJTktfTElTVAojZGVmaW5lIFNWX0xJTktfTElTVAogI2RlZmluZSBOVUxMIDAKI2luY2x1ZGUgPGxpbWl0cz4KIApuYW1lc3BhY2Ugc3YKewogICAgICAgIHRlbXBsYXRlIDxjbGFzcyBUPgogICAgICAgIGNsYXNzIGxpc3QKICAgICAgICB7CiAgICAgICAgICAgICAgICBjbGFzcyBub2RlCiAgICAgICAgICAgICAgICB7ICAgICAgCiAgICAgICAgICAgICAgICBwdWJsaWM6CiAgICAgICAgICAgICAgICAgICAgICAgIG5vZGUgKnByZXYsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKm5leHQ7CiAKICAgICAgICAgICAgICAgICAgICAgICAgVCBkYXRhOwogCiAgICAgICAgICAgICAgICAgICAgICAgIG5vZGUoKSA6IHByZXYoTlVMTCksIG5leHQoTlVMTCksIGRhdGEoTlVMTCl7fQogICAgICAgICAgICAgICAgICAgICAgICBub2RlKGNvbnN0IFQmIHQpIDogcHJldihOVUxMKSwgbmV4dChOVUxMKSwgZGF0YSh0KXt9CiAgICAgICAgICAgICAgICB9OwogCiAgICAgICAgICAgICAgICBub2RlICpfZnJvbnQsCiAgICAgICAgICAgICAgICAgICAgICAgICpfYmFjazsKICAgICAgICAgICAgICAgIHVuc2lnbmVkIGludCBfc2l6ZTsKIAogICAgICAgIHB1YmxpYzoKICAgICAgICAgICAgICAgIGNsYXNzIGl0ZXJhdG9yCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIG5vZGUqIF9ub2RlOwogICAgICAgICAgICAgICAgcHVibGljOgogICAgICAgICAgICAgICAgICAgICAgICBpdGVyYXRvcigpIDogX25vZGUoTlVMTCl7fQogICAgICAgICAgICAgICAgICAgICAgICBpdGVyYXRvcihub2RlKiBuKSA6IF9ub2RlKG4pe30KICAgICAgICAgICAgICAgICAgICAgICAgaXRlcmF0b3IoY29uc3QgaXRlcmF0b3ImIGl0KSA6IF9ub2RlKGl0Ll9ub2RlKXt9CiAgICAgICAgICAgICAgICAgICAgICAgIFQmIG9wZXJhdG9yKigpeyBpZihfbm9kZSlyZXR1cm4gX25vZGUtPmRhdGE7IH0KICAgICAgICAgICAgICAgICAgICAgICAgVCYgb3BlcmF0b3ItPigpeyBpZihfbm9kZSlyZXR1cm4gX25vZGUtPmRhdGE7IH0KICAgICAgICAgICAgICAgICAgICAgICAgaXRlcmF0b3ImIG9wZXJhdG9yKysoKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYoX25vZGUpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgX25vZGUgPSBfbm9kZS0+bmV4dDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuICp0aGlzOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGl0ZXJhdG9yIG9wZXJhdG9yKysoaW50KQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaXRlcmF0b3IgaXQoKnRoaXMpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICsrKCp0aGlzKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gaXQ7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgaXRlcmF0b3ImIG9wZXJhdG9yLS0oKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYoX25vZGUpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgX25vZGUgPSBfbm9kZS0+cHJldjsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuICp0aGlzOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGl0ZXJhdG9yJiBvcGVyYXRvci0tKGludCkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGl0ZXJhdG9yIGl0KCp0aGlzKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAtLSgqdGhpcyk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGl0OwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGJvb2wgb3BlcmF0b3IhPShjb25zdCBpdGVyYXRvciYgaXQpIGNvbnN0IHsgcmV0dXJuICh0aGlzLT5fbm9kZSAhPSBpdC5fbm9kZSk7IH0KIAogICAgICAgICAgICAgICAgICAgICAgICBpdGVyYXRvciYgb3BlcmF0b3I9KGNvbnN0IGl0ZXJhdG9yJiBpdCkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIF9ub2RlID0gaXQuX25vZGU7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuICp0aGlzOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9OyAgICAgICAgICAgICAKIAogICAgICAgICAgICAgICAgLy9jb25zdHJ1Y3RvcnMKICAgICAgICAgICAgICAgIGxpc3QoKSA6IF9mcm9udChOVUxMKSwgX2JhY2soTlVMTCksIF9zaXplKE5VTEwpe30KICAgICAgICAgICAgICAgIGxpc3QodW5zaWduZWQgaW50ICwgY29uc3QgVCYgdCA9IFQoKSl7fQogICAgICAgICAgICAgICAgbGlzdChjb25zdCBsaXN0PFQ+Jik7CiAgICAgICAgICAgICAgICB0ZW1wbGF0ZSA8IGNsYXNzIElucHV0SXRlcmF0b3IgPgogICAgICAgIGxpc3QoSW5wdXRJdGVyYXRvciBmaXJzdCwgSW5wdXRJdGVyYXRvciBsYXN0KTsKICAgICAgICAgICAgICAgIH5saXN0KCk7CiAKICAgICAgICAgICAgICAgIC8vaXRlcmF0b3JzCiAgICAgICAgICAgICAgICBpdGVyYXRvciBiZWdpbigpOwogICAgICAgICAgICAgICAgaXRlcmF0b3IgZW5kKCk7CiAgICAgICAgICAgICAgICAvL2l0ZXJhdG9yIHJiZWdpbigpOwogICAgICAgICAgICAgICAgLy9pdGVyYXRvciByZW5kKCk7CiAKICAgICAgICAgICAgICAgIC8vb3BlcmF0b3JzCiAgICAgICAgICAgICAgICBsaXN0PFQ+JiBvcGVyYXRvcj0oY29uc3QgbGlzdDxUPiYpOwogCiAgICAgICAgICAgICAgICAvL2VsZW1lbnQgYWNjZXNzCiAgICAgICAgICAgICAgICBUJiBmcm9udCgpOwogICAgICAgICAgICAgICAgVCYgYmFjaygpOwogCiAgICAgICAgICAgICAgICAvL2NhcGFjaXR5CiAgICAgICAgICAgICAgICBib29sIGVtcHR5KCkgY29uc3Q7CiAgICAgICAgICAgICAgICB1bnNpZ25lZCBpbnQgc2l6ZSgpIGNvbnN0OwogICAgICAgICAgICAgICAgdW5zaWduZWQgaW50IG1heF9zaXplKCkgY29uc3Q7CiAgICAgICAgICAgICAgICB2b2lkIHJlc2l6ZSh1bnNpZ25lZCBpbnQsIGNvbnN0IFQmIHQpOwogCiAgICAgICAgICAgICAgICAvL21vZGlmaWVycwogICAgICAgICAgICAgICAgdm9pZCBwdXNoX2Zyb250KGNvbnN0IFQmKTsKICAgICAgICAgICAgICAgIHZvaWQgcG9wX2Zyb250KCk7CiAgICAgICAgICAgICAgICB2b2lkIHB1c2hfYmFjayhjb25zdCBUJik7CiAgICAgICAgICAgICAgICB2b2lkIHBvcF9iYWNrKCk7CiAgICAgICAgICAgICAgICAvL2l0ZXJhdG9yIGluc2VydChpdGVyYXRvciBwb3MsIGNvbnN0IFQmKTsKICAgICAgICAgICAgICAgIC8vdm9pZCBpbnNlcnQoaXRlcmF0b3IgcG9zLCB1bnNpZ25lZCBpbnQgc2l6ZSwgY29uc3QgVCYpOwogICAgICAgICAgICAgICAgLy92b2lkIGluc2VydChpdGVyYXRvciBwb3NpdGlvbiwgSW5wdXRJdGVyYXRvciBmaXJzdCwgSW5wdXRJdGVyYXRvciBsYXN0KTsKICAgICAgICAgICAgICAgIC8vaXRlcmF0b3IgZXJhc2UoaXRlcmF0b3IgcG9zaXRpb24pOwogICAgICAgICAgICAgICAgLy9pdGVyYXRvciBlcmFzZShpdGVyYXRvciBmaXJzdCwgaXRlcmF0b3IgbGFzdCk7CiAgICAgICAgICAgICAgICAvL3ZvaWQgc3dhcChsaXN0PFQ+JiBsc3QpOwogICAgICAgICAgICAgICAgdm9pZCBjbGVhcigpOwogICAgICAgICAgICAgICAgLy92b2lkIGFzc2lnbihzaXplX3R5cGUgbiwgY29uc3QgVCYgdSk7CiAgICAgICAgICAgICAgICAvL3ZvaWQgYXNzaWduKElucHV0SXRlcmF0b3IgZmlyc3QsIElucHV0SXRlcmF0b3IgbGFzdCk7CiAKICAgICAgICAgICAgICAgIC8vb3BlcmF0aW9ucwogICAgICAgICAgICAgICAgLy92b2lkIHJlbW92ZShjb25zdCBUJiB2YWx1ZSk7CiAgICAgICAgICAgICAgICAvL3RlbXBsYXRlIDxjbGFzcyBQcmVkaWNhdGU+CiAgICAgICAgICAgICAgICAvL3ZvaWQgcmVtb3ZlX2lmKFByZWRpY2F0ZSBwcmVkKTsKICAgICAgICAgICAgICAgIC8vdm9pZCBzb3J0KGxpc3Q8VD4mIGxzdCk7CiAgICAgICAgICAgICAgICAvL3ZvaWQgbWVyZ2UobGlzdDxUPiYgbHN0KToKICAgICAgICAgICAgICAgIC8vdm9pZCBzcGxpY2UoaXRlcmF0b3IgcG9zaXRpb24sIGxpc3Q8VCxBbGxvY2F0b3I+JiB4KTsKICAgICAgICAgICAgICAgIC8vdm9pZCBzcGxpY2UoaXRlcmF0b3IgcG9zaXRpb24sIGxpc3Q8VCxBbGxvY2F0b3I+JiB4LCBpdGVyYXRvciBpKTsKICAgICAgICAgICAgICAgIC8vdm9pZCBzcGxpY2UoaXRlcmF0b3IgcG9zaXRpb24sIGxpc3Q8VCxBbGxvY2F0b3I+JiB4LCBpdGVyYXRvciBmaXJzdCwgaXRlcmF0b3IgbGFzdCk7CiAgICAgICAgICAgICAgICAvL3ZvaWQgdW5pcXVlKCk7CiAgICAgICAgICAgICAgICAvL3RlbXBsYXRlIDxjbGFzcyBCaW5hcnlQcmVkaWNhdGU+CiAgICAgICAgICAgICAgICAvL3ZvaWQgdW5pcXVlKEJpbmFyeVByZWRpY2F0ZSBiaW5hcnlfcHJlZCk7CiAgICAgICAgICAgICAgICAvL3ZvaWQgcmV2ZXJzZSgpOwogICAgICAgIH07CiAKICAgICAgICB0ZW1wbGF0ZSA8Y2xhc3MgVD4KICAgICAgICB0eXBlbmFtZSBsaXN0PFQ+OjppdGVyYXRvciBsaXN0PFQ+OjpiZWdpbigpCiAgICAgICAgewogICAgICAgICAgICAgICAgcmV0dXJuIGl0ZXJhdG9yKF9mcm9udCk7CiAgICAgICAgfQogCiAgICAgICAgdGVtcGxhdGUgPGNsYXNzIFQ+CiAgICAgICAgdHlwZW5hbWUgbGlzdDxUPjo6aXRlcmF0b3IgbGlzdDxUPjo6ZW5kKCkKICAgICAgICB7CiAgICAgICAgICAgICAgICByZXR1cm4gaXRlcmF0b3IoX2JhY2stPm5leHQpOwogICAgICAgIH0KIAogICAgICAgIC8qdGVtcGxhdGUgPGNsYXNzIFQ+CiAgICAgICAgdHlwZW5hbWUgbGlzdDxUPjo6aXRlcmF0b3IgbGlzdDxUPjo6cmJlZ2luKCkKICAgICAgICB7CiAgICAgICAgICAgICAgICByZXR1cm4gaXRlcmF0b3IoX2JhY2spOwogICAgICAgIH0KIAogICAgICAgIHRlbXBsYXRlIDxjbGFzcyBUPgogICAgICAgIHR5cGVuYW1lIGxpc3Q8VD46Oml0ZXJhdG9yIGxpc3Q8VD46OnJlbmQoKQogICAgICAgIHsKICAgICAgICAgICAgICAgIHJldHVybiBpdGVyYXRvcihfZnJvbnQtPnByZXYpOwogICAgICAgIH0qLwogCiAgICAgICAgdGVtcGxhdGUgPGNsYXNzIFQ+CiAgICAgICAgbGlzdDxUPjo6bGlzdChjb25zdCBsaXN0PFQ+JiBsc3QpIDogX2Zyb250KE5VTEwpLCBfYmFjayhOVUxMKSwgX3NpemUoTlVMTCkKICAgICAgICB7CiAgICAgICAgICAgICAgICBpZighbHN0LmVtcHR5KCkpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIG5vZGUqIG4gPSBsc3QuX2Zyb250OyAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgICAgICB3aGlsZShuKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHVzaF9iYWNrKG4tPmRhdGEpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG4gPSBuLT5uZXh0OyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgIH0KIAogICAgICAgIHRlbXBsYXRlIDxjbGFzcyBUPgogICAgICAgIGxpc3Q8VD4mIGxpc3Q8VD46Om9wZXJhdG9yPShjb25zdCBsaXN0PFQ+JiBsc3QpCiAgICAgICAgewogICAgICAgICAgICAgICAgaWYodGhpcyAhPSAmbHN0ICYmICFsc3QuZW1wdHkoKSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgY2xlYXIoKTsKIAogICAgICAgICAgICAgICAgICAgICAgICBub2RlKiBuID0gbHN0Ll9mcm9udDsgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgd2hpbGUobikKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHB1c2hfYmFjayhuLT5kYXRhKTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBuID0gbi0+bmV4dDsgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIHJldHVybiB0aGlzOwogICAgICAgIH0KIAogICAgICAgIHRlbXBsYXRlIDxjbGFzcyBUPgogICAgICAgIGxpc3Q8VD46On5saXN0KCkKICAgICAgICB7CiAgICAgICAgICAgICAgICBjbGVhcigpOwogICAgICAgIH0KIAogICAgICAgIHRlbXBsYXRlIDxjbGFzcyBUPgogICAgICAgIGJvb2wgbGlzdDxUPjo6ZW1wdHkoKWNvbnN0IHtyZXR1cm4gIV9mcm9udDt9CiAKICAgICAgICB0ZW1wbGF0ZSA8Y2xhc3MgVD4KICAgICAgICB1bnNpZ25lZCBpbnQgbGlzdDxUPjo6c2l6ZSgpY29uc3R7cmV0dXJuIF9zaXplO30KIAogICAgICAgIHRlbXBsYXRlIDxjbGFzcyBUPgogICAgICAgIHVuc2lnbmVkIGludCBsaXN0PFQ+OjptYXhfc2l6ZSgpY29uc3Qge3JldHVybiBzdGQ6Om51bWVyaWNfbGltaXRzPFQ+OjptYXgoKTt9CiAKICAgICAgICB0ZW1wbGF0ZSA8Y2xhc3MgVD4KICAgICAgICB2b2lkIGxpc3Q8VD46OnJlc2l6ZSh1bnNpZ25lZCBpbnQgc3osIGNvbnN0IFQmIHQgPSBUKCkpCiAgICAgICAgewogICAgICAgICAgICAgICAgd2hpbGUoc3ogPiBfc2l6ZSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgcHVzaF9iYWNrKHQpOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0KIAogICAgICAgIHRlbXBsYXRlIDxjbGFzcyBUPgogICAgICAgIFQmIGxpc3Q8VD46OmZyb250KCkKICAgICAgICB7CiAgICAgICAgICAgICAgICBpZihfZnJvbnQpCiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBfZnJvbnQtPmRhdGE7CiAgICAgICAgfQogCiAgICAgICAgdGVtcGxhdGUgPGNsYXNzIFQ+CiAgICAgICAgVCYgbGlzdDxUPjo6YmFjaygpCiAgICAgICAgewogICAgICAgICAgICAgICAgaWYoX2JhY2spCiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBfYmFjay0+ZGF0YTsKICAgICAgICB9CiAKICAgICAgICB0ZW1wbGF0ZSA8Y2xhc3MgVD4KICAgICAgICB2b2lkIGxpc3Q8VD46OnB1c2hfZnJvbnQoY29uc3QgVCYgdCkKICAgICAgICB7ICAgICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgbm9kZSogbiA9IG5ldyBub2RlKHQpOwogCiAgICAgICAgICAgICAgICBpZihfZnJvbnQpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIG4tPm5leHQgPSBfZnJvbnQ7CiAgICAgICAgICAgICAgICAgICAgICAgIF9mcm9udC0+cHJldiA9IG47CiAgICAgICAgICAgICAgICAgICAgICAgIF9mcm9udCA9IG47CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIF9iYWNrID0gX2Zyb250ID0gbjsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICsrX3NpemU7CiAgICAgICAgfQogCiAgICAgICAgdGVtcGxhdGUgPGNsYXNzIFQ+CiAgICAgICAgdm9pZCBsaXN0PFQ+Ojpwb3BfZnJvbnQoKQogICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKGZyb250KQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBub2RlKiBuID0gX2Zyb250LT5uZXh0OwogICAgICAgICAgICAgICAgICAgICAgICBkZWxldGUgX2Zyb250OwogICAgICAgICAgICAgICAgICAgICAgICBfZnJvbnQgPSBuOwogICAgICAgICAgICAgICAgICAgICAgICAtLV9zaXplOwogICAgICAgICAgICAgICAgfSAgICAgICAgICAgICAgCiAgICAgICAgfQogCiAgICAgICAgdGVtcGxhdGUgPGNsYXNzIFQ+CiAgICAgICAgdm9pZCBsaXN0PFQ+OjpwdXNoX2JhY2soY29uc3QgVCYgdCkKICAgICAgICB7CiAgICAgICAgICAgICAgICBub2RlKiBuID0gbmV3IG5vZGUodCk7CiAKICAgICAgICAgICAgICAgIGlmKF9iYWNrKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBuLT5wcmV2ID0gX2JhY2s7CiAgICAgICAgICAgICAgICAgICAgICAgIF9iYWNrLT5uZXh0ID0gbjsKICAgICAgICAgICAgICAgICAgICAgICAgX2JhY2sgPSBuOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBfZnJvbnQgPSBfYmFjayA9IG47ICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICsrX3NpemU7CiAgICAgICAgfQogCiAgICAgICAgdGVtcGxhdGUgPGNsYXNzIFQ+CiAgICAgICAgdm9pZCBsaXN0PFQ+Ojpwb3BfYmFjaygpCiAgICAgICAgewogICAgICAgICAgICAgICAgaWYoYmFjaykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgbm9kZSogbiA9IF9iYWNrLT5wcmV2OwogICAgICAgICAgICAgICAgICAgICAgICBkZWxldGUgX2JhY2s7CiAgICAgICAgICAgICAgICAgICAgICAgIF9iYWNrID0gbjsKICAgICAgICAgICAgICAgICAgICAgICAgLS1fc2l6ZTsKICAgICAgICAgICAgICAgIH0gICAgICAgICAgICAgIAogICAgICAgIH0KIAogICAgICAgIHRlbXBsYXRlIDxjbGFzcyBUPgogICAgICAgIHZvaWQgbGlzdDxUPjo6Y2xlYXIoKQogICAgICAgIHsKICAgICAgICAgICAgICAgIG5vZGUqIG47CiAgICAgICAgICAgICAgICB3aGlsZShfZnJvbnQpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIG4gPSBfZnJvbnQtPm5leHQ7CiAgICAgICAgICAgICAgICAgICAgICAgIGRlbGV0ZSBfZnJvbnQ7CiAgICAgICAgICAgICAgICAgICAgICAgIF9mcm9udCA9IG47CiAgICAgICAgICAgICAgICAgICAgICAgIC0tX3NpemU7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBfZnJvbnQgPSBfYmFjayA9IE5VTEw7CiAgICAgICAgfQp9CiNlbmRpZgojaW5jbHVkZSA8aW9zdHJlYW0+CmludCBtYWluKCkKewogICAgICAgIHN2OjpsaXN0PGludD4gbHN0OwogICAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCAxMDsgKytpKQogICAgICAgICAgICAgICAgbHN0LnB1c2hfZnJvbnQoaSArIDEpOwogICAgICAgIGxzdC5yZXNpemUoMjAsIDkzMzMpOwogICAgICAgIGlmKCFsc3QuZW1wdHkoKSkKICAgICAgICAgICAgICAgIHN0ZDo6Y291dDw8ImZyb250PSAiIDw8IGxzdC5mcm9udCgpPDwiIGJhY2s9ICI8PGxzdC5iYWNrKCk8PCIgc2l6ZT0gIjw8bHN0LnNpemUoKTw8c3RkOjplbmRsOwogICAgICAgIHsKICAgICAgICBzdjo6bGlzdDxpbnQ+IGxzdDIgPSBsc3Q7CiAgICAgICAgaWYoIWxzdDIuZW1wdHkoKSkKICAgICAgICAgICAgICAgIHN0ZDo6Y291dDw8ImZyb250PSAiIDw8IGxzdDIuZnJvbnQoKTw8IiBiYWNrPSAiPDxsc3QyLmJhY2soKTw8IiBzaXplPSAiPDxsc3QyLnNpemUoKTw8c3RkOjplbmRsOwogICAgICAgIH0KIAogICAgICAgIHN2OjpsaXN0PGludD46Oml0ZXJhdG9yIGl0OwogICAgICAgIHN2OjpsaXN0PGludD46Oml0ZXJhdG9yIGVuZCA9IGxzdC5lbmQoKTsKICAgICAgICBmb3IoaXQ9bHN0LmJlZ2luKCk7IGl0ICE9IGxzdC5lbmQoKTsgaXQrKykKICAgICAgICAgICAgICAgIHN0ZDo6Y291dDw8Kml0PDxzdGQ6OmVuZGw7CiAKICAgICAgICAvL3N0ZDo6Y291dDw8bC5tYXhfc2l6ZSgpPDxzdGQ6OmVuZGw7CiAgICAgICAgLy9zdGQ6OmNvdXQ8PGxzdC5tYXhfc2l6ZSgpPDxzdGQ6OmVuZGw7Cn0=