import java.io.* ;
class element< T>
{
protected element< T> prev, next;
protected T val;
public element( )
{
prev = null ;
next = null ;
}
public element( T x )
{
prev = null ;
next = null ;
val = x;
}
}
class list< T> implements java.util .Collection < T>
{
private element< T> front, back;
private int size;
public list( )
{
front = new element<> ( ) ;
back = new element<> ( ) ;
size = 0 ;
front.prev = back;
back.next = front;
}
public void AddFront( T x )
{
front.val = x;
front.next = new element<> ( ) ;
front.next .prev = front;
front = front.next ;
size ++;
}
public T RemoveFront( )
{
front.prev .next = null ;
front = front.prev ;
size --;
return front.val ;
}
public void AddBack( T x )
{
back.val = x;
back.prev = new element<> ( ) ;
back.prev .next = back;
back = back.prev ;
size ++;
}
public T RemoveBack( )
{
back.next .prev = null ;
back = back.next ;
size --;
return back.val ;
}
public int size( )
{
return size;
}
public boolean add( T x)
{
AddFront( x ) ;
}
public void clear( )
{
front = new element<> ( ) ;
back = new element<> ( ) ;
size = 0 ;
front.prev = back;
back.next = front;
}
}
class testowanie
{
public static void main
( String [ ] args
) {
list< String> x = new list< String> ( ) ;
x.AddFront ( "s" ) ;
x.AddFront ( "i" ) ;
x.AddBack ( "a" ) ;
x.AddBack ( "b" ) ;
x.AddBack ( "c" ) ;
x.AddBack ( "d" ) ;
}
}
aW1wb3J0IGphdmEuaW8uKjsKCmNsYXNzIGVsZW1lbnQ8VD4KewoJcHJvdGVjdGVkIGVsZW1lbnQ8VD4gcHJldiwgbmV4dDsKCXByb3RlY3RlZCBUIHZhbDsKCglwdWJsaWMgZWxlbWVudCgpCgl7CgkJcHJldiA9IG51bGw7CgkJbmV4dCA9IG51bGw7Cgl9CgoJcHVibGljIGVsZW1lbnQoIFQgeCApCgl7CgkJcHJldiA9IG51bGw7CgkJbmV4dCA9IG51bGw7CgkJdmFsID0geDsKCX0KfQoKY2xhc3MgbGlzdDxUPiBpbXBsZW1lbnRzIGphdmEudXRpbC5Db2xsZWN0aW9uPFQ+CnsKCXByaXZhdGUgZWxlbWVudDxUPiBmcm9udCwgYmFjazsKCXByaXZhdGUgaW50IHNpemU7CgoJcHVibGljIGxpc3QoKQoJewoJCWZyb250ID0gbmV3IGVsZW1lbnQ8PigpOwoJCWJhY2sgPSBuZXcgZWxlbWVudDw+KCk7CgkJc2l6ZSA9IDA7CgoJCWZyb250LnByZXYgPSBiYWNrOwoJCWJhY2submV4dCA9IGZyb250OwoJfQoKCXB1YmxpYyB2b2lkIEFkZEZyb250KCBUIHggKQoJewoJCWZyb250LnZhbCA9IHg7CgkJZnJvbnQubmV4dCA9IG5ldyBlbGVtZW50PD4oKTsKCQlmcm9udC5uZXh0LnByZXYgPSBmcm9udDsKCQlmcm9udCA9IGZyb250Lm5leHQ7CgkJc2l6ZSArKzsKCX0KCglwdWJsaWMgVCBSZW1vdmVGcm9udCgpCgl7CgkJZnJvbnQucHJldi5uZXh0ID0gbnVsbDsKCQlmcm9udCA9IGZyb250LnByZXY7CgkJc2l6ZSAtLTsKCQlyZXR1cm4gZnJvbnQudmFsOwoJfQoKCXB1YmxpYyB2b2lkIEFkZEJhY2soIFQgeCApCgl7CgkJYmFjay52YWwgPSB4OwoJCWJhY2sucHJldiA9IG5ldyBlbGVtZW50PD4oKTsKCQliYWNrLnByZXYubmV4dCA9IGJhY2s7CgkJYmFjayA9IGJhY2sucHJldjsKCQlzaXplICsrOwoJfQoKCXB1YmxpYyBUIFJlbW92ZUJhY2soKQoJewoJCWJhY2submV4dC5wcmV2ID0gbnVsbDsKCQliYWNrID0gYmFjay5uZXh0OwoJCXNpemUgLS07CgkJcmV0dXJuIGJhY2sudmFsOwoJfQoKCXB1YmxpYyBpbnQgc2l6ZSgpCgl7CgkJcmV0dXJuIHNpemU7Cgl9CgkKCXB1YmxpYyBib29sZWFuIGFkZChUIHgpCgl7CgkJQWRkRnJvbnQoIHggKTsKCX0KCQoJcHVibGljIHZvaWQgY2xlYXIoKQoJewoJCWZyb250ID0gbmV3IGVsZW1lbnQ8PigpOwoJCWJhY2sgPSBuZXcgZWxlbWVudDw+KCk7CgkJc2l6ZSA9IDA7CgoJCWZyb250LnByZXYgPSBiYWNrOwoJCWJhY2submV4dCA9IGZyb250OwoJfQp9CgpjbGFzcyB0ZXN0b3dhbmllCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpCgl7CgkJbGlzdDxTdHJpbmc+IHggPSBuZXcgbGlzdDxTdHJpbmc+KCk7CgoJCXguQWRkRnJvbnQoICJzIiApOwoJCXguQWRkRnJvbnQoICJpIiApOwoJCXguQWRkQmFjayggImEiICk7CgkJeC5BZGRCYWNrKCAiYiIgKTsKCQl4LkFkZEJhY2soICJjIiApOwoJCXguQWRkQmFjayggImQiICk7Cgl9Cn0=