#ifndef LITB_HASHTABLE_H
#define LITB_HASHTABLE_H
 
#include <type_traits>
#include <utility>
 
namespace litb {
   // A pair similar to std::pair, but a bit simplier
   template<typename First, typename Second>
   struct Pair {
      Pair()
         :first(), second()
      { }
 
      // for being able to construct us with non-deducible arguments
      // (e.g initializer lists)
      Pair(const First& first, const Second& second)
         :first(first), second(second)
      { }
 
      // for moving first and second into us
      template<typename First1, typename Second1,
         typename std::enable_if<
            std::is_convertible<First1, First>::value &&
            std::is_convertible<Second1, Second>::value,
         int>::type = 0>
      Pair(First1&& first, Second1&& second)
         :first(std::forward<First1>(first)), 
          second(std::forward<Second1>(second))
      { }
 
      // converting constructors from convertible pairs
      template<typename First1, typename Second1>
      Pair(const Pair<First1, Second1>& other)
         :first(other.first), second(other.second)
      { }
 
      // moving convertible pairs into us
      template<typename First1, typename Second1>
      Pair(Pair<First1, Second1>&& other)
         :first(std::move(other.first)), 
          second(std::move(other.second))
      { }
 
      // public, hence not prefixed by _
      First first;
      Second second;
   };
}
 
namespace litb {
   template<typename T>
   T min(const T& a, const T& b) {
      return a < b ? a : b;
   }
 
   template<typename T>
   T max(const T& a, const T& b) {
      return a > b ? a : b;
   }
 
   // add the cv-qualifiers of MaybeCv to T
   template<typename T, typename MaybeCv>
   struct TransferCv {
      typedef T type;
   };
   template<typename T, typename MaybeCv>
   struct TransferCv<T, const MaybeCv> {
      typedef const T type;
   };
   template<typename T, typename MaybeCv>
   struct TransferCv<T, volatile MaybeCv> {
      typedef volatile T type;
   };
   template<typename T, typename MaybeCv>
   struct TransferCv<T, const volatile MaybeCv> {
      typedef const volatile T type;
   };
}
 
#include <type_traits>
#include <cstdint>
 
namespace litb {
   inline uint32_t hash(int n) { return n; }
   inline uint32_t hash(unsigned n) { return n; }
 
   inline uint32_t hash(uint32_t n, std::true_type /* 32bit */) {
      return n;
   } 
   inline uint32_t hash(uint64_t n, std::false_type /* 64bit */) {
      uint32_t n32 = (uint32_t)n;
      return n32 ^ (uint32_t)(n >> 32);
   } 
 
   inline uint32_t hash(unsigned long n) { 
      return hash(n, std::integral_constant<bool, sizeof(unsigned long) == sizeof(uint32_t)>());
   }
   inline uint32_t hash(long n) { 
      return hash((unsigned long)n);
   }
 
   inline uint32_t hash(unsigned long long n) { 
      return hash(n, std::false_type());
   }
   inline uint32_t hash(long long n) { 
      return hash((unsigned long long)n); 
   }
}
 
#ifndef LITB_VECTOR_H
#define LITB_VECTOR_H
 
#include <new>
#include <type_traits>
 
namespace litb {
 
// The functionality of Vector that does not depend on the "SmallSize"
// template parameter.
//
template<typename T>
class VectorBase {
public:
   typedef T *iterator;
   typedef const T *const_iterator;
   typedef T value_type;
 
 
public:
   ~VectorBase() {
      clear();
      if(usesHeap()) {
         operator delete(_data);
      }
   }
 
public:
   iterator begin() { return _data; }
   iterator end() { return _endData; }
   const_iterator begin() const { return _data; }
   const_iterator end() const { return _endData; }
 
public:
   // returns a reference to the element at the given index
   T &at(int index) {
      return _data[index];
   }
 
   const T& at(int index) const {
      return _data[index];
   }
 
   T &operator[](int index) {
      return at(index);
   }
 
   const T& operator[](int index) const {
      return at(index); 
   }
 
   // appends a new item to the back of the vector
   void append(const T& t) {
      insert(end(), t);
   }
 
   void prepend(const T& t) {
      insert(begin(), t);
   }
 
   // inserts a new item before the given iterator, and return
   // an iterator to the new item
   iterator insert(iterator it, const T& t) {
      it = grow(it, 1);
      new ((void*)it) T(t);
      _endData++;
      return it;
   }
 
   // assigns the given range to this vector
   template<typename Iterator>
   void assign(Iterator b, Iterator e) {
      clear();
      insert(end(), b, e);
   }
 
   // inserts the range [b, e) before iterator position "it", and return
   // a pointer to the first item inserted
   template<typename Iterator>
   iterator insert(iterator it, Iterator b, Iterator e) {
      it = grow(it, e - b);
      for(; b != e; b++, it++) {
         new ((void*)it) T(*b);
         _endData++;
      }
      return it;
   }
 
   // returns true if the vector contains no elements
   bool isEmpty() const {
      return _data == _endData;
   }
 
   bool empty() const {
      return isEmpty();
   }
 
   // resizes the vector to be of the given size afterwards, initializing all 
   // new elements by value initialization
   void resize(int newSize) {
      if(size() < newSize) {
         iterator it = grow(end(), newSize - size());
         for(; newSize > 0; newSize--, it++) {
            new ((void*)it) T();
            _endData++;
         }
      } else if(size() > newSize) {
         erase(end() - (size() - newSize), end());
      }
   }
 
   // makes the vector have size() 0, without changing the capacity
   void clear() {
      for(; _endData != _data; _endData--) {
         _endData[-1].~T();
      }
      _endData = _data;
   }
 
   // erases the portion [b, e) of the vector, without changing the capacity
   void erase(iterator b, iterator e) {
      if(b == e) {
         clear();
         return;
      }
 
      for(; e != _endData; e++, b++) {
         *b = *e;
      }
      T *dptr = _endData;
      for(T *edptr = dptr - (e - b); dptr != edptr; dptr--)
         dptr->~T();
      _endData = dptr;
   }
 
   // returns the actual size of the vector
   int size() const { return _endData - _data; }
 
   // returns the reserved capacity of the vector that it can insert without
   // reallocating
   int capacity() const { return _endReserve - _data; }
 
   // returns true if we use the heap memory currently.
   bool usesHeap() const { return (const void*)_data != (this + 1); }
 
   // reserves space for at least "space" items
   void reserve(int space) {
      if(space <= capacity())
         return;
 
      grow(end(), space - capacity());
   }
 
   // simply uses the assign function
   VectorBase &operator=(const VectorBase& other) {
      if(this == &other)
         return *this;
      assign(other.begin(), other.end());
      return *this;
   }
 
protected:
   // VectorBase cannot be created on its own
   VectorBase(T *data, T *endData)
      :_data(data), _endData(data), _endReserve(endData)
   { }
 
private:
   // reserves space for "elements" items before iterator "it".
   // returns an iterator pointing at the first free slot.
   iterator grow(iterator it, int elements) {
      if(elements == 0)
         return it;
 
      int index = it - begin();
      if((_endReserve - _endData) < elements) {
         // reallocate, leaving "elements" free slots at "index"
         int newCapacity = max(capacity() * 2, capacity() + elements);
         T *data1 = (T*)operator new(sizeof(T) * newCapacity);
         T *endData1 = data1;
         T *endReserve1 = data1 + newCapacity;
         for(T *data = _data; data != _endData; data++, endData1++) {
            if(data - _data == index) {
               endData1 += elements;
            }
            new ((void*)endData1) T(*data);
         }
 
         for(; _endData != _data; _endData--)
            _endData[-1].~T();
         if(usesHeap()) {
            operator delete(_data);
         }
         _data = data1;
         _endData= endData1;
         _endReserve = endReserve1;
      } else if(it != end()) {
         T *endData1 = _endData, *endDataNew1 = _endData + elements;
         int newlyAllocated = min(elements, end() - it);
         for(; newlyAllocated > 0; newlyAllocated--, endDataNew1--, endData1--) {
            new ((void*)&endDataNew1[-1]) T(endData1[-1]); 
         }
         for(; endData1 != it; endData1--, endDataNew1--) {
            endDataNew1[-1] = endData1[-1];
         }
 
         // the hole should contain unconstructed items that the caller can placement-new into
         int dtorsInHole = min(elements, (end() - it));
         for(iterator itHole = it; dtorsInHole > 0; dtorsInHole--, itHole++)
            itHole->~T();
      }
      return begin() + index;
   }
 
private:
   T *_data;
   T *_endData;
   T *_endReserve;
};
 
// A vector that allocates "SmallSize" elements in its own memory and
// only if more elements are needed, reverts to heap memory.
template<typename T, int SmallSize>
class Vector : public VectorBase<T> {
   union {
      typename std::aligned_storage<sizeof(T), alignof(T)>::type
         _aligner;
      unsigned char _buffer[sizeof(T) * SmallSize];
   };
 
public:
   Vector():VectorBase<T>((T*)_buffer, (T*)_buffer + SmallSize) {}
   Vector(const Vector& other):Vector() {
      this->insert(this->end(), other.begin(), other.end());
   }
   template<int SmallSize1>
   Vector(const Vector<T, SmallSize1>& other):Vector() {
      this->insert(this->end(), other.begin(), other.end());
   }
};
 
// A vector similar to std::vector. 
template<typename T>
class DynamicVector : public VectorBase<T> {
   // this padding. VectorBase can then determine that its pointers do never 
   // point to the in-object buffer (as it cound otherise happen if VectorBase and its
   // malloced buffer would be adjacent in memory).
   char padding;
 
public:
   DynamicVector():VectorBase<T>(nullptr, nullptr) {}
   DynamicVector(const DynamicVector& other):DynamicVector() {
      this->insert(this->end(), other.begin(), other.end());
   }
};
 
}
 
#endif
 
#include <utility>
#include <iterator>
#include <cstdint>
 
namespace litb {
 
// A hash table mapping "Key" to "Value". 
// "Key" must provide a "hash" function that is
// found by argument-dependent-lookup.
template<typename Key, typename Value>
class HashTable {
   struct Bucket;
 
   template<typename BucketType>
   struct Iterator;
 
   typedef Iterator<Bucket> iterator;
   typedef Iterator<const Bucket> const_iterator;
   typedef Pair<const Key, Value> value_type;
   typedef Key key_type;
   typedef Value mapped_type;
 
public:
   HashTable():_size() { _buckets.append((Bucket*)-1); }
   ~HashTable() {
      clear();
   }
 
   iterator begin() { return iterator(_buckets.begin()); }
   iterator end() { return iterator(_buckets.end() - 1); }
   const_iterator begin() const { return const_iterator(_buckets.begin()); }
   const_iterator end() const { return const_iterator(_buckets.end() - 1); }
 
public:
   // returns the size (number of keys) of this table
   int size() const {
      return _size;
   }
 
   // inserts the given mapping, returning false if the key was already mapped. in that case,
   // the value will not be updated.
   bool insert(const Pair<Key, Value>& mapping) {
      struct C { 
         const Value &operator()() const { 
            return value;
         }
         const Value& value;
      } creator = { mapping.second };
      return internalInsert(mapping.first, creator);
   }
 
   // inserts a mapping of key to value.
   // returns true if the mapping was inserted, and false if the key was already
   // mapped. In that case, the value will not be updated.
   bool insert(const Key& key, const Value& value) {
      struct C { 
         const Value &operator()() const { 
            return value;
         }
         const Value& value;
      } creator = { value };
      return internalInsert(key, creator);
   }
 
   // returns true if the table contains a mapping from key to a value
   bool contains(const Key& key) const {
      return getBucket(key) != nullptr;
   }
 
   // returns a reference to the value mapped by the given key. If the element
   // does not exist yet, it is value-initialized and copied to the map.
   Value &at(const Key& key) {
      struct C { 
         Value operator()() const {
            return Value();
         }
      } creator;
      return getOrCreateBucket(key, creator)->_data.second;
   }
 
   Value &operator[](const Key& key) {
      return at(key);
   }
 
   // if for this overload the element does not exist, behavior is undefined
   const Value& at(const Key& key) const {
      return getBucket(key)->_data.second;
   }
 
   const Value& operator[](const Key& key) const {
      return at(key);
   }
 
   // after calling this the map contains no elements anymore and the bucket array
   // is empty
   void clear() {
      for(auto it = _buckets.begin(), ite = _buckets.end()-1; it != ite; ++it) {
         Bucket *bucket = *it;
         while(bucket) {
            Bucket *bucket1 = bucket;
            delete bucket1;
            bucket = bucket->_next;
         }
      }
      _buckets.clear();
      _buckets.append((Bucket*)-1);
      _size = 0;
   }
 
   // erases the item at the given position
   void erase(iterator it) {
      Bucket ** head = it._bucketHead;
      if(*head == it._bucket) {
         *head = (*head)->next;
      } else {
         Bucket *bucket = *head;
         for(; bucket->_next != it._bucket; bucket = bucket->_next)
            ;
         bucket->_next = it._bucket->next;
      }
      delete it._bucket;
      _size--;
   }
 
private:
   // one bucket in the buckets array
   struct Bucket {
      Bucket(const Key& key, const Value& value, Bucket *next)
         :_data(key, value), _next(next)
      { }
 
      value_type _data;
      Bucket *_next;
   };
 
   template<typename BucketType>
   struct Iterator {  
      template<typename Key1, typename Value1>
      friend class HashTable;
 
      typedef HashTable::value_type value_type;
      typedef typename TransferCv<value_type, BucketType>::type &reference_type;
      typedef typename TransferCv<value_type, BucketType>::type *pointer;
      typedef int difference_type;
      typedef std::forward_iterator_tag iterator_category;
 
      Iterator(typename TransferCv<BucketType*, BucketType>::type *bucketHead)
         :_bucketHead(bucketHead)
      { alignToNextBucket(); }
 
   public:
      friend bool operator==(const Iterator& a, const Iterator& b) {
         return a._bucket == b._bucket;
      }
 
      friend bool operator!=(const Iterator& a, const Iterator& b) {
         return !(a == b);
      }
 
   public:
      reference_type operator*() const {
         return _bucket->_data;
      }
 
      pointer operator->() const {
         return &_bucket->_data;
      }
 
      // convenience wrappers key() and value() return the key and the mapped data 
      // respectively
      const key_type& key() const {
         return (*this)->first;
      }
 
      typename TransferCv<mapped_type, BucketType>::type &value() const {
         return (*this)->second;
      }
 
   public:
      Iterator operator++(int) {
         Iterator it(*this);
         ++it;
         return it;
      }
 
      Iterator &operator++() {
         if(!_bucket->_next) {
            _bucketHead++;
            alignToNextBucket();
         } else {
            _bucket = _bucket->_next;
         }
         return *this;
      }
 
    private:
      void alignToNextBucket() {
         while (!*_bucketHead && *_bucketHead != (Bucket*)-1) {
            _bucketHead++;
         }
         _bucket = *_bucketHead;
      }
 
      typename TransferCv<BucketType*, BucketType>::type *_bucketHead;
      BucketType *_bucket;
   };
 
private:
   static uint32_t hash(const Key& key) {
      using litb::hash;
      return hash(key);
   }
 
   template<typename Creator>
   bool internalInsert(const Key& key, const Creator& c) {
      int oldSize = size();
      Bucket *bucket = getOrCreateBucket(key, c);
      return size() != oldSize;
   }
 
   // returns a bucket for the given key and value.
   // if not yet existing, call "creator()" to create and return a new
   // instance of the value.
   template<typename Creator>
   Bucket *getOrCreateBucket(const Key& key, const Creator& c) {
      if(_buckets.size() == 1) {
         _buckets.clear();
         _buckets.resize(32);
         _buckets.append((Bucket*)-1);
      } else {
         const float loadFactor = size() / (float)(_buckets.size() - 1);
         if(loadFactor > 0.75) {
            rehash();
         }
      }
 
      int bucketIndex = hash(key) % (_buckets.size() - 1);
      Bucket *bucket = _buckets[bucketIndex];
      for(Bucket *bucket1 = bucket; bucket1; bucket1 = bucket1->_next) {
         if(bucket1->_data.first == key) {
            return bucket1;
         }
      }
      bucket = new Bucket(key, c(), bucket);
      _buckets[bucketIndex] = bucket;
      _size++;
      return bucket;
   }
 
   // returns the bucket for the given key and nullptr if it is not found
   const Bucket *getBucket(const Key& key) const {
      if(_buckets.size() == 1)
         return nullptr;
 
      int bucketIndex = hash(key) % (_buckets.size() - 1);
      const Bucket *bucket = _buckets[bucketIndex];
      for(const Bucket *bucket1 = bucket; bucket1; bucket1 = bucket1->_next) {
         if(bucket1->_data.first == key) {
            return bucket1;
         }
      }
      return nullptr;
   }
 
   // this will reallocate the bucket array and rehash everything
   void rehash() {
      int newSize = (_buckets.size() - 1) * 2;
      Vector<Bucket*, 1> newBuckets;
      newBuckets.resize(newSize);
      for(auto it = _buckets.begin(), ite = _buckets.end()-1; it != ite; ++it) {
         Bucket *bucket = *it;
         while(bucket) {
            int bucketIndex = hash(bucket->_data.first) % newBuckets.size();
 
            Bucket *bucket1 = bucket;
            bucket = bucket->_next;
            bucket1->_next = newBuckets[bucketIndex];
            newBuckets[bucketIndex] = bucket1;
         }
      }
      newBuckets.append((Bucket*)-1);
      _buckets = std::move(newBuckets);
   }
 
private:
   // the last bucket pointer of _buckets designates the end() position
   // and always has the value (Bucket*)-1
   Vector<Bucket*, 1> _buckets;
   int _size;
};
}
 
#endif
 
#include <iostream>
 
struct A {
   A():x(-1) {
      std::cout << "A()" << std::endl;
   }
 
   A(int x):x(x) {
      std::cout << "A(" << x << ")" << std::endl;
   }
 
   ~A() {
      std::cout << "~A(" << x << ")" << std::endl;
   }
 
   A(A const& other):x(other.x) {
      std::cout << "A(A const&)(" << other.x << ")" << std::endl;
   }
 
   int x;
};
 
int main() {
   litb::HashTable<int, A> hashTable;
   for(int i = 0; i < 100; i++) 
      hashTable[i] = A(i * 2);
 
   std::cout << "\n";
   for(auto it = hashTable.begin(), ite = hashTable.end(); it != ite; ++it) {
      std::cout << "> (" << it->first << ") -> (" << it->second.x << ")\n";
   }
}
 
 

I2lmbmRlZiBMSVRCX0hBU0hUQUJMRV9ICiNkZWZpbmUgTElUQl9IQVNIVEFCTEVfSAoKI2luY2x1ZGUgPHR5cGVfdHJhaXRzPgojaW5jbHVkZSA8dXRpbGl0eT4KCm5hbWVzcGFjZSBsaXRiIHsKICAgLy8gQSBwYWlyIHNpbWlsYXIgdG8gc3RkOjpwYWlyLCBidXQgYSBiaXQgc2ltcGxpZXIKICAgdGVtcGxhdGU8dHlwZW5hbWUgRmlyc3QsIHR5cGVuYW1lIFNlY29uZD4KICAgc3RydWN0IFBhaXIgewogICAgICBQYWlyKCkKICAgICAgICAgOmZpcnN0KCksIHNlY29uZCgpCiAgICAgIHsgfQoKICAgICAgLy8gZm9yIGJlaW5nIGFibGUgdG8gY29uc3RydWN0IHVzIHdpdGggbm9uLWRlZHVjaWJsZSBhcmd1bWVudHMKICAgICAgLy8gKGUuZyBpbml0aWFsaXplciBsaXN0cykKICAgICAgUGFpcihjb25zdCBGaXJzdCYgZmlyc3QsIGNvbnN0IFNlY29uZCYgc2Vjb25kKQogICAgICAgICA6Zmlyc3QoZmlyc3QpLCBzZWNvbmQoc2Vjb25kKQogICAgICB7IH0KICAgICAgCiAgICAgIC8vIGZvciBtb3ZpbmcgZmlyc3QgYW5kIHNlY29uZCBpbnRvIHVzCiAgICAgIHRlbXBsYXRlPHR5cGVuYW1lIEZpcnN0MSwgdHlwZW5hbWUgU2Vjb25kMSwKICAgICAgICAgdHlwZW5hbWUgc3RkOjplbmFibGVfaWY8CiAgICAgICAgICAgIHN0ZDo6aXNfY29udmVydGlibGU8Rmlyc3QxLCBGaXJzdD46OnZhbHVlICYmCiAgICAgICAgICAgIHN0ZDo6aXNfY29udmVydGlibGU8U2Vjb25kMSwgU2Vjb25kPjo6dmFsdWUsCiAgICAgICAgIGludD46OnR5cGUgPSAwPgogICAgICBQYWlyKEZpcnN0MSYmIGZpcnN0LCBTZWNvbmQxJiYgc2Vjb25kKQogICAgICAgICA6Zmlyc3Qoc3RkOjpmb3J3YXJkPEZpcnN0MT4oZmlyc3QpKSwgCiAgICAgICAgICBzZWNvbmQoc3RkOjpmb3J3YXJkPFNlY29uZDE+KHNlY29uZCkpCiAgICAgIHsgfQogICAgICAgICAKICAgICAgLy8gY29udmVydGluZyBjb25zdHJ1Y3RvcnMgZnJvbSBjb252ZXJ0aWJsZSBwYWlycwogICAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBGaXJzdDEsIHR5cGVuYW1lIFNlY29uZDE+CiAgICAgIFBhaXIoY29uc3QgUGFpcjxGaXJzdDEsIFNlY29uZDE+JiBvdGhlcikKICAgICAgICAgOmZpcnN0KG90aGVyLmZpcnN0KSwgc2Vjb25kKG90aGVyLnNlY29uZCkKICAgICAgeyB9CgogICAgICAvLyBtb3ZpbmcgY29udmVydGlibGUgcGFpcnMgaW50byB1cwogICAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBGaXJzdDEsIHR5cGVuYW1lIFNlY29uZDE+CiAgICAgIFBhaXIoUGFpcjxGaXJzdDEsIFNlY29uZDE+JiYgb3RoZXIpCiAgICAgICAgIDpmaXJzdChzdGQ6Om1vdmUob3RoZXIuZmlyc3QpKSwgCiAgICAgICAgICBzZWNvbmQoc3RkOjptb3ZlKG90aGVyLnNlY29uZCkpCiAgICAgIHsgfQoKICAgICAgLy8gcHVibGljLCBoZW5jZSBub3QgcHJlZml4ZWQgYnkgXwogICAgICBGaXJzdCBmaXJzdDsKICAgICAgU2Vjb25kIHNlY29uZDsKICAgfTsKfQoKbmFtZXNwYWNlIGxpdGIgewogICB0ZW1wbGF0ZTx0eXBlbmFtZSBUPgogICBUIG1pbihjb25zdCBUJiBhLCBjb25zdCBUJiBiKSB7CiAgICAgIHJldHVybiBhIDwgYiA/IGEgOiBiOwogICB9CgogICB0ZW1wbGF0ZTx0eXBlbmFtZSBUPgogICBUIG1heChjb25zdCBUJiBhLCBjb25zdCBUJiBiKSB7CiAgICAgIHJldHVybiBhID4gYiA/IGEgOiBiOwogICB9CgogICAvLyBhZGQgdGhlIGN2LXF1YWxpZmllcnMgb2YgTWF5YmVDdiB0byBUCiAgIHRlbXBsYXRlPHR5cGVuYW1lIFQsIHR5cGVuYW1lIE1heWJlQ3Y+CiAgIHN0cnVjdCBUcmFuc2ZlckN2IHsKICAgICAgdHlwZWRlZiBUIHR5cGU7CiAgIH07CiAgIHRlbXBsYXRlPHR5cGVuYW1lIFQsIHR5cGVuYW1lIE1heWJlQ3Y+CiAgIHN0cnVjdCBUcmFuc2ZlckN2PFQsIGNvbnN0IE1heWJlQ3Y+IHsKICAgICAgdHlwZWRlZiBjb25zdCBUIHR5cGU7CiAgIH07CiAgIHRlbXBsYXRlPHR5cGVuYW1lIFQsIHR5cGVuYW1lIE1heWJlQ3Y+CiAgIHN0cnVjdCBUcmFuc2ZlckN2PFQsIHZvbGF0aWxlIE1heWJlQ3Y+IHsKICAgICAgdHlwZWRlZiB2b2xhdGlsZSBUIHR5cGU7CiAgIH07CiAgIHRlbXBsYXRlPHR5cGVuYW1lIFQsIHR5cGVuYW1lIE1heWJlQ3Y+CiAgIHN0cnVjdCBUcmFuc2ZlckN2PFQsIGNvbnN0IHZvbGF0aWxlIE1heWJlQ3Y+IHsKICAgICAgdHlwZWRlZiBjb25zdCB2b2xhdGlsZSBUIHR5cGU7CiAgIH07Cn0KCiNpbmNsdWRlIDx0eXBlX3RyYWl0cz4KI2luY2x1ZGUgPGNzdGRpbnQ+CgpuYW1lc3BhY2UgbGl0YiB7CiAgIGlubGluZSB1aW50MzJfdCBoYXNoKGludCBuKSB7IHJldHVybiBuOyB9CiAgIGlubGluZSB1aW50MzJfdCBoYXNoKHVuc2lnbmVkIG4pIHsgcmV0dXJuIG47IH0KCiAgIGlubGluZSB1aW50MzJfdCBoYXNoKHVpbnQzMl90IG4sIHN0ZDo6dHJ1ZV90eXBlIC8qIDMyYml0ICovKSB7CiAgICAgIHJldHVybiBuOwogICB9IAogICBpbmxpbmUgdWludDMyX3QgaGFzaCh1aW50NjRfdCBuLCBzdGQ6OmZhbHNlX3R5cGUgLyogNjRiaXQgKi8pIHsKICAgICAgdWludDMyX3QgbjMyID0gKHVpbnQzMl90KW47CiAgICAgIHJldHVybiBuMzIgXiAodWludDMyX3QpKG4gPj4gMzIpOwogICB9IAoKICAgaW5saW5lIHVpbnQzMl90IGhhc2godW5zaWduZWQgbG9uZyBuKSB7IAogICAgICByZXR1cm4gaGFzaChuLCBzdGQ6OmludGVncmFsX2NvbnN0YW50PGJvb2wsIHNpemVvZih1bnNpZ25lZCBsb25nKSA9PSBzaXplb2YodWludDMyX3QpPigpKTsKICAgfQogICBpbmxpbmUgdWludDMyX3QgaGFzaChsb25nIG4pIHsgCiAgICAgIHJldHVybiBoYXNoKCh1bnNpZ25lZCBsb25nKW4pOwogICB9CgogICBpbmxpbmUgdWludDMyX3QgaGFzaCh1bnNpZ25lZCBsb25nIGxvbmcgbikgeyAKICAgICAgcmV0dXJuIGhhc2gobiwgc3RkOjpmYWxzZV90eXBlKCkpOwogICB9CiAgIGlubGluZSB1aW50MzJfdCBoYXNoKGxvbmcgbG9uZyBuKSB7IAogICAgICByZXR1cm4gaGFzaCgodW5zaWduZWQgbG9uZyBsb25nKW4pOyAKICAgfQp9CgojaWZuZGVmIExJVEJfVkVDVE9SX0gKI2RlZmluZSBMSVRCX1ZFQ1RPUl9ICgojaW5jbHVkZSA8bmV3PgojaW5jbHVkZSA8dHlwZV90cmFpdHM+CgpuYW1lc3BhY2UgbGl0YiB7CgovLyBUaGUgZnVuY3Rpb25hbGl0eSBvZiBWZWN0b3IgdGhhdCBkb2VzIG5vdCBkZXBlbmQgb24gdGhlICJTbWFsbFNpemUiCi8vIHRlbXBsYXRlIHBhcmFtZXRlci4KLy8KdGVtcGxhdGU8dHlwZW5hbWUgVD4KY2xhc3MgVmVjdG9yQmFzZSB7CnB1YmxpYzoKICAgdHlwZWRlZiBUICppdGVyYXRvcjsKICAgdHlwZWRlZiBjb25zdCBUICpjb25zdF9pdGVyYXRvcjsKICAgdHlwZWRlZiBUIHZhbHVlX3R5cGU7CgogICAKcHVibGljOgogICB+VmVjdG9yQmFzZSgpIHsKICAgICAgY2xlYXIoKTsKICAgICAgaWYodXNlc0hlYXAoKSkgewogICAgICAgICBvcGVyYXRvciBkZWxldGUoX2RhdGEpOwogICAgICB9CiAgIH0KCnB1YmxpYzoKICAgaXRlcmF0b3IgYmVnaW4oKSB7IHJldHVybiBfZGF0YTsgfQogICBpdGVyYXRvciBlbmQoKSB7IHJldHVybiBfZW5kRGF0YTsgfQogICBjb25zdF9pdGVyYXRvciBiZWdpbigpIGNvbnN0IHsgcmV0dXJuIF9kYXRhOyB9CiAgIGNvbnN0X2l0ZXJhdG9yIGVuZCgpIGNvbnN0IHsgcmV0dXJuIF9lbmREYXRhOyB9CgpwdWJsaWM6CiAgIC8vIHJldHVybnMgYSByZWZlcmVuY2UgdG8gdGhlIGVsZW1lbnQgYXQgdGhlIGdpdmVuIGluZGV4CiAgIFQgJmF0KGludCBpbmRleCkgewogICAgICByZXR1cm4gX2RhdGFbaW5kZXhdOwogICB9CiAgIAogICBjb25zdCBUJiBhdChpbnQgaW5kZXgpIGNvbnN0IHsKICAgICAgcmV0dXJuIF9kYXRhW2luZGV4XTsKICAgfQoKICAgVCAmb3BlcmF0b3JbXShpbnQgaW5kZXgpIHsKICAgICAgcmV0dXJuIGF0KGluZGV4KTsKICAgfQoKICAgY29uc3QgVCYgb3BlcmF0b3JbXShpbnQgaW5kZXgpIGNvbnN0IHsKICAgICAgcmV0dXJuIGF0KGluZGV4KTsgCiAgIH0KICAgCiAgIC8vIGFwcGVuZHMgYSBuZXcgaXRlbSB0byB0aGUgYmFjayBvZiB0aGUgdmVjdG9yCiAgIHZvaWQgYXBwZW5kKGNvbnN0IFQmIHQpIHsKICAgICAgaW5zZXJ0KGVuZCgpLCB0KTsKICAgfQoKICAgdm9pZCBwcmVwZW5kKGNvbnN0IFQmIHQpIHsKICAgICAgaW5zZXJ0KGJlZ2luKCksIHQpOwogICB9CgogICAvLyBpbnNlcnRzIGEgbmV3IGl0ZW0gYmVmb3JlIHRoZSBnaXZlbiBpdGVyYXRvciwgYW5kIHJldHVybgogICAvLyBhbiBpdGVyYXRvciB0byB0aGUgbmV3IGl0ZW0KICAgaXRlcmF0b3IgaW5zZXJ0KGl0ZXJhdG9yIGl0LCBjb25zdCBUJiB0KSB7CiAgICAgIGl0ID0gZ3JvdyhpdCwgMSk7CiAgICAgIG5ldyAoKHZvaWQqKWl0KSBUKHQpOwogICAgICBfZW5kRGF0YSsrOwogICAgICByZXR1cm4gaXQ7CiAgIH0KCiAgIC8vIGFzc2lnbnMgdGhlIGdpdmVuIHJhbmdlIHRvIHRoaXMgdmVjdG9yCiAgIHRlbXBsYXRlPHR5cGVuYW1lIEl0ZXJhdG9yPgogICB2b2lkIGFzc2lnbihJdGVyYXRvciBiLCBJdGVyYXRvciBlKSB7CiAgICAgIGNsZWFyKCk7CiAgICAgIGluc2VydChlbmQoKSwgYiwgZSk7CiAgIH0KCiAgIC8vIGluc2VydHMgdGhlIHJhbmdlIFtiLCBlKSBiZWZvcmUgaXRlcmF0b3IgcG9zaXRpb24gIml0IiwgYW5kIHJldHVybgogICAvLyBhIHBvaW50ZXIgdG8gdGhlIGZpcnN0IGl0ZW0gaW5zZXJ0ZWQKICAgdGVtcGxhdGU8dHlwZW5hbWUgSXRlcmF0b3I+CiAgIGl0ZXJhdG9yIGluc2VydChpdGVyYXRvciBpdCwgSXRlcmF0b3IgYiwgSXRlcmF0b3IgZSkgewogICAgICBpdCA9IGdyb3coaXQsIGUgLSBiKTsKICAgICAgZm9yKDsgYiAhPSBlOyBiKyssIGl0KyspIHsKICAgICAgICAgbmV3ICgodm9pZCopaXQpIFQoKmIpOwogICAgICAgICBfZW5kRGF0YSsrOwogICAgICB9CiAgICAgIHJldHVybiBpdDsKICAgfQoKICAgLy8gcmV0dXJucyB0cnVlIGlmIHRoZSB2ZWN0b3IgY29udGFpbnMgbm8gZWxlbWVudHMKICAgYm9vbCBpc0VtcHR5KCkgY29uc3QgewogICAgICByZXR1cm4gX2RhdGEgPT0gX2VuZERhdGE7CiAgIH0KICAgCiAgIGJvb2wgZW1wdHkoKSBjb25zdCB7CiAgICAgIHJldHVybiBpc0VtcHR5KCk7CiAgIH0KCiAgIC8vIHJlc2l6ZXMgdGhlIHZlY3RvciB0byBiZSBvZiB0aGUgZ2l2ZW4gc2l6ZSBhZnRlcndhcmRzLCBpbml0aWFsaXppbmcgYWxsIAogICAvLyBuZXcgZWxlbWVudHMgYnkgdmFsdWUgaW5pdGlhbGl6YXRpb24KICAgdm9pZCByZXNpemUoaW50IG5ld1NpemUpIHsKICAgICAgaWYoc2l6ZSgpIDwgbmV3U2l6ZSkgewogICAgICAgICBpdGVyYXRvciBpdCA9IGdyb3coZW5kKCksIG5ld1NpemUgLSBzaXplKCkpOwogICAgICAgICBmb3IoOyBuZXdTaXplID4gMDsgbmV3U2l6ZS0tLCBpdCsrKSB7CiAgICAgICAgICAgIG5ldyAoKHZvaWQqKWl0KSBUKCk7CiAgICAgICAgICAgIF9lbmREYXRhKys7CiAgICAgICAgIH0KICAgICAgfSBlbHNlIGlmKHNpemUoKSA+IG5ld1NpemUpIHsKICAgICAgICAgZXJhc2UoZW5kKCkgLSAoc2l6ZSgpIC0gbmV3U2l6ZSksIGVuZCgpKTsKICAgICAgfQogICB9CgogICAvLyBtYWtlcyB0aGUgdmVjdG9yIGhhdmUgc2l6ZSgpIDAsIHdpdGhvdXQgY2hhbmdpbmcgdGhlIGNhcGFjaXR5CiAgIHZvaWQgY2xlYXIoKSB7CiAgICAgIGZvcig7IF9lbmREYXRhICE9IF9kYXRhOyBfZW5kRGF0YS0tKSB7CiAgICAgICAgIF9lbmREYXRhWy0xXS5+VCgpOwogICAgICB9CiAgICAgIF9lbmREYXRhID0gX2RhdGE7CiAgIH0KICAgCiAgIC8vIGVyYXNlcyB0aGUgcG9ydGlvbiBbYiwgZSkgb2YgdGhlIHZlY3Rvciwgd2l0aG91dCBjaGFuZ2luZyB0aGUgY2FwYWNpdHkKICAgdm9pZCBlcmFzZShpdGVyYXRvciBiLCBpdGVyYXRvciBlKSB7CiAgICAgIGlmKGIgPT0gZSkgewogICAgICAgICBjbGVhcigpOwogICAgICAgICByZXR1cm47CiAgICAgIH0KCiAgICAgIGZvcig7IGUgIT0gX2VuZERhdGE7IGUrKywgYisrKSB7CiAgICAgICAgICpiID0gKmU7CiAgICAgIH0KICAgICAgVCAqZHB0ciA9IF9lbmREYXRhOwogICAgICBmb3IoVCAqZWRwdHIgPSBkcHRyIC0gKGUgLSBiKTsgZHB0ciAhPSBlZHB0cjsgZHB0ci0tKQogICAgICAgICBkcHRyLT5+VCgpOwogICAgICBfZW5kRGF0YSA9IGRwdHI7CiAgIH0KCiAgIC8vIHJldHVybnMgdGhlIGFjdHVhbCBzaXplIG9mIHRoZSB2ZWN0b3IKICAgaW50IHNpemUoKSBjb25zdCB7IHJldHVybiBfZW5kRGF0YSAtIF9kYXRhOyB9CgogICAvLyByZXR1cm5zIHRoZSByZXNlcnZlZCBjYXBhY2l0eSBvZiB0aGUgdmVjdG9yIHRoYXQgaXQgY2FuIGluc2VydCB3aXRob3V0CiAgIC8vIHJlYWxsb2NhdGluZwogICBpbnQgY2FwYWNpdHkoKSBjb25zdCB7IHJldHVybiBfZW5kUmVzZXJ2ZSAtIF9kYXRhOyB9CgogICAvLyByZXR1cm5zIHRydWUgaWYgd2UgdXNlIHRoZSBoZWFwIG1lbW9yeSBjdXJyZW50bHkuCiAgIGJvb2wgdXNlc0hlYXAoKSBjb25zdCB7IHJldHVybiAoY29uc3Qgdm9pZCopX2RhdGEgIT0gKHRoaXMgKyAxKTsgfQoKICAgLy8gcmVzZXJ2ZXMgc3BhY2UgZm9yIGF0IGxlYXN0ICJzcGFjZSIgaXRlbXMKICAgdm9pZCByZXNlcnZlKGludCBzcGFjZSkgewogICAgICBpZihzcGFjZSA8PSBjYXBhY2l0eSgpKQogICAgICAgICByZXR1cm47CgogICAgICBncm93KGVuZCgpLCBzcGFjZSAtIGNhcGFjaXR5KCkpOwogICB9CgogICAvLyBzaW1wbHkgdXNlcyB0aGUgYXNzaWduIGZ1bmN0aW9uCiAgIFZlY3RvckJhc2UgJm9wZXJhdG9yPShjb25zdCBWZWN0b3JCYXNlJiBvdGhlcikgewogICAgICBpZih0aGlzID09ICZvdGhlcikKICAgICAgICAgcmV0dXJuICp0aGlzOwogICAgICBhc3NpZ24ob3RoZXIuYmVnaW4oKSwgb3RoZXIuZW5kKCkpOwogICAgICByZXR1cm4gKnRoaXM7CiAgIH0KCnByb3RlY3RlZDoKICAgLy8gVmVjdG9yQmFzZSBjYW5ub3QgYmUgY3JlYXRlZCBvbiBpdHMgb3duCiAgIFZlY3RvckJhc2UoVCAqZGF0YSwgVCAqZW5kRGF0YSkKICAgICAgOl9kYXRhKGRhdGEpLCBfZW5kRGF0YShkYXRhKSwgX2VuZFJlc2VydmUoZW5kRGF0YSkKICAgeyB9Cgpwcml2YXRlOgogICAvLyByZXNlcnZlcyBzcGFjZSBmb3IgImVsZW1lbnRzIiBpdGVtcyBiZWZvcmUgaXRlcmF0b3IgIml0Ii4KICAgLy8gcmV0dXJucyBhbiBpdGVyYXRvciBwb2ludGluZyBhdCB0aGUgZmlyc3QgZnJlZSBzbG90LgogICBpdGVyYXRvciBncm93KGl0ZXJhdG9yIGl0LCBpbnQgZWxlbWVudHMpIHsKICAgICAgaWYoZWxlbWVudHMgPT0gMCkKICAgICAgICAgcmV0dXJuIGl0OwoKICAgICAgaW50IGluZGV4ID0gaXQgLSBiZWdpbigpOwogICAgICBpZigoX2VuZFJlc2VydmUgLSBfZW5kRGF0YSkgPCBlbGVtZW50cykgewogICAgICAgICAvLyByZWFsbG9jYXRlLCBsZWF2aW5nICJlbGVtZW50cyIgZnJlZSBzbG90cyBhdCAiaW5kZXgiCiAgICAgICAgIGludCBuZXdDYXBhY2l0eSA9IG1heChjYXBhY2l0eSgpICogMiwgY2FwYWNpdHkoKSArIGVsZW1lbnRzKTsKICAgICAgICAgVCAqZGF0YTEgPSAoVCopb3BlcmF0b3IgbmV3KHNpemVvZihUKSAqIG5ld0NhcGFjaXR5KTsKICAgICAgICAgVCAqZW5kRGF0YTEgPSBkYXRhMTsKICAgICAgICAgVCAqZW5kUmVzZXJ2ZTEgPSBkYXRhMSArIG5ld0NhcGFjaXR5OwogICAgICAgICBmb3IoVCAqZGF0YSA9IF9kYXRhOyBkYXRhICE9IF9lbmREYXRhOyBkYXRhKyssIGVuZERhdGExKyspIHsKICAgICAgICAgICAgaWYoZGF0YSAtIF9kYXRhID09IGluZGV4KSB7CiAgICAgICAgICAgICAgIGVuZERhdGExICs9IGVsZW1lbnRzOwogICAgICAgICAgICB9CiAgICAgICAgICAgIG5ldyAoKHZvaWQqKWVuZERhdGExKSBUKCpkYXRhKTsKICAgICAgICAgfQogICAgICAKICAgICAgICAgZm9yKDsgX2VuZERhdGEgIT0gX2RhdGE7IF9lbmREYXRhLS0pCiAgICAgICAgICAgIF9lbmREYXRhWy0xXS5+VCgpOwogICAgICAgICBpZih1c2VzSGVhcCgpKSB7CiAgICAgICAgICAgIG9wZXJhdG9yIGRlbGV0ZShfZGF0YSk7CiAgICAgICAgIH0KICAgICAgICAgX2RhdGEgPSBkYXRhMTsKICAgICAgICAgX2VuZERhdGE9IGVuZERhdGExOwogICAgICAgICBfZW5kUmVzZXJ2ZSA9IGVuZFJlc2VydmUxOwogICAgICB9IGVsc2UgaWYoaXQgIT0gZW5kKCkpIHsKICAgICAgICAgVCAqZW5kRGF0YTEgPSBfZW5kRGF0YSwgKmVuZERhdGFOZXcxID0gX2VuZERhdGEgKyBlbGVtZW50czsKICAgICAgICAgaW50IG5ld2x5QWxsb2NhdGVkID0gbWluKGVsZW1lbnRzLCBlbmQoKSAtIGl0KTsKICAgICAgICAgZm9yKDsgbmV3bHlBbGxvY2F0ZWQgPiAwOyBuZXdseUFsbG9jYXRlZC0tLCBlbmREYXRhTmV3MS0tLCBlbmREYXRhMS0tKSB7CiAgICAgICAgICAgIG5ldyAoKHZvaWQqKSZlbmREYXRhTmV3MVstMV0pIFQoZW5kRGF0YTFbLTFdKTsgCiAgICAgICAgIH0KICAgICAgICAgZm9yKDsgZW5kRGF0YTEgIT0gaXQ7IGVuZERhdGExLS0sIGVuZERhdGFOZXcxLS0pIHsKICAgICAgICAgICAgZW5kRGF0YU5ldzFbLTFdID0gZW5kRGF0YTFbLTFdOwogICAgICAgICB9CgogICAgICAgICAvLyB0aGUgaG9sZSBzaG91bGQgY29udGFpbiB1bmNvbnN0cnVjdGVkIGl0ZW1zIHRoYXQgdGhlIGNhbGxlciBjYW4gcGxhY2VtZW50LW5ldyBpbnRvCiAgICAgICAgIGludCBkdG9yc0luSG9sZSA9IG1pbihlbGVtZW50cywgKGVuZCgpIC0gaXQpKTsKICAgICAgICAgZm9yKGl0ZXJhdG9yIGl0SG9sZSA9IGl0OyBkdG9yc0luSG9sZSA+IDA7IGR0b3JzSW5Ib2xlLS0sIGl0SG9sZSsrKQogICAgICAgICAgICBpdEhvbGUtPn5UKCk7CiAgICAgIH0KICAgICAgcmV0dXJuIGJlZ2luKCkgKyBpbmRleDsKICAgfQoKcHJpdmF0ZToKICAgVCAqX2RhdGE7CiAgIFQgKl9lbmREYXRhOwogICBUICpfZW5kUmVzZXJ2ZTsKfTsKCi8vIEEgdmVjdG9yIHRoYXQgYWxsb2NhdGVzICJTbWFsbFNpemUiIGVsZW1lbnRzIGluIGl0cyBvd24gbWVtb3J5IGFuZAovLyBvbmx5IGlmIG1vcmUgZWxlbWVudHMgYXJlIG5lZWRlZCwgcmV2ZXJ0cyB0byBoZWFwIG1lbW9yeS4KdGVtcGxhdGU8dHlwZW5hbWUgVCwgaW50IFNtYWxsU2l6ZT4KY2xhc3MgVmVjdG9yIDogcHVibGljIFZlY3RvckJhc2U8VD4gewogICB1bmlvbiB7CiAgICAgIHR5cGVuYW1lIHN0ZDo6YWxpZ25lZF9zdG9yYWdlPHNpemVvZihUKSwgYWxpZ25vZihUKT46OnR5cGUKICAgICAgICAgX2FsaWduZXI7CiAgICAgIHVuc2lnbmVkIGNoYXIgX2J1ZmZlcltzaXplb2YoVCkgKiBTbWFsbFNpemVdOwogICB9OwoKcHVibGljOgogICBWZWN0b3IoKTpWZWN0b3JCYXNlPFQ+KChUKilfYnVmZmVyLCAoVCopX2J1ZmZlciArIFNtYWxsU2l6ZSkge30KICAgVmVjdG9yKGNvbnN0IFZlY3RvciYgb3RoZXIpOlZlY3RvcigpIHsKICAgICAgdGhpcy0+aW5zZXJ0KHRoaXMtPmVuZCgpLCBvdGhlci5iZWdpbigpLCBvdGhlci5lbmQoKSk7CiAgIH0KICAgdGVtcGxhdGU8aW50IFNtYWxsU2l6ZTE+CiAgIFZlY3Rvcihjb25zdCBWZWN0b3I8VCwgU21hbGxTaXplMT4mIG90aGVyKTpWZWN0b3IoKSB7CiAgICAgIHRoaXMtPmluc2VydCh0aGlzLT5lbmQoKSwgb3RoZXIuYmVnaW4oKSwgb3RoZXIuZW5kKCkpOwogICB9Cn07CgovLyBBIHZlY3RvciBzaW1pbGFyIHRvIHN0ZDo6dmVjdG9yLiAKdGVtcGxhdGU8dHlwZW5hbWUgVD4KY2xhc3MgRHluYW1pY1ZlY3RvciA6IHB1YmxpYyBWZWN0b3JCYXNlPFQ+IHsKICAgLy8gdGhpcyBwYWRkaW5nLiBWZWN0b3JCYXNlIGNhbiB0aGVuIGRldGVybWluZSB0aGF0IGl0cyBwb2ludGVycyBkbyBuZXZlciAKICAgLy8gcG9pbnQgdG8gdGhlIGluLW9iamVjdCBidWZmZXIgKGFzIGl0IGNvdW5kIG90aGVyaXNlIGhhcHBlbiBpZiBWZWN0b3JCYXNlIGFuZCBpdHMKICAgLy8gbWFsbG9jZWQgYnVmZmVyIHdvdWxkIGJlIGFkamFjZW50IGluIG1lbW9yeSkuCiAgIGNoYXIgcGFkZGluZzsKCnB1YmxpYzoKICAgRHluYW1pY1ZlY3RvcigpOlZlY3RvckJhc2U8VD4obnVsbHB0ciwgbnVsbHB0cikge30KICAgRHluYW1pY1ZlY3Rvcihjb25zdCBEeW5hbWljVmVjdG9yJiBvdGhlcik6RHluYW1pY1ZlY3RvcigpIHsKICAgICAgdGhpcy0+aW5zZXJ0KHRoaXMtPmVuZCgpLCBvdGhlci5iZWdpbigpLCBvdGhlci5lbmQoKSk7CiAgIH0KfTsKCn0KCiNlbmRpZgoKI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxpdGVyYXRvcj4KI2luY2x1ZGUgPGNzdGRpbnQ+CgpuYW1lc3BhY2UgbGl0YiB7CgovLyBBIGhhc2ggdGFibGUgbWFwcGluZyAiS2V5IiB0byAiVmFsdWUiLiAKLy8gIktleSIgbXVzdCBwcm92aWRlIGEgImhhc2giIGZ1bmN0aW9uIHRoYXQgaXMKLy8gZm91bmQgYnkgYXJndW1lbnQtZGVwZW5kZW50LWxvb2t1cC4KdGVtcGxhdGU8dHlwZW5hbWUgS2V5LCB0eXBlbmFtZSBWYWx1ZT4KY2xhc3MgSGFzaFRhYmxlIHsKICAgc3RydWN0IEJ1Y2tldDsKCiAgIHRlbXBsYXRlPHR5cGVuYW1lIEJ1Y2tldFR5cGU+CiAgIHN0cnVjdCBJdGVyYXRvcjsKCiAgIHR5cGVkZWYgSXRlcmF0b3I8QnVja2V0PiBpdGVyYXRvcjsKICAgdHlwZWRlZiBJdGVyYXRvcjxjb25zdCBCdWNrZXQ+IGNvbnN0X2l0ZXJhdG9yOwogICB0eXBlZGVmIFBhaXI8Y29uc3QgS2V5LCBWYWx1ZT4gdmFsdWVfdHlwZTsKICAgdHlwZWRlZiBLZXkga2V5X3R5cGU7CiAgIHR5cGVkZWYgVmFsdWUgbWFwcGVkX3R5cGU7CgpwdWJsaWM6CiAgIEhhc2hUYWJsZSgpOl9zaXplKCkgeyBfYnVja2V0cy5hcHBlbmQoKEJ1Y2tldCopLTEpOyB9CiAgIH5IYXNoVGFibGUoKSB7CiAgICAgIGNsZWFyKCk7CiAgIH0KCiAgIGl0ZXJhdG9yIGJlZ2luKCkgeyByZXR1cm4gaXRlcmF0b3IoX2J1Y2tldHMuYmVnaW4oKSk7IH0KICAgaXRlcmF0b3IgZW5kKCkgeyByZXR1cm4gaXRlcmF0b3IoX2J1Y2tldHMuZW5kKCkgLSAxKTsgfQogICBjb25zdF9pdGVyYXRvciBiZWdpbigpIGNvbnN0IHsgcmV0dXJuIGNvbnN0X2l0ZXJhdG9yKF9idWNrZXRzLmJlZ2luKCkpOyB9CiAgIGNvbnN0X2l0ZXJhdG9yIGVuZCgpIGNvbnN0IHsgcmV0dXJuIGNvbnN0X2l0ZXJhdG9yKF9idWNrZXRzLmVuZCgpIC0gMSk7IH0KCnB1YmxpYzoKICAgLy8gcmV0dXJucyB0aGUgc2l6ZSAobnVtYmVyIG9mIGtleXMpIG9mIHRoaXMgdGFibGUKICAgaW50IHNpemUoKSBjb25zdCB7CiAgICAgIHJldHVybiBfc2l6ZTsKICAgfQoKICAgLy8gaW5zZXJ0cyB0aGUgZ2l2ZW4gbWFwcGluZywgcmV0dXJuaW5nIGZhbHNlIGlmIHRoZSBrZXkgd2FzIGFscmVhZHkgbWFwcGVkLiBpbiB0aGF0IGNhc2UsCiAgIC8vIHRoZSB2YWx1ZSB3aWxsIG5vdCBiZSB1cGRhdGVkLgogICBib29sIGluc2VydChjb25zdCBQYWlyPEtleSwgVmFsdWU+JiBtYXBwaW5nKSB7CiAgICAgIHN0cnVjdCBDIHsgCiAgICAgICAgIGNvbnN0IFZhbHVlICZvcGVyYXRvcigpKCkgY29uc3QgeyAKICAgICAgICAgICAgcmV0dXJuIHZhbHVlOwogICAgICAgICB9CiAgICAgICAgIGNvbnN0IFZhbHVlJiB2YWx1ZTsKICAgICAgfSBjcmVhdG9yID0geyBtYXBwaW5nLnNlY29uZCB9OwogICAgICByZXR1cm4gaW50ZXJuYWxJbnNlcnQobWFwcGluZy5maXJzdCwgY3JlYXRvcik7CiAgIH0KCiAgIC8vIGluc2VydHMgYSBtYXBwaW5nIG9mIGtleSB0byB2YWx1ZS4KICAgLy8gcmV0dXJucyB0cnVlIGlmIHRoZSBtYXBwaW5nIHdhcyBpbnNlcnRlZCwgYW5kIGZhbHNlIGlmIHRoZSBrZXkgd2FzIGFscmVhZHkKICAgLy8gbWFwcGVkLiBJbiB0aGF0IGNhc2UsIHRoZSB2YWx1ZSB3aWxsIG5vdCBiZSB1cGRhdGVkLgogICBib29sIGluc2VydChjb25zdCBLZXkmIGtleSwgY29uc3QgVmFsdWUmIHZhbHVlKSB7CiAgICAgIHN0cnVjdCBDIHsgCiAgICAgICAgIGNvbnN0IFZhbHVlICZvcGVyYXRvcigpKCkgY29uc3QgeyAKICAgICAgICAgICAgcmV0dXJuIHZhbHVlOwogICAgICAgICB9CiAgICAgICAgIGNvbnN0IFZhbHVlJiB2YWx1ZTsKICAgICAgfSBjcmVhdG9yID0geyB2YWx1ZSB9OwogICAgICByZXR1cm4gaW50ZXJuYWxJbnNlcnQoa2V5LCBjcmVhdG9yKTsKICAgfQoKICAgLy8gcmV0dXJucyB0cnVlIGlmIHRoZSB0YWJsZSBjb250YWlucyBhIG1hcHBpbmcgZnJvbSBrZXkgdG8gYSB2YWx1ZQogICBib29sIGNvbnRhaW5zKGNvbnN0IEtleSYga2V5KSBjb25zdCB7CiAgICAgIHJldHVybiBnZXRCdWNrZXQoa2V5KSAhPSBudWxscHRyOwogICB9CgogICAvLyByZXR1cm5zIGEgcmVmZXJlbmNlIHRvIHRoZSB2YWx1ZSBtYXBwZWQgYnkgdGhlIGdpdmVuIGtleS4gSWYgdGhlIGVsZW1lbnQKICAgLy8gZG9lcyBub3QgZXhpc3QgeWV0LCBpdCBpcyB2YWx1ZS1pbml0aWFsaXplZCBhbmQgY29waWVkIHRvIHRoZSBtYXAuCiAgIFZhbHVlICZhdChjb25zdCBLZXkmIGtleSkgewogICAgICBzdHJ1Y3QgQyB7IAogICAgICAgICBWYWx1ZSBvcGVyYXRvcigpKCkgY29uc3QgewogICAgICAgICAgICByZXR1cm4gVmFsdWUoKTsKICAgICAgICAgfQogICAgICB9IGNyZWF0b3I7CiAgICAgIHJldHVybiBnZXRPckNyZWF0ZUJ1Y2tldChrZXksIGNyZWF0b3IpLT5fZGF0YS5zZWNvbmQ7CiAgIH0KCiAgIFZhbHVlICZvcGVyYXRvcltdKGNvbnN0IEtleSYga2V5KSB7CiAgICAgIHJldHVybiBhdChrZXkpOwogICB9CgogICAvLyBpZiBmb3IgdGhpcyBvdmVybG9hZCB0aGUgZWxlbWVudCBkb2VzIG5vdCBleGlzdCwgYmVoYXZpb3IgaXMgdW5kZWZpbmVkCiAgIGNvbnN0IFZhbHVlJiBhdChjb25zdCBLZXkmIGtleSkgY29uc3QgewogICAgICByZXR1cm4gZ2V0QnVja2V0KGtleSktPl9kYXRhLnNlY29uZDsKICAgfQoKICAgY29uc3QgVmFsdWUmIG9wZXJhdG9yW10oY29uc3QgS2V5JiBrZXkpIGNvbnN0IHsKICAgICAgcmV0dXJuIGF0KGtleSk7CiAgIH0KCiAgIC8vIGFmdGVyIGNhbGxpbmcgdGhpcyB0aGUgbWFwIGNvbnRhaW5zIG5vIGVsZW1lbnRzIGFueW1vcmUgYW5kIHRoZSBidWNrZXQgYXJyYXkKICAgLy8gaXMgZW1wdHkKICAgdm9pZCBjbGVhcigpIHsKICAgICAgZm9yKGF1dG8gaXQgPSBfYnVja2V0cy5iZWdpbigpLCBpdGUgPSBfYnVja2V0cy5lbmQoKS0xOyBpdCAhPSBpdGU7ICsraXQpIHsKICAgICAgICAgQnVja2V0ICpidWNrZXQgPSAqaXQ7CiAgICAgICAgIHdoaWxlKGJ1Y2tldCkgewogICAgICAgICAgICBCdWNrZXQgKmJ1Y2tldDEgPSBidWNrZXQ7CiAgICAgICAgICAgIGRlbGV0ZSBidWNrZXQxOwogICAgICAgICAgICBidWNrZXQgPSBidWNrZXQtPl9uZXh0OwogICAgICAgICB9CiAgICAgIH0KICAgICAgX2J1Y2tldHMuY2xlYXIoKTsKICAgICAgX2J1Y2tldHMuYXBwZW5kKChCdWNrZXQqKS0xKTsKICAgICAgX3NpemUgPSAwOwogICB9CgogICAvLyBlcmFzZXMgdGhlIGl0ZW0gYXQgdGhlIGdpdmVuIHBvc2l0aW9uCiAgIHZvaWQgZXJhc2UoaXRlcmF0b3IgaXQpIHsKICAgICAgQnVja2V0ICoqIGhlYWQgPSBpdC5fYnVja2V0SGVhZDsKICAgICAgaWYoKmhlYWQgPT0gaXQuX2J1Y2tldCkgewogICAgICAgICAqaGVhZCA9ICgqaGVhZCktPm5leHQ7CiAgICAgIH0gZWxzZSB7CiAgICAgICAgIEJ1Y2tldCAqYnVja2V0ID0gKmhlYWQ7CiAgICAgICAgIGZvcig7IGJ1Y2tldC0+X25leHQgIT0gaXQuX2J1Y2tldDsgYnVja2V0ID0gYnVja2V0LT5fbmV4dCkKICAgICAgICAgICAgOwogICAgICAgICBidWNrZXQtPl9uZXh0ID0gaXQuX2J1Y2tldC0+bmV4dDsKICAgICAgfQogICAgICBkZWxldGUgaXQuX2J1Y2tldDsKICAgICAgX3NpemUtLTsKICAgfQoKcHJpdmF0ZToKICAgLy8gb25lIGJ1Y2tldCBpbiB0aGUgYnVja2V0cyBhcnJheQogICBzdHJ1Y3QgQnVja2V0IHsKICAgICAgQnVja2V0KGNvbnN0IEtleSYga2V5LCBjb25zdCBWYWx1ZSYgdmFsdWUsIEJ1Y2tldCAqbmV4dCkKICAgICAgICAgOl9kYXRhKGtleSwgdmFsdWUpLCBfbmV4dChuZXh0KQogICAgICB7IH0KCiAgICAgIHZhbHVlX3R5cGUgX2RhdGE7CiAgICAgIEJ1Y2tldCAqX25leHQ7CiAgIH07CgogICB0ZW1wbGF0ZTx0eXBlbmFtZSBCdWNrZXRUeXBlPgogICBzdHJ1Y3QgSXRlcmF0b3IgeyAgCiAgICAgIHRlbXBsYXRlPHR5cGVuYW1lIEtleTEsIHR5cGVuYW1lIFZhbHVlMT4KICAgICAgZnJpZW5kIGNsYXNzIEhhc2hUYWJsZTsKCiAgICAgIHR5cGVkZWYgSGFzaFRhYmxlOjp2YWx1ZV90eXBlIHZhbHVlX3R5cGU7CiAgICAgIHR5cGVkZWYgdHlwZW5hbWUgVHJhbnNmZXJDdjx2YWx1ZV90eXBlLCBCdWNrZXRUeXBlPjo6dHlwZSAmcmVmZXJlbmNlX3R5cGU7CiAgICAgIHR5cGVkZWYgdHlwZW5hbWUgVHJhbnNmZXJDdjx2YWx1ZV90eXBlLCBCdWNrZXRUeXBlPjo6dHlwZSAqcG9pbnRlcjsKICAgICAgdHlwZWRlZiBpbnQgZGlmZmVyZW5jZV90eXBlOwogICAgICB0eXBlZGVmIHN0ZDo6Zm9yd2FyZF9pdGVyYXRvcl90YWcgaXRlcmF0b3JfY2F0ZWdvcnk7CgogICAgICBJdGVyYXRvcih0eXBlbmFtZSBUcmFuc2ZlckN2PEJ1Y2tldFR5cGUqLCBCdWNrZXRUeXBlPjo6dHlwZSAqYnVja2V0SGVhZCkKICAgICAgICAgOl9idWNrZXRIZWFkKGJ1Y2tldEhlYWQpCiAgICAgIHsgYWxpZ25Ub05leHRCdWNrZXQoKTsgfQogICAgIAogICBwdWJsaWM6CiAgICAgIGZyaWVuZCBib29sIG9wZXJhdG9yPT0oY29uc3QgSXRlcmF0b3ImIGEsIGNvbnN0IEl0ZXJhdG9yJiBiKSB7CiAgICAgICAgIHJldHVybiBhLl9idWNrZXQgPT0gYi5fYnVja2V0OwogICAgICB9CgogICAgICBmcmllbmQgYm9vbCBvcGVyYXRvciE9KGNvbnN0IEl0ZXJhdG9yJiBhLCBjb25zdCBJdGVyYXRvciYgYikgewogICAgICAgICByZXR1cm4gIShhID09IGIpOwogICAgICB9CgogICBwdWJsaWM6CiAgICAgIHJlZmVyZW5jZV90eXBlIG9wZXJhdG9yKigpIGNvbnN0IHsKICAgICAgICAgcmV0dXJuIF9idWNrZXQtPl9kYXRhOwogICAgICB9CgogICAgICBwb2ludGVyIG9wZXJhdG9yLT4oKSBjb25zdCB7CiAgICAgICAgIHJldHVybiAmX2J1Y2tldC0+X2RhdGE7CiAgICAgIH0KICAgICAgCiAgICAgIC8vIGNvbnZlbmllbmNlIHdyYXBwZXJzIGtleSgpIGFuZCB2YWx1ZSgpIHJldHVybiB0aGUga2V5IGFuZCB0aGUgbWFwcGVkIGRhdGEgCiAgICAgIC8vIHJlc3BlY3RpdmVseQogICAgICBjb25zdCBrZXlfdHlwZSYga2V5KCkgY29uc3QgewogICAgICAgICByZXR1cm4gKCp0aGlzKS0+Zmlyc3Q7CiAgICAgIH0KCiAgICAgIHR5cGVuYW1lIFRyYW5zZmVyQ3Y8bWFwcGVkX3R5cGUsIEJ1Y2tldFR5cGU+Ojp0eXBlICZ2YWx1ZSgpIGNvbnN0IHsKICAgICAgICAgcmV0dXJuICgqdGhpcyktPnNlY29uZDsKICAgICAgfQoKICAgcHVibGljOgogICAgICBJdGVyYXRvciBvcGVyYXRvcisrKGludCkgewogICAgICAgICBJdGVyYXRvciBpdCgqdGhpcyk7CiAgICAgICAgICsraXQ7CiAgICAgICAgIHJldHVybiBpdDsKICAgICAgfQoKICAgICAgSXRlcmF0b3IgJm9wZXJhdG9yKysoKSB7CiAgICAgICAgIGlmKCFfYnVja2V0LT5fbmV4dCkgewogICAgICAgICAgICBfYnVja2V0SGVhZCsrOwogICAgICAgICAgICBhbGlnblRvTmV4dEJ1Y2tldCgpOwogICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBfYnVja2V0ID0gX2J1Y2tldC0+X25leHQ7CiAgICAgICAgIH0KICAgICAgICAgcmV0dXJuICp0aGlzOwogICAgICB9CgogICAgcHJpdmF0ZToKICAgICAgdm9pZCBhbGlnblRvTmV4dEJ1Y2tldCgpIHsKICAgICAgICAgd2hpbGUgKCEqX2J1Y2tldEhlYWQgJiYgKl9idWNrZXRIZWFkICE9IChCdWNrZXQqKS0xKSB7CiAgICAgICAgICAgIF9idWNrZXRIZWFkKys7CiAgICAgICAgIH0KICAgICAgICAgX2J1Y2tldCA9ICpfYnVja2V0SGVhZDsKICAgICAgfQoKICAgICAgdHlwZW5hbWUgVHJhbnNmZXJDdjxCdWNrZXRUeXBlKiwgQnVja2V0VHlwZT46OnR5cGUgKl9idWNrZXRIZWFkOwogICAgICBCdWNrZXRUeXBlICpfYnVja2V0OwogICB9OwoKcHJpdmF0ZToKICAgc3RhdGljIHVpbnQzMl90IGhhc2goY29uc3QgS2V5JiBrZXkpIHsKICAgICAgdXNpbmcgbGl0Yjo6aGFzaDsKICAgICAgcmV0dXJuIGhhc2goa2V5KTsKICAgfQoKICAgdGVtcGxhdGU8dHlwZW5hbWUgQ3JlYXRvcj4KICAgYm9vbCBpbnRlcm5hbEluc2VydChjb25zdCBLZXkmIGtleSwgY29uc3QgQ3JlYXRvciYgYykgewogICAgICBpbnQgb2xkU2l6ZSA9IHNpemUoKTsKICAgICAgQnVja2V0ICpidWNrZXQgPSBnZXRPckNyZWF0ZUJ1Y2tldChrZXksIGMpOwogICAgICByZXR1cm4gc2l6ZSgpICE9IG9sZFNpemU7CiAgIH0KCiAgIC8vIHJldHVybnMgYSBidWNrZXQgZm9yIHRoZSBnaXZlbiBrZXkgYW5kIHZhbHVlLgogICAvLyBpZiBub3QgeWV0IGV4aXN0aW5nLCBjYWxsICJjcmVhdG9yKCkiIHRvIGNyZWF0ZSBhbmQgcmV0dXJuIGEgbmV3CiAgIC8vIGluc3RhbmNlIG9mIHRoZSB2YWx1ZS4KICAgdGVtcGxhdGU8dHlwZW5hbWUgQ3JlYXRvcj4KICAgQnVja2V0ICpnZXRPckNyZWF0ZUJ1Y2tldChjb25zdCBLZXkmIGtleSwgY29uc3QgQ3JlYXRvciYgYykgewogICAgICBpZihfYnVja2V0cy5zaXplKCkgPT0gMSkgewogICAgICAgICBfYnVja2V0cy5jbGVhcigpOwogICAgICAgICBfYnVja2V0cy5yZXNpemUoMzIpOwogICAgICAgICBfYnVja2V0cy5hcHBlbmQoKEJ1Y2tldCopLTEpOwogICAgICB9IGVsc2UgewogICAgICAgICBjb25zdCBmbG9hdCBsb2FkRmFjdG9yID0gc2l6ZSgpIC8gKGZsb2F0KShfYnVja2V0cy5zaXplKCkgLSAxKTsKICAgICAgICAgaWYobG9hZEZhY3RvciA+IDAuNzUpIHsKICAgICAgICAgICAgcmVoYXNoKCk7CiAgICAgICAgIH0KICAgICAgfQoKICAgICAgaW50IGJ1Y2tldEluZGV4ID0gaGFzaChrZXkpICUgKF9idWNrZXRzLnNpemUoKSAtIDEpOwogICAgICBCdWNrZXQgKmJ1Y2tldCA9IF9idWNrZXRzW2J1Y2tldEluZGV4XTsKICAgICAgZm9yKEJ1Y2tldCAqYnVja2V0MSA9IGJ1Y2tldDsgYnVja2V0MTsgYnVja2V0MSA9IGJ1Y2tldDEtPl9uZXh0KSB7CiAgICAgICAgIGlmKGJ1Y2tldDEtPl9kYXRhLmZpcnN0ID09IGtleSkgewogICAgICAgICAgICByZXR1cm4gYnVja2V0MTsKICAgICAgICAgfQogICAgICB9CiAgICAgIGJ1Y2tldCA9IG5ldyBCdWNrZXQoa2V5LCBjKCksIGJ1Y2tldCk7CiAgICAgIF9idWNrZXRzW2J1Y2tldEluZGV4XSA9IGJ1Y2tldDsKICAgICAgX3NpemUrKzsKICAgICAgcmV0dXJuIGJ1Y2tldDsKICAgfQoKICAgLy8gcmV0dXJucyB0aGUgYnVja2V0IGZvciB0aGUgZ2l2ZW4ga2V5IGFuZCBudWxscHRyIGlmIGl0IGlzIG5vdCBmb3VuZAogICBjb25zdCBCdWNrZXQgKmdldEJ1Y2tldChjb25zdCBLZXkmIGtleSkgY29uc3QgewogICAgICBpZihfYnVja2V0cy5zaXplKCkgPT0gMSkKICAgICAgICAgcmV0dXJuIG51bGxwdHI7CgogICAgICBpbnQgYnVja2V0SW5kZXggPSBoYXNoKGtleSkgJSAoX2J1Y2tldHMuc2l6ZSgpIC0gMSk7CiAgICAgIGNvbnN0IEJ1Y2tldCAqYnVja2V0ID0gX2J1Y2tldHNbYnVja2V0SW5kZXhdOwogICAgICBmb3IoY29uc3QgQnVja2V0ICpidWNrZXQxID0gYnVja2V0OyBidWNrZXQxOyBidWNrZXQxID0gYnVja2V0MS0+X25leHQpIHsKICAgICAgICAgaWYoYnVja2V0MS0+X2RhdGEuZmlyc3QgPT0ga2V5KSB7CiAgICAgICAgICAgIHJldHVybiBidWNrZXQxOwogICAgICAgICB9CiAgICAgIH0KICAgICAgcmV0dXJuIG51bGxwdHI7CiAgIH0KCiAgIC8vIHRoaXMgd2lsbCByZWFsbG9jYXRlIHRoZSBidWNrZXQgYXJyYXkgYW5kIHJlaGFzaCBldmVyeXRoaW5nCiAgIHZvaWQgcmVoYXNoKCkgewogICAgICBpbnQgbmV3U2l6ZSA9IChfYnVja2V0cy5zaXplKCkgLSAxKSAqIDI7CiAgICAgIFZlY3RvcjxCdWNrZXQqLCAxPiBuZXdCdWNrZXRzOwogICAgICBuZXdCdWNrZXRzLnJlc2l6ZShuZXdTaXplKTsKICAgICAgZm9yKGF1dG8gaXQgPSBfYnVja2V0cy5iZWdpbigpLCBpdGUgPSBfYnVja2V0cy5lbmQoKS0xOyBpdCAhPSBpdGU7ICsraXQpIHsKICAgICAgICAgQnVja2V0ICpidWNrZXQgPSAqaXQ7CiAgICAgICAgIHdoaWxlKGJ1Y2tldCkgewogICAgICAgICAgICBpbnQgYnVja2V0SW5kZXggPSBoYXNoKGJ1Y2tldC0+X2RhdGEuZmlyc3QpICUgbmV3QnVja2V0cy5zaXplKCk7CgogICAgICAgICAgICBCdWNrZXQgKmJ1Y2tldDEgPSBidWNrZXQ7CiAgICAgICAgICAgIGJ1Y2tldCA9IGJ1Y2tldC0+X25leHQ7CiAgICAgICAgICAgIGJ1Y2tldDEtPl9uZXh0ID0gbmV3QnVja2V0c1tidWNrZXRJbmRleF07CiAgICAgICAgICAgIG5ld0J1Y2tldHNbYnVja2V0SW5kZXhdID0gYnVja2V0MTsKICAgICAgICAgfQogICAgICB9CiAgICAgIG5ld0J1Y2tldHMuYXBwZW5kKChCdWNrZXQqKS0xKTsKICAgICAgX2J1Y2tldHMgPSBzdGQ6Om1vdmUobmV3QnVja2V0cyk7CiAgIH0KCnByaXZhdGU6CiAgIC8vIHRoZSBsYXN0IGJ1Y2tldCBwb2ludGVyIG9mIF9idWNrZXRzIGRlc2lnbmF0ZXMgdGhlIGVuZCgpIHBvc2l0aW9uCiAgIC8vIGFuZCBhbHdheXMgaGFzIHRoZSB2YWx1ZSAoQnVja2V0KiktMQogICBWZWN0b3I8QnVja2V0KiwgMT4gX2J1Y2tldHM7CiAgIGludCBfc2l6ZTsKfTsKfQoKI2VuZGlmCgojaW5jbHVkZSA8aW9zdHJlYW0+CgpzdHJ1Y3QgQSB7CiAgIEEoKTp4KC0xKSB7CiAgICAgIHN0ZDo6Y291dCA8PCAiQSgpIiA8PCBzdGQ6OmVuZGw7CiAgIH0KCiAgIEEoaW50IHgpOngoeCkgewogICAgICBzdGQ6OmNvdXQgPDwgIkEoIiA8PCB4IDw8ICIpIiA8PCBzdGQ6OmVuZGw7CiAgIH0KCiAgIH5BKCkgewogICAgICBzdGQ6OmNvdXQgPDwgIn5BKCIgPDwgeCA8PCAiKSIgPDwgc3RkOjplbmRsOwogICB9CgogICBBKEEgY29uc3QmIG90aGVyKTp4KG90aGVyLngpIHsKICAgICAgc3RkOjpjb3V0IDw8ICJBKEEgY29uc3QmKSgiIDw8IG90aGVyLnggPDwgIikiIDw8IHN0ZDo6ZW5kbDsKICAgfQoKICAgaW50IHg7Cn07CgppbnQgbWFpbigpIHsKICAgbGl0Yjo6SGFzaFRhYmxlPGludCwgQT4gaGFzaFRhYmxlOwogICBmb3IoaW50IGkgPSAwOyBpIDwgMTAwOyBpKyspIAogICAgICBoYXNoVGFibGVbaV0gPSBBKGkgKiAyKTsKCiAgIHN0ZDo6Y291dCA8PCAiXG4iOwogICBmb3IoYXV0byBpdCA9IGhhc2hUYWJsZS5iZWdpbigpLCBpdGUgPSBoYXNoVGFibGUuZW5kKCk7IGl0ICE9IGl0ZTsgKytpdCkgewogICAgICBzdGQ6OmNvdXQgPDwgIj4gKCIgPDwgaXQtPmZpcnN0IDw8ICIpIC0+ICgiIDw8IGl0LT5zZWNvbmQueCA8PCAiKVxuIjsKICAgfQp9Cgo=