template<class T> class Collection {
protected:
	unsigned long count;
public:
	Collection() : count(0) {}

	virtual void clear() = 0;
	virtual void add(const T &val) = 0;
	virtual const bool remove(const T &val) = 0;

	const unsigned long size() const { return count; }
};

template<class T> class Node {
public:
	T val;

	Node(const T &v) : val(v) {}
	virtual ~Node() {}
};

template<class T> class ListNode : public Node < T > {
public:
	ListNode<T> *next, *prev;

	ListNode(const T &v) : Node<T>(v), next(0), prev(0) {}
	virtual ~ListNode() {
		if (next) next->prev = prev;
		if (prev) prev->next = next;
	}
};

template<class T> class LinkedList : public Collection < T > {
protected:
	ListNode<T> *head, *tail;

public:
	class Iterator {
		friend class LinkedList < T > ;
	protected:
		ListNode<T> *n;
		Iterator(ListNode<T> *start) : n(start) {}
	public:
		Iterator(const Iterator &other) : n(other.n) {}

		virtual T &val() { return n->val; }
		virtual void next() { if (n) n = n->next; }
		virtual void prev() { if (n) n = n->prev; }
		virtual const bool has_val() { return (n ? true : false); }
	};

	LinkedList() : Collection<T>(), head(0), tail(0) {};
	LinkedList(const LinkedList<T> &other) : Collection<T>(), head(0), tail(0) {
		for (Iterator i = other.begin(); i.has_val(); i.next())
			add(i.val());
	}
	virtual ~LinkedList() { clear(); }

	LinkedList<T> &operator=(const LinkedList<T> &other)
	{
		clear();
		for (Iterator i = other.begin(); i.has_val(); i.next())
			add(i.val());
		return *this;
	}

	virtual void clear()
	{
		ListNode<T> *n;
		while (head) {
			n = head;
			head = head->next;
			delete n;
		}
		tail = 0;
		Collection<T>::count = 0;
	}

	virtual Iterator begin() const { return Iterator(head); }

	virtual void add_front(T &val) {
		ListNode<T> *n = new ListNode<T>(val);
		n->next = head;
		if (head) head->prev = n;
		head = n;
		if (!tail) tail = n;
		Collection<T>::count++;
	}

	virtual void add(const T &val) {
		ListNode<T> *n = new ListNode<T>(val);
		n->prev = tail;
		if (tail) tail->next = n;
		tail = n;
		if (!head) head = n;
		Collection<T>::count++;
	}

	virtual const bool remove(const T &val) {
		ListNode<T> *n = head;
		while (n) {
			if (n->val == val) {
				if (n == head) head = head->next;
				if (n == tail) tail = tail->prev;

				delete n;
				Collection<T>::count--;
				return true;
			}
			else
				n = n->next;
		}

		return false;
	}

	virtual const bool contains(T &val) const {
		ListNode<T> *n = head;
		while (n) {
			if (n->val == val) {
				return true;
			}
			else
				n = n->next;
		}

		return false;
	}

	// queue/stack functions
	// stack - use push/pop
	// queue - use push_back/pop
	virtual void push(T val) {
		add_front(val);
	}

	virtual void push_back(T &val) {
		add(val);
	}

	virtual const bool pop(T &val) {
		if (!head) return false;

		ListNode<T> *n = head;
		if (head) {
			head = head->next;
			if (n == tail) tail = 0;
			val = n->val;
			delete n;
			Collection<T>::count--;
			return true;
		}
		else
			return false;
	}
};

template<class T> class DynamicArray : public Collection < T > {
protected:
	T *ar;

	unsigned long initial, limit, increment;

public:
	class Iterator {
		friend class DynamicArray < T > ;
	protected:
		T *ar;
		unsigned long count;
		unsigned long pos;
		Iterator(T *a, const int c, unsigned long p) : ar(a), count(c), pos(p) {}
	public:
		Iterator(const Iterator &other) : ar(other.ar), count(other.count), pos(other.pos) {}

		virtual T &val() { return ar[pos]; }
		virtual void next() { pos++; }
		virtual void prev() { pos--; }
		virtual const bool has_val() { return pos < count; }
	};

	DynamicArray(unsigned long init = 0, unsigned long inc = 1) : Collection<T>(), ar(0), initial(init), limit(init), increment(inc) {
		if (limit) ar = (T *)malloc(limit * sizeof(T));
	}
	virtual ~DynamicArray() { if (ar) free(ar); }

	virtual void clear() {
		Collection<T>::count = 0;
		limit = initial;
		if (limit) ar = (T *)realloc(ar, limit * sizeof(T));
		else {
			free(ar);
			ar = 0;
		}
	}

	virtual Iterator begin() const { return Iterator(ar, Collection<T>::count, 0); }

	virtual void add(const T &val) {
		if (Collection<T>::count == limit) {
			limit += increment;
			ar = (T *)realloc(ar, limit * sizeof(T));
			ar[Collection<T>::count++] = val;
		}
		else
			ar[Collection<T>::count++] = val;
	}

	virtual void add_all(DynamicArray<T> &other) {
		for (Iterator i = other.begin(); i != pl.end(); ++i) {
			add(i.val());
		}
	}

	virtual const bool remove(const T &val) {
		for (unsigned long i = 0; i < Collection<T>::count; i++) {
			if (ar[i] == val) {
				memmove(ar + i, ar + i + 1, (Collection<T>::count - i) * sizeof(T));
				Collection<T>::count--;
				return true;
			}
		}
		return false;
	}

	virtual const bool remove(const unsigned long index) {
		if (index >= Collection<T>::count) return false;

		memmove(ar + index, ar + index + 1, (Collection<T>::count - index) * sizeof(T));
		Collection<T>::count--;
		return true;
	}

	virtual const bool insert(const T &val, const unsigned long index) {
		if (index > Collection<T>::count) return false;

		if (Collection<T>::count == limit) {
			limit += increment;
			ar = (T *)realloc(ar, limit * sizeof(T));
		}

		if (index < Collection<T>::count)
			memmove(ar + index + 1, ar + index, (Collection<T>::count - index) * sizeof(T));

		ar[index] = val;
		Collection<T>::count++;
		return true;
	}

	virtual T &operator[](const int index) {
		return ar[index];
	}

	const bool index_of(const T &val, unsigned long &index) const {
		for (int i = 0; i < Collection<T>::count; i++) {
			if (ar[index] == val) {
				index = i;
				return true;
			}
		}
		return false;
	}

	const int index_of(const T &val) const {
		for (int i = 0; i < Collection<T>::count; i++) {
			if (ar[i] == val) {
				return i;
			}
		}
		return -1;
	}

	// stack functions
	virtual const bool pop(T &val) {
		if (Collection<T>::count) {
			val = ar[Collection<T>::count - 1];
			remove(Collection<T>::count - 1);
			return true;
		}
		return false;
	}

	virtual void push(const T &val) {
		add(val);
	}
};

template<class T> class SortedDynamicArray : public DynamicArray < T > {
public:
	SortedDynamicArray(unsigned long init = 0, unsigned long inc = 1) : DynamicArray<T>(init, inc) {}
	virtual ~SortedDynamicArray() {}

	const bool get_index(const T &val, unsigned long &index) {
		unsigned long low = 0;
		unsigned long high = Collection<T>::count - 1;

		while (high < Collection<T>::count && low <= high)
		{
			unsigned long i = (low + high) / 2;
			if (DynamicArray<T>::ar[i] == val)
			{
				index = i;
				return true;
			}
			else
				if (DynamicArray<T>::ar[i] < val)
					low = i + 1;
				else
					high = i - 1;
		}

		index = low;
		return false;
	}

	virtual void add(const T &val) {
		unsigned long index;
		get_index(val, index);
		insert(val, index);
	}
};

template<class T> class TreeNode : public Node < T > {
public:
	TreeNode<T> *parent, *left, *right;

	TreeNode(const T &v, TreeNode<T> *par) : Node<T>(v), parent(par), left(0), right(0) {}
	virtual ~TreeNode() {
		if (parent) {
			if (parent->left == this) parent->left = 0;
			if (parent->right == this)parent->right = 0;
		}
	}
};

template<class T, class N = TreeNode<T> > class BinaryTree : public Collection < T > {
protected:

	N *root;

	virtual void delete_node(N *n) {
		if (n->left && n->right) {
			N *minmax = n->left;
			while (minmax->right) minmax = minmax->right;
			n->val = minmax->val;
			delete_node(minmax);
			return;
		}
		else if (n->right) {
			if (n->parent) {
				if (n->parent->left == n) n->parent->left = n->right;
				else n->parent->right = n->right;
			}
			else
				root = n->right;
			n->right->parent = n->parent;
		}
		else if (n->left) {
			if (n->parent) {
				if (n->parent->left == n)	n->parent->left = n->left;
				else n->parent->right = n->left;
			}
			else
				root = n->left;
			n->left->parent = n->parent;
		}
		else {
			if (n == root) root = 0;
		}
		delete n;
		Collection<T>::count--;
	}

	virtual void insert_node(N *n) {
		N *current = root, *parent = 0;
		while (current) {
			parent = current;
			if (n->val < current->val)
				current = current->left;
			else
				current = current->right;
		}

		if (parent) {
			if (n->val < parent->val) {
				parent->left = n;
			}
			else {
				parent->right = n;
			}
		}
		else
			root = n;

		n->parent = parent;
		Collection<T>::count++;
	}

public:
	class Iterator {
		friend class BinaryTree < T, N > ;
	protected:

		class EvalNode {
		public:
			bool evaluate;
			N *node;

			EvalNode() : evaluate(false), node(0) {}
			EvalNode(const bool eval, N *n) : evaluate(eval), node(n) {}
			const bool operator==(const EvalNode &other) const { return node == other.node; }
			EvalNode &operator=(const EvalNode &other) { evaluate = other.evaluate; node = other.node; return *this; }

		};

		N *n;
		LinkedList<EvalNode> stack;


		Iterator(N *start) : n(0) {
			if (start) {
				stack.push(EvalNode(true, start));
				next();
			}
		}

	public:
		Iterator(const Iterator &other) :n(other.n), stack(other.stack)  {}
		virtual ~Iterator() {}

		virtual T &val() { return n->val; }
		virtual void next() {
			EvalNode en;
			bool popped = false;
			while ((popped = stack.pop(en)) && en.evaluate) {
				if (en.node->right) stack.push(EvalNode(true, en.node->right));
				stack.push(EvalNode(false, en.node));
				if (en.node->left) stack.push(EvalNode(true, en.node->left));
			}

			n = (popped ? en.node : 0);
		}
		virtual const bool has_val() { return (n ? true : false); }
	};

	BinaryTree() : Collection<T>(), root(0) {};
	BinaryTree(BinaryTree<T> &other) : Collection<T>(), root(0) {
		for (Iterator i = other.begin(); i != pl.end(); ++i)
			add(i.val());
	}
	virtual ~BinaryTree() { clear(); }

	BinaryTree &operator=(BinaryTree<T> &other) {
		clear();
		for (Iterator i = other.begin(); i != pl.end(); ++i)
			add(i.val());
		return *this;
	}

	virtual void clear() {
		N *current = root, *parent = 0;
		while (current) {
			if (current->left) current = current->left;
			else if (current->right) current = current->right;
			else {
				parent = current->parent;
				delete current;
				current = parent;
			}
		}

		root = 0;
		Collection<T>::count = 0;
	}

	void add(const T &val) {
		N *n = new N(val, 0);
		insert_node(n);
	}

	const bool remove(const T &val) {
		N *current = root;
		while (current) {
			if (current->val == val)
				break;
			else if (val < current->val)
				current = current->left;
			else
				current = current->right;
		}

		if (current) {
			delete_node(current);
			return true;
		}

		return false;
	}

	const bool contains(const T &val) const {
		N *current = root;
		while (current) {
			if (current->val == val)
				break;
			else if (val < current->val)
				current = current->left;
			else
				current = current->right;
		}

		return current != 0;
	}

	Iterator begin() const { return Iterator(root); }
};

#define RED		1
#define BLACK	0

// thanks to wikipedia (http://en.wikipedia.org/wiki/Red_black_tree)
template<class T> class ColouredTreeNode : public Node < T > {
public:
	ColouredTreeNode<T> *parent, *left, *right;
	char color;

	ColouredTreeNode(const T &v, ColouredTreeNode<T> *par) : Node<T>(v), parent(par), left(0), right(0), color(BLACK) {}
	virtual ~ColouredTreeNode() {
		if (parent) {
			if (parent->left == this) parent->left = 0;
			if (parent->right == this)parent->right = 0;
		}
	}
};

template<class T, class N = ColouredTreeNode<T> > class RedBlackTree : public BinaryTree < T, N > {
protected:
	N *grandparent(N *n) {
		if (n && n->parent)
			return n->parent->parent;
		else
			return NULL;
	}
	N *uncle(N *n) {
		if (grandparent(n)) {
			if (n->parent == grandparent(n)->left)
				return grandparent(n)->right;
			else
				return grandparent(n)->left;
		}
		else
			return NULL;
	}
	N *sibling(N *n) {
		if (n->parent) {
			if (n == n->parent->left)
				return n->parent->right;
			else
				return n->parent->left;
		}
		else
			return NULL;
	}
	bool is_leaf(N *n) {
		return n == 0;
	}

	void replace_node(N *o, N *n) {
		n->parent = o->parent;
		if (n->parent) {
			if (n->parent->left == o) n->parent->left = n;
			else if (n->parent->right == o) n->parent->right = n;
		}
		else
			BinaryTree<T, N>::root = n;
	}

	void rotate_left(N *n) {
		N *p = n->right;
		N *q = n;

		q->right = p->left;
		if (q->right) q->right->parent = q;
		p->left = q;
		p->parent = q->parent;
		q->parent = p;
		if (p->parent) {
			if (p->parent->left == q) p->parent->left = p;
			else if (p->parent->right == q) p->parent->right = p;
		}
		else
			BinaryTree<T, N>::root = p;
	}
	void rotate_right(N *n) {
		N *p = n->left;
		N *q = n;

		q->left = p->right;
		if (q->left) q->left->parent = q;
		p->right = q;
		p->parent = q->parent;
		q->parent = p;
		if (p->parent) {
			if (p->parent->left == q) p->parent->left = p;
			else if (p->parent->right == q) p->parent->right = p;
		}
		else
			BinaryTree<T, N>::root = p;
	}

	void insert_case1(N *n) {
		if (n->parent == NULL)
			n->color = BLACK;
		else
			insert_case2(n);
	}
	void insert_case2(N *n) {
		if (n->parent->color == BLACK)
			return; /* Tree is still valid */
		else
			insert_case3(n);
	}
	void insert_case3(N *n) {
		if (uncle(n) != NULL && uncle(n)->color == RED) {
			n->parent->color = BLACK;
			uncle(n)->color = BLACK;
			grandparent(n)->color = RED;
			insert_case1(grandparent(n));
		}
		else
			insert_case4(n);
	}
	void insert_case4(N *n) {
		if (n == n->parent->right && n->parent == grandparent(n)->left) {
			rotate_left(n->parent);
			n = n->left;
		}
		else if (n == n->parent->left && n->parent == grandparent(n)->right) {
			rotate_right(n->parent);
			n = n->right;
		}
		insert_case5(n);
	}
	void insert_case5(N *n) {
		n->parent->color = BLACK;
		grandparent(n)->color = RED;
		if (n == n->parent->left && n->parent == grandparent(n)->left) {
			rotate_right(grandparent(n));
		}
		else {
			/* Here, n == n->parent->right && n->parent == grandparent(n)->right */
			rotate_left(grandparent(n));
		}
	}

	void delete_case0(N *n) {
		/* Precondition: n has at most one non-null child */
		N *child = is_leaf(n->right) ? n->left : n->right;
		if (child) replace_node(n, child);
		if (n->color == BLACK) {
			if (child) {
				if (child->color == RED)
					child->color = BLACK;
				else
					delete_case1(child);
			}
			else
				delete_case1(n);
		}
		if (BinaryTree<T, N>::root == n) BinaryTree<T, N>::root = 0;
		delete n;
		Collection<T>::count--;
	}
	void delete_case1(N *n) {
		if (n->parent == NULL)
			return;
		else
			delete_case2(n);
	}
	void delete_case2(N *n) {
		if (sibling(n) && sibling(n)->color == RED) {
			n->parent->color = RED;
			sibling(n)->color = BLACK;
			if (n == n->parent->left)
				rotate_left(n->parent);
			else
				rotate_right(n->parent);
		}
		delete_case3(n);
	}
	void delete_case3(N *n) {
		if (n->parent->color == BLACK &&
			sibling(n) &&
			sibling(n)->color == BLACK &&
			(sibling(n)->left == 0 || sibling(n)->left->color == BLACK) &&
			(sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
		{
			sibling(n)->color = RED;
			delete_case1(n->parent);
		}
		else
			delete_case4(n);
	}
	void delete_case4(N *n) {
		if (n->parent->color == RED &&
			sibling(n) &&
			sibling(n)->color == BLACK &&
			(sibling(n)->left == 0 || sibling(n)->left->color == BLACK) &&
			(sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
		{
			sibling(n)->color = RED;
			n->parent->color = BLACK;
		}
		else
			delete_case5(n);
	}
	void delete_case5(N *n) {
		if (n == n->parent->left &&
			sibling(n) &&
			sibling(n)->color == BLACK &&
			sibling(n)->left &&
			sibling(n)->left->color == RED &&
			(sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
		{
			sibling(n)->color = RED;
			sibling(n)->left->color = BLACK;
			rotate_right(sibling(n));
		}
		else if (n == n->parent->right &&
			sibling(n) &&
			sibling(n)->color == BLACK &&
			sibling(n)->right &&
			sibling(n)->right->color == RED &&
			(sibling(n)->left == 0 || sibling(n)->left->color == BLACK))
		{
			sibling(n)->color = RED;
			sibling(n)->right->color = BLACK;
			rotate_left(sibling(n));
		}
		delete_case6(n);
	}
	void delete_case6(N *n) {
		sibling(n)->color = n->parent->color;
		n->parent->color = BLACK;
		if (n == n->parent->left) {
			/* Here, sibling(n)->right->color == RED */
			sibling(n)->right->color = BLACK;
			rotate_left(n->parent);
		}
		else {
			/* Here, sibling(n)->left->color == RED */
			sibling(n)->left->color = BLACK;
			rotate_right(n->parent);
		}
	}

	N *get_predecessor(N *n) {
		N *minmax = n->left;
		while (minmax->right) minmax = minmax->right;
		return minmax;
	}

	virtual void insert_node(N *n) {
		BinaryTree<T, N>::insert_node(n);
		n->color = RED;

		insert_case1(n);
	}

	virtual void delete_node(N *n) {
		if (n->left && n->right) {
			N *predecessor = get_predecessor(n);
			n->val = predecessor->val;
			delete_case0(predecessor);
		}
		else
			delete_case0(n);
	}

public:
	RedBlackTree() : BinaryTree< T, N >() {}
	virtual ~RedBlackTree() {}
};

template<class A, class B> class Pair {
public:
	A first;
	B second;

	Pair(const A &f) : first(f) {}
	Pair(const A &f, const B &s) : first(f), second(s) {}
	Pair(const Pair<A, B> &other) : first(other.first), second(other.second) {}
	virtual ~Pair() {}

	const bool operator<(const Pair<A, B> &other) const { return first < other.first; }
	const bool operator==(const Pair<A, B> &other) const { return first == other.first; }
	Pair<A, B> &operator=(const Pair<A, B> &other) { first = other.first; second = other.second; return *this; }
};

//template<class A, class B, class N = TreeNode<Pair<A, B> > > class Map: public BinaryTree< Pair< A, B >, N > {
template<class A, class B, class N = ColouredTreeNode<Pair<A, B> > > class Map : public RedBlackTree < Pair< A, B >, N > {
protected:

	N *find(A &key) const {
		N *n = RedBlackTree< Pair< A, B >, N >::root;
		while (n) {
			if (n->val.first == key)
				return n;
			else if (key < n->val.first)
				n = n->left;
			else
				n = n->right;

		}
		return 0;
	}
public:
	//Map(): BinaryTree< Pair<A,B>, N >() {}
	Map() : RedBlackTree< Pair<A, B>, N >() {}
	virtual ~Map() {}

	void put(A &key, B &value) {
		add(Pair<A, B>(key, value));
	}

	const bool get(A &key, B &val) const {
		const N *n = find(key);
		if (n) {
			val = n->val.second;
			return true;
		}
		else
			return false;
	}

	B &operator[](A &key) {
		N *n = find(key);
		if (n)
			return n->val.second;
		else {
			Pair< A, B > p(key);
			N *n = new N(p, 0);
			insert_node(n);
			return n->val.second;
		}
	}

	virtual const bool exists(A &key) const {
		const N *n = find(key);
		if (n) {
			return true;
		}
		else
			return false;
	}

	virtual const bool remove(A &key) {
		N *n = find(key);
		if (n) {
			delete_node(n);
			return true;
		}
		else
			return false;
	}
};