#include <iostream>
#include <cstdlib>
#include <ctime>

template<class T>
class DoublyLinkedList
{
private:
	class Link
	{
	public:
		T data;
		Link* next;
		Link* previous;

		Link(T data, Link* next = nullptr, Link* previous = nullptr);
	};
private:
	Link* first;
	Link* last;
public:
	DoublyLinkedList();
	~DoublyLinkedList();

	bool isEmpty();
	void insertFirst(T dd);
	void insertLast(T dd);
	void deleteFirst();
	void deleteLast();
	bool insertAfter(T key, T dd);
	void deleteKey(T key);
	void displayForward();
	void displayBackward();
	void BSTinsert(Link*& root, Link* z);
	void BSTtoDLL(Link* root, DoublyLinkedList<T> &L);
	void BSTSort();
private:
	Link* find(T key);
};


template<class T>
DoublyLinkedList<T>::Link::Link(T data, Link* next, Link* previous)
	: data(data), next(next), previous(previous)
{
}


template<class T>
DoublyLinkedList<T>::DoublyLinkedList()
	: first(nullptr), last(nullptr)
{
}

template<class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
	while (!isEmpty())
	{
		deleteFirst();
	}
}

template<class T>
bool DoublyLinkedList<T>::isEmpty()
{
	return first == nullptr;
}

template<class T>
void DoublyLinkedList<T>::insertFirst(T dd)
{
	Link* newLink = new Link(dd);
	if (isEmpty())
		last = newLink;
	else
		first->previous = newLink;
	newLink->next = first;
	first = newLink;
}

template<class T>
void DoublyLinkedList<T>::insertLast(T dd)
{
	Link* newLink = new Link(dd);
	if (isEmpty())
		first = newLink;
	else
		last->next = newLink;
	newLink->previous = last;
	last = newLink;
}

template<class T>
void DoublyLinkedList<T>::deleteFirst()
{
	if (isEmpty())
		return;
	Link* temp = first;
	if (first->next == nullptr)
		last = nullptr;
	else
		first->next->previous = nullptr;
	first = first->next;
	delete temp;
}

template<class T>
void DoublyLinkedList<T>::deleteLast()
{
	if (isEmpty())
		return;
	Link* temp = last;
	if (first->next == nullptr)
		first = nullptr;
	else
		last->previous->next = nullptr;
	last = last->previous;
	delete temp;
}

template<class T>
bool DoublyLinkedList<T>::insertAfter(T key, T dd)
{
	Link* current = find(key);
	if (current == nullptr)
		return false;
	Link* newLink = new Link(dd);
	if (current->next == nullptr)
	{
		newLink->next = nullptr;
		last = newLink;
	}
	else
	{
		newLink->next = current->next;
		current->next->previous = newLink;
	}
	newLink->previous = current;
	current->next = newLink;
	return true;
}

template<class T>
void DoublyLinkedList<T>::deleteKey(T key)
{
	Link* current = find(key);
	if (current == nullptr)
		return;
	if (current->previous == nullptr)
		first = current->next;
	else
		current->previous->next = current->next;
	if (current->next == nullptr)
		last = current->previous;
	else
		current->next->previous = current->previous;
	delete current;
}

template<class T>
void DoublyLinkedList<T>::displayForward()
{
	std::cout << "List (first-->last): ";
	Link* current = first;
	while (current != nullptr)
	{
		std::cout << current->data << " ";
		current = current->next;
	}
	std::cout << std::endl;
}

template<class T>
void DoublyLinkedList<T>::displayBackward()
{
	std::cout << "List (last-->first): ";
	Link* current = last;
	while (current != nullptr)
	{
		std::cout << current->data << " ";
		current = current->previous;
	}
	std::cout << std::endl;
}

template<class T>
void DoublyLinkedList<T>::BSTinsert(Link* &root, Link* z)
{
	Link* y = nullptr;
	Link* x = root;
	while (x != nullptr)
	{
		y = x;
		if (z->data < x->data)
			x = x->previous;
		else
			x = x->next;
	}
	if (y == nullptr)
		root = z;
	else if (z->data < y->data)
		y->previous = z;
	else
		y->next = z;
}

template<class T>
void DoublyLinkedList<T>::BSTtoDLL(Link* root, DoublyLinkedList<T> &L)
{
	if (root != nullptr)
	{
		BSTtoDLL(root->previous, L);
		if (L.isEmpty())
			L.first = root;
		else
			L.last->next = root;
		root->previous = L.last;
		L.last = root;
		BSTtoDLL(root->next, L);
	}
}

template<class T>
typename DoublyLinkedList<T>::Link* DoublyLinkedList<T>::find(T key)
{
	Link* current = first;
	while (current != nullptr && !(current->data == key))
		current = current->next;
	return current;
}

template<class T>
void DoublyLinkedList<T>::BSTSort()
{
	Link* temp;
	Link* root = nullptr;
	while (!isEmpty())
	{
		temp = first;
		if (first->next == nullptr)
			last = nullptr;
		else
			first->next->previous = nullptr;
		first = first->next;
		temp->previous = nullptr;
		temp->next = nullptr;
		BSTinsert(root, temp);
	}
	BSTtoDLL(root, *this);
}

int main(int argc, char *argv[])
{
	DoublyLinkedList<int> A;
	int k, n, m;
	srand(time(nullptr));
	std::cin >> n >> m;
	for (k = 0; k < n; k++)
		A.insertLast(rand() % m);
	A.displayForward();
	A.displayBackward();
	A.BSTSort();
	A.displayForward();
	A.displayBackward();
	while (!A.isEmpty())
		A.deleteFirst();
	return EXIT_SUCCESS;
}