class K:Node{
    int value;
    Optional<SimpleRc<K:Node>> next;
    Optional<SimpleRc<K:Node>> prev;
    Node(int value){
        this.value = value;
        next = Optional<SimpleRc<K:Node>>();
        prev = Optional<SimpleRc<K:Node>>();
    }
    void SetNext(Optional<SimpleRc<K:Node>> x) mut{
        drop next;
        next = x;
    }
    void SetPrev(Optional<SimpleRc<K:Node>> x) mut{
        drop prev;
        prev = x;
    }
    void FreeNextPrev() mut{
        Optional<SimpleRc<K:Node>> temp_next = next.take();
        if(temp_next.present()){
            &K:Node node = temp_next.ref().ref();
            node.SetPrev(Optional<SimpleRc<K:Node>>());//we can convert to a mut by borrowing K
            drop next;
            drop node;
            next = temp_next.take();
        }
        drop temp_next;
    }
}
class K:List{
    Optional<SimpleRc<K:Node>> head;
    Optional<SimpleRc<K:Node>> tail;
    List(){
        head = Optional<SimpleRc<K:Node>>();
        tail = Optional<SimpleRc<K:Node>>();
    }
    void push(int x) mut{
        SimpleRc<K:Node> node = SimpleRc<K:Node>(Node(x));
        Optional<SimpleRc<K:Node>> old_head = head.take();
        if(old_head.present()){
            &K:Node inner = old_head.ref().ref();
            SimpleRc<K:Node> node_copy = node.copy();
            inner.SetPrev(Optional<SimpleRc<K:Node>>(node_copy));//back pointer for old head
            drop inner;
        }
        else{
            drop tail;
            tail = Optional<SimpleRc<K:Node>>(node.copy());
        }
        &K:Node n = node.ref();
        n.SetNext(old_head);
        drop n;
        drop head;
        head = Optional<SimpleRc<K:Node>>(node);
    }
    void push_back(int x) mut{
        SimpleRc<K:Node> node = SimpleRc<K:Node>(Node(x));
        Optional<SimpleRc<K:Node>> old_tail = tail.take();
        if(old_tail.present()){
            &K:Node inner = old_tail.ref().ref();
            inner.SetNext(Optional<SimpleRc<K:Node>>(node.copy()));//forward pointer for old tail
            drop inner;
        }
        else{
            drop head;
            head = Optional<SimpleRc<K:Node>>(node.copy());
        }
        &K:Node n = node.ref();
        n.SetPrev(old_tail);//moves out tail
        drop n;
        drop tail;
        tail = Optional<SimpleRc<K:Node>>(node);
    }
    Optional<int> pop() mut{
        Optional<SimpleRc<K:Node>> old_head = head.take();
        if(old_head.present()){
            SimpleRc<K:Node> node = old_head.into_inner();
            &K:Node n = node.ref(); // we can convert to a mut by borrowing K
            mut &Node n_mut = n;
            old_head = n_mut.next.take();

            int val = n_mut.value;
            drop n_mut; //returns K, which we need
            drop head;
            head = old_head;

            if(head.present()){

            }
            else{
                Optional<SimpleRc<K:Node>> x = tail.take();
                drop x;
            }
            
            drop n;
            drop node;
            return Optional<int>(val);
        }
        else{
            drop old_head;
            return Optional<int>();
        }
    }
}