template<class T> void inline system_alloc(T*&ptr, size_t count) {
    ptr = (T*)realloc(ptr, count * sizeof(T));
    assert(ptr || count == 0);
}

struct DefaultCtrNoCopy {  // Thanks mmozeiko!
    DefaultCtrNoCopy() = default;
    DefaultCtrNoCopy(DefaultCtrNoCopy const&) = delete;
    DefaultCtrNoCopy& operator=(DefaultCtrNoCopy const&) = delete;
};

template<typename T> struct DLList:DefaultCtrNoCopy {
    struct Wrapper {
        Wrapper*prev = 0;
        Wrapper*next = 0;
        T wrapped; };
    Wrapper*first    = 0;
    Wrapper*last     = 0;

    inline auto insert_after(Wrapper*item, Wrapper*new_item) {
        new_item->prev                   = item;
        new_item->next                   = item->next;
        if (item->next) item->next->prev = new_item;
        else            last             = new_item;
        item->next                       = new_item;
        return                             new_item;     }
    inline auto insert_before(Wrapper*item, Wrapper*new_item) {
        new_item->next                   = item;
        new_item->prev                   = item->prev;
        if (item->prev) item->prev->next = new_item;
        else            first            = new_item;
        item->prev                       = new_item;
        return                             new_item;     }
    inline auto remove(Wrapper*item) {
        if (item->prev) item->prev->next = item->next;
        else            first            = item->next;
        if (item->next) item->next->prev = item->prev;
        else            first            = item->prev;   }

    inline auto append(Wrapper*new_item) {
        if (first) {
            return insert_after(last, new_item);
        } else {
            assert(!last);
            first = last = new_item;
            first->prev  = 0;
            first->next  = 0;
            return first;
        }
    }
    inline auto append() {  return append(new Wrapper());  }
    inline auto append(T v) {
        auto ret = append();
        ret->wrapped = v;
        return ret;
    }

    inline ~DLList() {
        Wrapper*p = 0;
        for (auto&a:*this) {
            delete p;
            p= &a;
        }
        delete p;
    }

    struct Iterator {
        Wrapper*i;
        inline bool operator!=(Iterator&other) { return i;  }
        inline void operator++()               { i=i->next; }
        inline Wrapper&operator*()             { return *i; }
    };

    Iterator begin() { return {.i=first}; }
    Iterator end  () { return {.i=last }; }
};

template<typename T> struct DynamicArray:DefaultCtrNoCopy {
    size_t len = 0;
    size_t cap = 0;
    T     *buf = 0;
    inline void cap_set(size_t new_cap)  {
        system_alloc(buf, new_cap);
        cap = new_cap;
    }
    inline T&append() {
        len++;
        if (len > cap) cap_set(MAX(len, cap *2));
        return buf[len-1];
    }
    inline T&append(T v  ) { return append() = v;  }
    T&operator[](size_t i) { return buf[i];        }
    inline ~DynamicArray() { system_alloc(buf, 0); }
    T*begin() { return buf; }
    T*end  () { return buf + len; }
};