/*
#include <stdio.h>
#include <string.h>
#include <windows.h>
#include <math.h>
#define MAX 1000
int numstack[1000];
int stack[1000];
char charstack[1000];
char equation[1000];
int numtop=0;
int chartop=0;
int top=0;
void convert();
void calculator();
void convert()
{
int i;
for(i=0;i<strlen(equation);i++)
{
//printf("------------------------------------------\n");
if(equation[i]>=48&&equation[i]<=57)
{
int temp=0;
while(equation[i]>=48&&equation[i]<=57)
{
stack[top++]=equation[i]-'0';
i++;
}
int cnt=0;
while(top>0)
{
temp+=(stack[top-1])*pow(10.0, cnt);
top--;
}
numstack[numtop++]=temp;
}
if(equation[i]<48||equation[i]>57)
{
if(equation[i]==')'||equation[i]=='}'||equation[i]==']')
calculator();
else
charstack[chartop++]=equation[i];
}
}
calculator();
}
void calculator()//괄호 계산은 1번 , 그냥 계산은 0번
{
while(chartop>0)
{
int x, y;
int temp;
x=numstack[numtop-2];
y=numstack[numtop-1];
if(charstack[chartop-1]=='('||charstack[chartop-1]=='{'||charstack[chartop-1]=='[')
{
chartop--;
return;
}
if(charstack[chartop-1]=='+')
{
temp=x+y;
numtop=numtop-2;
numstack[numtop++]=temp;
}
else if(charstack[chartop-1]=='-')
{
temp=x-y;
numtop=numtop-2;
numstack[numtop++]=temp;
}
else if(charstack[chartop-1]=='*')
{
temp=x*y;
numtop=numtop-2;
numstack[numtop++]=temp;
}
else if(charstack[chartop-1]=='/')
{
temp=x/y;
numtop=numtop-2;
numstack[numtop++]=temp;
}
chartop--;
}
}
int main()
{
scanf("%s", equation);
// printf("%s\n", equation);
convert();
printf("%d\n", numstack[numtop-1]);
return 0;
}
*/
/*
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <string.h>
typedef struct node
{
int data;
node *rlink;
node *llink;
}node;
node* queue[1000];
int front=0;
int rear=0;
int heap[];
node *start;
node *current;
node *before;
//int nodes=1;
void MAXheap();
void deletemax();
void menu();
void print();
void MAXheap()
{
printf("---------------------------------------------------\n");
int num;
printf("please enter a integer you want to insert.\n");
scanf("%d", &num);
while(num<=0)
{
printf("please enter a integer.\n");
scanf("%d", &num);
}
if(start->data==0)
{
start->data=num;
printf("insert complete.\n");
printf("---------------------------------------------------\n");
return;
}
node *newnode;
newnode=(node*)malloc(sizeof(node));
//newnode->index=nodes++;
newnode->llink=NULL;
newnode->rlink=NULL;
newnode->data=num;
if(current->llink==NULL)
current->llink=newnode;
else
current->rlink=newnode;
//비교
if(current->data<newnode->data)
{
int temp;
temp=current->data;
current->data=newnode->data;
newnode->data=temp;
}
before=current;
current=newnode;
printf("insert complete.\n");
printf("---------------------------------------------------\n");
}
void deletemax()
{
printf("---------------------------------------------------\n");
if(start->data==0)
{
printf("the heap is empty\n");
return;
}
else if(start->llink==NULL)
{
printf("delete complete\n");
start->data=0;
return;
}
node *temp;
temp=start;
start->data=current->data;
free(current);
current=before;
while(1)
{
if(temp->llink==NULL||(temp->llink->data>=temp->data&&(temp->rlink->data>=temp->data||temp->rlink==NULL)))
break;
else
{
int t;
if(temp->llink->data<temp->data)
{
t=temp->llink->data;
temp->llink->data=temp->data;
temp->data=t;
}
else
{
t=temp->rlink->data;
temp->rlink->data=temp->data;
temp->data=t;
}
}
}
printf("delete complete.\n");
printf("---------------------------------------------------\n");
}
void menu()
{
printf("---------------------------------------------------\n");
printf("Welcome to heap management\n");
int m=0;
start = (node*)malloc(sizeof(node));
//start->index=nodes++;
start->rlink=NULL;
start->llink=NULL;
start->data=0;
current=start;
while(m!=4)
{
printf("press 1 to insert, 2 to delete the max node,3 to print, 4 to quit.\n");
scanf("%d", &m);
if(m==1)
MAXheap();
else if(m==2)
deletemax();
else if(m==3)
print();
else if(m==4)
{
printf("BYE.");
return;
}
else
printf("Please enter a number between 1 and 3.\n");
printf("---------------------------------------------------\n");
}
}
void print()
{
if(start->data==0)
{
printf("the heap is empty.\n");
printf("---------------------------------------------------\n");
return;
}
queue[rear++]=start;
node *temp;
while(1)
{
int i;
for(i=front;i<rear;i++)
{
printf("%d ", queue[i]->data);
if(queue[i]==current)
{
printf("\n");
front=0;
rear=0;
printf("---------------------------------------------------\n");
return;
}
}
printf("\n");
int t=rear;
for(i=front;i<t;i++)
{
if(queue[i]->llink!=NULL)
queue[rear++]=queue[i]->llink;
if(queue[i]->rlink!=NULL)
queue[rear++]=queue[i]->rlink;
}
front=t;
}
}
int main()
{
menu();
return 0;
}
*/
/*
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<windows.h>
void addheap();
void deleteheap();
void print();
void menu();
int n=1;
int heap[10000];
void addheap()
{
printf("--------------------------------------------------------------\n");
if(n>=10000)
{
printf("the heap is full.\n");
printf("--------------------------------------------------------------\n");
return;
}
int num;
printf("please enter an integer.\n");
scanf("%d", &num);
while(num<=0)
{
printf("please enter an integer.\n");
scanf("%d", &num);
}
heap[n++]=num;
//printf("num=%d\n", num);
// for(int k=0;k<n;k++)
//printf("%d ", heap[k]);
// printf("\n");
int i;
i=(n-1)/2;
int j;
j=(n-1);
//printf("%d %d %d %d %d\n",n, i, j, heap[i], heap[j]);
while(heap[i]<heap[j]&&i>0)
{
//printf("debug\n");
int temp;
temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
j=i;
i=i/2;
}
printf("insert complete.\n");
printf("--------------------------------------------------------------\n");
}
void deleteheap()
{
printf("--------------------------------------------------------------\n");
if(n==1)
{
printf("the heap is empty.\n");
printf("--------------------------------------------------------------\n");
return;
}
heap[1]=heap[n-1];
n--;
int i=1;
while(1)
{
if(i*2>=n)
break;
else if(i*2+1>=n)
break;
if(heap[i]>heap[i*2]&&heap[i]>heap[i*2+1])
break;
int temp;
if(heap[i]<heap[i*2])
{
temp=heap[i];
heap[i]=heap[i*2];
heap[i*2]=temp;
i=i*2;
}
else if(heap[i]<heap[i*2+1])
{
temp=heap[i];
heap[i]=heap[i*2+1];
heap[i*2+1]=temp;
i=i*2+1;
}
}
printf("delete complete.\n");
printf("--------------------------------------------------------------\n");
}
void print()
{
printf("--------------------------------------------------------------\n");
if(n==1)
{
printf("the heap is empty.\n");
printf("--------------------------------------------------------------\n");
return;
}
int a=1;
int b=1;
int c;
int i;
printf("%d\n", heap[1]);
while(a<n)
{
c=a+b*2;
if(a+b*2>=n)
c=n-1;
for(i=a+1;i<=c;i++)
printf("%d ", heap[i]);
printf("\n");
a=a+b*2;
b++;
}
printf("--------------------------------------------------------------\n");
}
void menu()
{
int num=0;
printf("--------------------------------------------------------------\n");
printf("welcome to heap management.\n");
while(num!=4)
{
printf("enter 1 to insert, 2 to delete the max node, 3 to print, 4 to quit.\n");
scanf("%d", &num);
if(num==1)
addheap();
else if(num==2)
deleteheap();
else if(num==3)
print();
else if(num==4)
{
printf("BYE.\n");
printf("--------------------------------------------------------------\n");
return;
}
else
printf("please enter a number between 1 to 4.\n");
printf("--------------------------------------------------------------\n");
}
}
int main()
{
menu();
return 0;
}
*/
/*
#include <stdio.h>
int map[200][200];
int visit[200][200];
int bfscheck[200][200];
int rain;
int n;
int max;
int min=101;
int bfscnt=1;
void bfs(int x, int y, int danger);
int findsafe();
void bfs(int x, int y, int danger)
{
//printf("debug\n");
/*if(danger==2)
{
printf("x=%d y=%d bfscnt=%d\n", x, y, bfscnt);
bfscheck[x][y]=bfscnt;
}*/
/* visit[x][y]=danger;
if(visit[x][y-1]!=danger&&map[x][y-1]>danger&&y-1>=0)
bfs(x, y-1, danger);
if(visit[x][y+1]!=danger&&map[x][y+1]>danger&&y+1<n)
bfs(x, y+1, danger);
if(visit[x-1][y]!=danger&&map[x-1][y]>danger&&x-1>=0)
bfs(x-1, y, danger);
if(visit[x+1][y]!=danger&&map[x+1][y]>danger&&x+1<n)
bfs(x+1, y, danger);
}*/
/*
int findsafe()
{
int i,j;
int cnt=min;
int safe=0;
while(cnt<=max)
{
int safecnt=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(visit[i][j]==cnt);
else
{
if(map[i][j]>cnt)
{
bfs(i, j, cnt);
if(cnt==2)
bfscnt++;
safecnt++;
}
else
visit[i][j]=cnt;
}
}
}
if(safecnt>safe)
safe=safecnt;
/* if(safecnt==2)
printf("%d\n", cnt);*/
/* cnt++;
}
return safe;
}
int main()
{
int i, j;
scanf("%d", &n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d", &map[i][j]);
if(map[i][j]<min)
min=map[i][j];
if(map[i][j]>max)
max=map[i][j];
}
}
int ans = findsafe();
if(ans==0)
ans=1;
printf("%d", ans);
return 0;
}
*/
/*
#include <stdio.h>
int graph[10010][10010];//x, y, 가중치
int n;
int m;
int main()
{
int i, j, a, b, c;
scanf("%d %d", &n, &m);
for(i=0;i<m;i++)
{
scanf("%d %d %d", &a, &b, &c);
graph[a][b]=c;
}
for(i=0;i<9;i++)
{
printf("%d\n", arr[i]);
}
return 0;
}
*/
/*
#include <stdio.h>
int graph[10010][5];//0=가중치, 1=x, 2=y
int visit[10010];
int n;
int m;
int cnt;
int partition(int arr[10010][5],int left, int right)
{
int pivot=arr[left][0];
int high, low;
low = left+1;
high=right;
while(low<=high)
{
while(arr[low][0]>pivot&&low<=high)
low++;
while(arr[high][0]<pivot&&high>=low)
high--;
if(low<high)
{
int temp;
temp=arr[low][0];
arr[low][0]=arr[high][0];
arr[high][0]=temp;
temp=arr[low][1];
arr[low][1]=arr[high][1];
arr[high][1]=temp;
temp=arr[low][2];
arr[low][2]=arr[high][2];
arr[high][2]=temp;
}
}
int temp;
temp=arr[left][0];
arr[left][0]=arr[high][0];
arr[high][0]=temp;
temp=arr[left][1];
arr[left][1]=arr[high][1];
arr[high][1]=temp;
temp=arr[left][2];
arr[left][2]=arr[high][2];
arr[high][2]=temp;
return high;
}
void qsort(int arr[10010][5], int left, int right)
{
if(left<right)
{
int q = partition(arr, left, right);
qsort(arr, left, q-1);
qsort(arr, q+1, right);
}
}
int main()
{
int i, j, a, b, c;
scanf("%d %d", &n, &m);
for(i=0;i<m;i++)
{
scanf("%d %d %d", &a, &b, &c);
graph[cnt][0]=c;
graph[cnt][1]=a;
graph[cnt++][2]=b;
visit[a]++;
visit[b]++;
}
qsort(graph, 0, m-1);
int erasecnt=0;
int sum=0;
//for(i=1;i<=n;i++)
// printf("%d ", visit[i]);
// printf("\n");
for(i=0;i<m;i++)
{
//printf("%d %d %d\n", graph[i][0], graph[i][1], graph[i][2]);
if(m-erasecnt==n-1)
{
if(graph[i][0]%2==1)
sum+=graph[i][0];
}
else
{
if(visit[graph[i][1]]>1&&visit[graph[i][2]]>1)
{
visit[graph[i][1]]--;
visit[graph[i][2]]--;
erasecnt++;
}
}
}
printf("%d", sum);
return 0;
}
*/
#include <stdio.h>
#include <time.h>
void randomseed()
{
}
int main()
{
}