/*#include<stdio.h>
#include<string.h>
int stack[100100]={};
int top=-1;
void push(int k)
{
stack[++top]=k;
}
void pop()
{
stack[top--];
}
int main()
{
char str[100100]={};
int c=0,len;
scanf("%s",str);
len=strlen(str);
for(int i=0;i<len;i++)
{
if(str[i]=='(') push(str[i]);
else
{
if(str[i-1]=='(')
{
pop();
c+=top+1;
}
else
{
c+=1;
pop();
}
}
}
printf("%d",c);
return 0;
}*//*
#include<stdio.h>
int memo[300]={};
int fib(int k)
{
if(memo[k]!=0) return memo[k];
if(k==1 || k==2) return memo[k]=1;
return memo[k]=(fib(k-1)+fib(k-2))%10009;
}
int main()
{
int N;
scanf("%d",&N);
printf("%d",fib(N));
}*//*
#include<stdio.h>
int arr[60][60]={},i,j;
int memo[60][60]={};
int rec(int a, int b)
{
if(a==0||b==0) return memo[a][b]=1;
if(memo[a][b]!=0) return memo[a][b];
return memo[a][b]=(rec(a-1,b)+rec(a,b-1))%100000000;
}
int main()
{
int r,c;
scanf("%d %d",&r,&c);
printf("%d",rec(r-1,c-1));
}*//*
#include<stdio.h>
int memo[20][20]={};
int SuperSum(int a,int b)
{
if(a==0) return memo[a][b]=b;
if(memo[a][b]!=0) return memo[a][b];
for(int i=0;i<b;i++)
{
memo[a][b]+=SuperSum(a-1,b-i);
}
return memo[a][b];
}
int main()
{
int k,n;
while( scanf("%d %d", &k, &n) != EOF )
printf("%d\n", SuperSum(k, n));
}*/
//basic linked list
/*
#include<stdio.h>
typedef struct node
{
int data;
struct node* link;
}bn;
void view(bn* st)
{
bn* p=st;
printf("\n---------------------------\nLIST : ");
while(p!=NULL)
{
printf("%d -> ",p->data);
p=p->link;
}
printf("NULL \n");
}
int main()
{
struct node n1,n2,n3,n4,insertn;
//node 생성
n1.link=&n2;
n2.link=&n3;
n3.link=&n4;
n4.link=NULL;
n1.data=1;
n2.data=10;
n3.data=100;
n4.data=1000;
view(&n1);
//n2 다음에 insertn 삽입하기
insertn.data=50;
insertn.link=n2.link;
n2.link=&insertn;
printf("\ninsert\n");
view(&n1);
//n2다음노드 삭제하기
n2.link=n2.link->link;
printf("\ndelete\n");
view(&n1);
}
*/
//double linked list
#include<stdio.h>
typedef struct dnode
{
int data;
struct dnode* next;
struct dnode* prev;
}dnode;
void view(dnode* st)
{
dnode* p=st;
printf("\n---------------------------\nLIST : ");
while(p!=NULL)
{
printf("%d -> ",p->data);
p=p->next;
}
printf("NULL \n");
}
void insertnode()
{
}
void deletenode()
{
}
int main()
{
struct dnode n1,n2,n3,n4,insertn;
n1.next=&n2;
n2.next=&n3;
n3.next=&n4;
n4.next=NULL;
n4.prev=&n3;
n3.prev=&n2;
n2.prev=&n1;
n1.data=1;
n2.data=10;
n3.data=100;
n4.data=1000;
//n2뒤에 노드 삽입
insertn.data=50;
insertn.next=n2.next;
n2.next->prev=&insertn;
n2.next=&insertn;
insertn.prev=&n2;
view(&n1);
//n2뒤에 노드 삭제
n2.next=n2.next->next;
n2.next->prev=&n2;
view(&n1);
}