/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
char a[100];
int b,c,d;
} hi;
int main()
{
hi arr[101],temp;
int n,i,j;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%s %d %d %d",arr[i].a,&arr[i].b,&arr[i].c,&arr[i].d);
}
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if(arr[j].b>arr[j+1].b)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else if(arr[j].b==arr[j+1].b)
{
if(arr[j].c>arr[j+1].c)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else if(arr[j].c==arr[j+1].c)
{
if(arr[j].d>arr[j+1].d)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else if(arr[j].d==arr[j+1].d)
{
if(strcmp(arr[j].a,arr[j+1].a)>0)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
}
}
for(i=1; i<=n; i++)
{
printf("%s\n",arr[i].a);
}
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
char a[101];
int b;
}hi;
int main()
{
hi arr[51],temp;
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%s %d",arr[i].a,&arr[i].b);
}
for(i=1;i<n;i++)
{
for(j=1;j<=n-1;j++)
{
if(arr[j].b<arr[j+1].b)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
printf("%s",arr[3].a);
}
*/
/*
#include <stdio.h>
typedef struct
{
int a,b,c;
}hi;
int main()
{
hi arr[1001],temp;
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&arr[i].b,&arr[i].c);
arr[i].a=i;
}
for(i=1;i<n;i++)
{
for(j=1;j<=n-1;j++)
{
if(arr[j].b<arr[j+1].b)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else if(arr[j].b==arr[j+1].b)
{
if(arr[j].c<arr[j+1].c)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
for(i=1;i<=n;i++)
{
printf("%d %d %d\n",arr[i].a,arr[i].b,arr[i].c);
}
return 0;
}
binary search
// s번째부터 e번째까지 중에 k의 위치 리턴 (없으면 -1)
*/
/*
#include <stdio.h>
int arr[1000];
int bs(int s, int e, int k)
{
int mid=(e+s)/2;
if(s==e&&arr[mid]!=k)
{
return -1;
}
if(k<arr[mid])
{
bs(s,mid-1,k);
}
else if(k>arr[mid])
{
bs(mid+1,e,k);
}
else
{
return mid;
}
}
int main()
{
int i,k;
for(i=1;i<=5;i++)
{
scanf("%d",&arr[i]);
}
scanf("%d",&k);
printf("k값의 위치는??!! %d 입니다!!",bs(1,5,k));
return 0;
}
*/