#include <stdio.h>
// Definitions
typedef M;typedef struct M{int d;M*n;M*p;}Q;typedef struct{Q*f;Q*e;}L;Q*t;x;
// Obtain iterator on first item
Q*F(L**l){return*l?(*l)->f:0;}
// Obtain iterator on last item
Q*E(L**l){return*l?(*l)->e:0;}
// Move iterator to next item
N(Q**t){*t=*t?(*t)->n:0;}
// Move iterator to previous item
P(Q**t){*t=*t?(*t)->p:0;}
// Push Front
A
(L
**l
,int d
){Q
*t
=(Q
*)malloc(sizeof(Q
));t
->d
=d
;if(*l
)(*l
)->f
->p
=t
,t
->n
=(*l
)->f
,(*l
)->f
=t
;else(*l
)=(L
*)malloc(sizeof(L
)),(*l
)->f
=t
,(*l
)->e
=t
;}
// Pop Front
B
(L
**l
){if(*l
)t
=(*l
)->f
,(*l
)->f
=t
->n
,(*l
)->f
->p
=0,x
=t
->d
,free(t
);if(!(*l
)->f
)free(*l
);return x
;}
// Push Back
C
(L
**l
,int d
){t
=(Q
*)malloc(sizeof(Q
));t
->d
=d
;if(*l
)(*l
)->e
->n
=t
,t
->p
=(*l
)->e
,(*l
)->e
=t
;else (*l
)=(L
*)malloc(sizeof(L
)),(*l
)->f
=t
,(*l
)->e
=t
;}
// Pop Back
D
(L
**l
){if(*l
)t
=(*l
)->e
,(*l
)->e
=t
->p
,(*l
)->e
->n
=0,x
=t
->d
,free(t
);if(!(*l
)->e
)free(*l
);return x
;}
main(void){}
I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBEZWZpbml0aW9ucwp0eXBlZGVmIE07dHlwZWRlZiBzdHJ1Y3QgTXtpbnQgZDtNKm47TSpwO31RO3R5cGVkZWYgc3RydWN0e1EqZjtRKmU7fUw7USp0O3g7CgovLyBPYnRhaW4gaXRlcmF0b3Igb24gZmlyc3QgaXRlbQpRKkYoTCoqbCl7cmV0dXJuKmw/KCpsKS0+ZjowO30KCi8vIE9idGFpbiBpdGVyYXRvciBvbiBsYXN0IGl0ZW0KUSpFKEwqKmwpe3JldHVybipsPygqbCktPmU6MDt9CgovLyBNb3ZlIGl0ZXJhdG9yIHRvIG5leHQgaXRlbQpOKFEqKnQpeyp0PSp0PygqdCktPm46MDt9CgovLyBNb3ZlIGl0ZXJhdG9yIHRvIHByZXZpb3VzIGl0ZW0KUChRKip0KXsqdD0qdD8oKnQpLT5wOjA7fQoKLy8gUHVzaCBGcm9udApBKEwqKmwsaW50IGQpe1EqdD0oUSopbWFsbG9jKHNpemVvZihRKSk7dC0+ZD1kO2lmKCpsKSgqbCktPmYtPnA9dCx0LT5uPSgqbCktPmYsKCpsKS0+Zj10O2Vsc2UoKmwpPShMKiltYWxsb2Moc2l6ZW9mKEwpKSwoKmwpLT5mPXQsKCpsKS0+ZT10O30KCi8vIFBvcCBGcm9udApCKEwqKmwpe2lmKCpsKXQ9KCpsKS0+ZiwoKmwpLT5mPXQtPm4sKCpsKS0+Zi0+cD0wLHg9dC0+ZCxmcmVlKHQpO2lmKCEoKmwpLT5mKWZyZWUoKmwpO3JldHVybiB4O30KCi8vIFB1c2ggQmFjawpDKEwqKmwsaW50IGQpe3Q9KFEqKW1hbGxvYyhzaXplb2YoUSkpO3QtPmQ9ZDtpZigqbCkoKmwpLT5lLT5uPXQsdC0+cD0oKmwpLT5lLCgqbCktPmU9dDtlbHNlICgqbCk9KEwqKW1hbGxvYyhzaXplb2YoTCkpLCgqbCktPmY9dCwoKmwpLT5lPXQ7fQoKLy8gUG9wIEJhY2sKRChMKipsKXtpZigqbCl0PSgqbCktPmUsKCpsKS0+ZT10LT5wLCgqbCktPmUtPm49MCx4PXQtPmQsZnJlZSh0KTtpZighKCpsKS0+ZSlmcmVlKCpsKTtyZXR1cm4geDt9CgptYWluKHZvaWQpe30K