class Solution {
 	  public static class Node {
	    // Each node object has these three variables
	    private Object element;
	    private Node   next;
	    private Node   previous;

	    // Constructor: Creates a Node object with element = e, next = n and previous = p
	    Node(Object e, Node n, Node p) {
	      element = e;
	      next    = n;
	      previous = p;
	    }

	    // This function gets Object e as input and sets e as the element of the Node
	    public void setElement(Object e) {
	      element = e;
	    }

	    // This function returns the element variable of the Node
	    public Object getElement() {
	      return element;
	    }

	    // This function gets Node n as input and sets the next variable of the current Node object as n.
	    public void setNext(Node n) {
	      next = n;
	    }

	    // This function returns the next Node
	    public Node getNext() {
	      return next;
	    }

	    // This function gets Node n as input and sets the previous variable of the current Node object as p.
	    public void setPrevious(Node p) {
	      previous = p;
	    }

	    // This function returns the previous Node
	    public Node getPrevious() {
	      return previous;
	    }

	  }

	  public static class DLList {

	    // Each object in DLList has one variable head, which points to the starting Node of DLList.
	    private Node head;
	    private Node tail;

	    // Implemens an empty constructor which initialises the head variable as null
	    DLList() {
	      head = null;
	      tail = null;
	    }

	    // Returns the head node of the DLL
	    public Node getHead() {
	      return head;
	    }



	    // Returns the tail node of the DLL
	    public Node getTail() {
	    	return tail;
	    }

	    // Following methods are the ones you are expected to implement

	    // Adds node n to the head of the list.
	    public void addFirst(Node n) {
	      if(head == null) {
	    		n.setNext(null);
	    		n.setPrevious(null);

	    		head = n;
	    		tail = n;
	    	} else {
	     		  n.setNext(head);
	     		  n.setPrevious(null);
	    		  head.setPrevious(n);
	    	  	head = n;
	    	  }
	    }

	    //Removes and returns the first node in the list. If the list is empty, returns null.
	    public Node removeFirst() {
	      Node temp = null;

	    	if(head == null) {
	    		return temp;
	    	}

	    	if(size() == 1) {
	    		temp = head;
	    		head = null;
	    		tail = null;
	    		return temp;
	    	}

	    	temp = head;
	    	head = head.getNext();
	    	head.setPrevious(null);

	    	return temp;

    }

	    // Adds node n to the end of the list
	    public void addLast(Node n) {
	        if(tail != null) {
	          n.setPrevious(tail);
	          n.setNext(null);
	          tail.setNext(n);
	          tail = n;
	        } else {
	          n.setNext(null);
	          n.setPrevious(null);

	          tail = n;
	          head = n;
	        }


	    }

	    //Removes and returns the last node in the list.If the list is empty, returns null.
	    public Node removeLast() {
	      Node temp = null;

	    	if(head == null) {
	    		return temp;
	    	}

	    	if(size() == 0) {
	    		temp = head;
	    		tail = null;
	    		head = null;
	    		return temp;
	    	}

	    	temp = tail;
  	    	tail = tail.getPrevious();
  	    	//tail.setPrevious(tail.getPrevious());
  	    	tail.setNext(null);

	    	return temp;

	    }

	    // Returns the number of nodes in the list
	    public int size() {
	      int counter = 1;

	      if(head == null) {
	    		return 0;
	    	}

	    	for(Node n = head; n.getNext() != null; n = n.getNext()) {
	    		counter++;
	    	}

	    	return counter;
	    }

	    // Adds node n after the node in position pos. The list is zero indexed, so the first element in the list correspond
	    // to position 0. If there is no node in position pos, this method adds it to the last position.
	    public void addAtPosition(Node n, int pos) {
	      Node temp = head;

	    	if(size()-1 <= pos) {
	    		addLast(n);
	    		return;
	    	}

	    	for(int i = 0; i < pos; i++) {
	    		temp = temp.getNext();
	    	}

	    	n.setPrevious(temp);
	    	n.setNext(temp.getNext());

	    	temp.getNext().setPrevious(n);
	    	temp.setNext(n);
	    }

	    // Remove and return node n at position pos. The list is zero indexed, so the first element in the list correspond
	    // to position 0. If there is no node in position pos, this method returns null.
	    public Node removeFromPosition(int pos) {

	     	Node temp = this.getHead();

	    	//if the list is empty
	    	if (temp == null) {
	    		return null;
	    	}

	      //if the pos is not in the list
	    	if(size() <= pos ) {
	    	  return null;
	    	}

	    	//if pos is head
	    	if(pos == 0) {
	    		removeFirst();
	    		return temp;
	    	}

	    		//if pos is tail
	    	if(temp.getNext() == null) {
          temp = this.getTail();
          removeLast();
	    	  return temp;
	    	}

	    	//find the node to be removed
	    	for(int i=0; i < pos; i++) {
	    		temp = temp.getNext();
	    	}

	    	temp.getPrevious().setNext(temp.getNext());
	    	temp.getNext().setPrevious(temp.getPrevious());

	    	return temp;
	    }

	    // Returns  a new DLL that contains the elements of the current one in reversed order
	    public DLList reverse() {
	    	DLList reversed = new DLList();
	    	Node next = this.getTail();
	    	while(next!=null){
				Node temp = new Node(next.getElement(),null,null);
				//System.out.println("next" + next.getElement());
				reversed.addLast(temp);
				next = next.getPrevious();
			}
	      return reversed;
	    }

	}
}