#include <iostream>
using namespace std;
template < typename T > class Container{
public:
T val;
Container(){}
Container(T _val){
val = _val;
}
};
template < typename T > class Deque{
public:
Container<T>* head;
Container<T>* tail;
Deque< pair<T, T> > *child;
Deque<T>(){}
Deque<T>(Container<T>* _head, Deque< pair<T, T> > *_child, Container<T>* _tail){
head = _head;
child = _child;
tail = _tail;
}
Deque<T>* push_front(T x){
if (this == NULL)
return new Deque<T>(new Container<T>(x), NULL, NULL);
if (head == NULL)
return new Deque<T>(new Container<T>(x), child, tail);
return new Deque<T>(NULL, child->push_front(make_pair(x, head->val)), tail);
}
};
int main(){
Deque<int> d;
int a = 1;
d.push_front(a);
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnRlbXBsYXRlIDwgdHlwZW5hbWUgVCA+IGNsYXNzIENvbnRhaW5lcnsKcHVibGljOgogICAgVCB2YWw7CiAgICBDb250YWluZXIoKXt9CiAgICBDb250YWluZXIoVCBfdmFsKXsKICAgICAgICB2YWwgPSBfdmFsOwogICAgfQp9OwoKdGVtcGxhdGUgPCB0eXBlbmFtZSBUID4gY2xhc3MgRGVxdWV7CnB1YmxpYzoKICAgIENvbnRhaW5lcjxUPiogaGVhZDsKICAgIENvbnRhaW5lcjxUPiogdGFpbDsKICAgIERlcXVlPCBwYWlyPFQsIFQ+ID4gKmNoaWxkOwogICAgRGVxdWU8VD4oKXt9CiAgICBEZXF1ZTxUPihDb250YWluZXI8VD4qIF9oZWFkLCBEZXF1ZTwgcGFpcjxULCBUPiA+ICpfY2hpbGQsIENvbnRhaW5lcjxUPiogX3RhaWwpewogICAgICAgIGhlYWQgPSBfaGVhZDsKICAgICAgICBjaGlsZCA9IF9jaGlsZDsKICAgICAgICB0YWlsID0gX3RhaWw7CiAgICB9CiAgICBEZXF1ZTxUPiogcHVzaF9mcm9udChUIHgpewogICAgICAgIGlmICh0aGlzID09IE5VTEwpCiAgICAgICAgICAgIHJldHVybiBuZXcgRGVxdWU8VD4obmV3IENvbnRhaW5lcjxUPih4KSwgTlVMTCwgTlVMTCk7CiAgICAgICAgaWYgKGhlYWQgPT0gTlVMTCkKICAgICAgICAgICAgcmV0dXJuIG5ldyBEZXF1ZTxUPihuZXcgQ29udGFpbmVyPFQ+KHgpLCBjaGlsZCwgdGFpbCk7CiAgICAgICAgcmV0dXJuIG5ldyBEZXF1ZTxUPihOVUxMLCBjaGlsZC0+cHVzaF9mcm9udChtYWtlX3BhaXIoeCwgaGVhZC0+dmFsKSksIHRhaWwpOwogICAgfQp9OwoKaW50IG1haW4oKXsKICAgIERlcXVlPGludD4gZDsKICAgIGludCBhID0gMTsKICAgIGQucHVzaF9mcm9udChhKTsKfQ==