import java.util.*;
import java.lang.*;
import java.io.*;
class list<T>
{
node head;
node tail;
public int size;
class node
{
T data;
node next;
node(T d)
{
data=d;
next=null;
}
}
list()
{
head=null;
tail=null;
size=0;
}
public void add_tail(T d)
{
node newnode=new node(d);
if(head==null)
{
head=newnode;
tail=newnode;
}
else
{
tail.next=newnode;
tail=newnode;
}
size++;
}
public void add_head(T d)
{
node newnode=new node(d);
if(head==null)
{
head=newnode;
tail=newnode;
}
else
{
newnode.next=head;
head=newnode;
}
size++;
}
public void add(int p,T d)
{
if(p<0 || p>size)
{
System.
out.
println("wrong position"); return;
}
if (head==null || p==0)
add_head(d);
else if(p==size)
add_tail(d);
else
{
node newnode=new node(d);
node pred=head;
node succ=head;
while(p>0)
{
pred=succ;
succ=succ.next;
p--;
}
pred.next=newnode;
newnode.next=succ;
size++;
}
}
void print()
{
node n=head;
while(n!=null)
{
n=n.next;
}
}
void del_head()
{
node t;
if(tail==head)
{
head=tail=null;
size=0;
}
else
{
t=head;
head=head.next;
t.next=null;
t=null;
size--;
}
}
void del_tail()
{
node t;
if(tail==head)
{
head=tail=null;
size=0;
}
else
{
node pred,succ;
pred=succ=head;
while(succ.next!=null)
{
pred=succ;
succ=succ.next;
}
pred.next=null;
tail=pred;
succ=null;
size--;
}
}
public void del(int p)
{
if(p<0 || p>size-1)
{
System.
out.
println("wrong position"); return;
}
if (p==0)
del_head();
else if(p==size-1)
del_tail();
else
{
node pred=head;
node succ=head;
while(p>0)
{
pred=succ;
succ=succ.next;
p--;
}
pred.next=succ.next;
succ.next=null;
succ=null;
size--;
}
}
}
class Ideone
{
public static void main
(String argv
[]) {
list<Integer> l=new list<Integer>();
l.add_head(1);
l.add_head(2);
l.add_tail(3);
l.add_tail(4);
l.add(2,5);
l.print();
l.del_head();
l.print();
l.del_tail();
l.print();
l.del(2);
l.add(2,7);
l.print();
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CmNsYXNzIGxpc3Q8VD4Kewpub2RlIGhlYWQ7Cm5vZGUgdGFpbDsKcHVibGljIGludCBzaXplOwpjbGFzcyBub2RlCnsKCVQgZGF0YTsKCW5vZGUgbmV4dDsKCSBub2RlKFQgZCkKCXsKCQlkYXRhPWQ7CgkJbmV4dD1udWxsOwoJfQp9CgogbGlzdCgpCnsKCWhlYWQ9bnVsbDsKCXRhaWw9bnVsbDsKCXNpemU9MDsKfQpwdWJsaWMgdm9pZCBhZGRfdGFpbChUIGQpCnsKCW5vZGUgbmV3bm9kZT1uZXcgbm9kZShkKTsKCWlmKGhlYWQ9PW51bGwpCgl7CgkJaGVhZD1uZXdub2RlOwoJCXRhaWw9bmV3bm9kZTsKCX0KCWVsc2UKCXsKCQl0YWlsLm5leHQ9bmV3bm9kZTsKCQl0YWlsPW5ld25vZGU7Cgl9CnNpemUrKzsKfQoKcHVibGljIHZvaWQgYWRkX2hlYWQoVCBkKQp7Cglub2RlIG5ld25vZGU9bmV3IG5vZGUoZCk7CglpZihoZWFkPT1udWxsKQoJewoJCWhlYWQ9bmV3bm9kZTsKCQl0YWlsPW5ld25vZGU7Cgl9CgllbHNlCgl7CgkJbmV3bm9kZS5uZXh0PWhlYWQ7CgkJaGVhZD1uZXdub2RlOwoJfQpzaXplKys7Cn0KCnB1YmxpYyB2b2lkIGFkZChpbnQgcCxUIGQpCnsKCQoJaWYocDwwIHx8IHA+c2l6ZSkgCgl7CgkJU3lzdGVtLm91dC5wcmludGxuKCJ3cm9uZyBwb3NpdGlvbiIpOwoJCXJldHVybjsKCX0KCWlmIChoZWFkPT1udWxsIHx8IHA9PTApCgkgICAgYWRkX2hlYWQoZCk7CgllbHNlIGlmKHA9PXNpemUpCgkJYWRkX3RhaWwoZCk7CgllbHNlCgl7CgkJbm9kZSBuZXdub2RlPW5ldyBub2RlKGQpOwoJCW5vZGUgcHJlZD1oZWFkOwoJCW5vZGUgc3VjYz1oZWFkOwoJCXdoaWxlKHA+MCkKCQl7CgkJCXByZWQ9c3VjYzsKCQkJc3VjYz1zdWNjLm5leHQ7CgkJCXAtLTsKCQl9CgkJcHJlZC5uZXh0PW5ld25vZGU7CgkJbmV3bm9kZS5uZXh0PXN1Y2M7CgkJc2l6ZSsrOwoJfQp9IAp2b2lkIHByaW50KCkKewoJbm9kZSBuPWhlYWQ7Cgl3aGlsZShuIT1udWxsKQoJewoJCVN5c3RlbS5vdXQucHJpbnQobi5kYXRhKyIgIik7CgkJbj1uLm5leHQ7Cgl9ClN5c3RlbS5vdXQucHJpbnRsbigpOwp9Cgp2b2lkIGRlbF9oZWFkKCkKewoJbm9kZSB0OwoJaWYodGFpbD09aGVhZCkKCXsKCQloZWFkPXRhaWw9bnVsbDsKCQlzaXplPTA7Cgl9CgllbHNlCgl7Cgl0PWhlYWQ7CgloZWFkPWhlYWQubmV4dDsKCXQubmV4dD1udWxsOwoJdD1udWxsOwoJc2l6ZS0tOwogICAgfQp9CnZvaWQgZGVsX3RhaWwoKQp7Cglub2RlIHQ7CglpZih0YWlsPT1oZWFkKQoJewoJCWhlYWQ9dGFpbD1udWxsOwoJCXNpemU9MDsKCX0KCWVsc2UKCQl7CgkJbm9kZSBwcmVkLHN1Y2M7CgkJcHJlZD1zdWNjPWhlYWQ7CgkJd2hpbGUoc3VjYy5uZXh0IT1udWxsKQoJCXsKCQkJcHJlZD1zdWNjOwoJCQlzdWNjPXN1Y2MubmV4dDsKCQl9CgkJcHJlZC5uZXh0PW51bGw7CgkJdGFpbD1wcmVkOwoJCXN1Y2M9bnVsbDsKCQlzaXplLS07CgkJCgl9Cn0KcHVibGljIHZvaWQgZGVsKGludCBwKQp7CgkKCWlmKHA8MCB8fCBwPnNpemUtMSkgCgl7CgkJU3lzdGVtLm91dC5wcmludGxuKCJ3cm9uZyBwb3NpdGlvbiIpOwoJCXJldHVybjsKCX0KCWlmIChwPT0wKQoJICAgIGRlbF9oZWFkKCk7CgllbHNlIGlmKHA9PXNpemUtMSkKCQlkZWxfdGFpbCgpOwoJZWxzZQoJewoJCW5vZGUgcHJlZD1oZWFkOwoJCW5vZGUgc3VjYz1oZWFkOwoJCXdoaWxlKHA+MCkKCQl7CgkJCXByZWQ9c3VjYzsKCQkJc3VjYz1zdWNjLm5leHQ7CgkJCXAtLTsKCQl9CgkJcHJlZC5uZXh0PXN1Y2MubmV4dDsKCQlzdWNjLm5leHQ9bnVsbDsKCQlzdWNjPW51bGw7CgkJc2l6ZS0tOwoJfQp9IAp9CgpjbGFzcyBJZGVvbmUKewpwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmcgYXJndltdKQp7CglsaXN0PEludGVnZXI+IGw9bmV3IGxpc3Q8SW50ZWdlcj4oKTsKCWwuYWRkX2hlYWQoMSk7CglsLmFkZF9oZWFkKDIpOwoJbC5hZGRfdGFpbCgzKTsKCWwuYWRkX3RhaWwoNCk7CglsLmFkZCgyLDUpOwoJbC5wcmludCgpOwkKCWwuZGVsX2hlYWQoKTsKCWwucHJpbnQoKTsKCWwuZGVsX3RhaWwoKTsKCWwucHJpbnQoKTsKCWwuZGVsKDIpOwoJbC5hZGQoMiw3KTsKCWwucHJpbnQoKTsKCQp9Cn0K