/*
#include <stdio.h>
int main()
{
int n,i,j;
scanf("%d", &n);
for(i=0;i<n;i++)
{
for(j=0;j<=i;j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,j;
scanf("%d", &n);
for(i=n;i>0;i--)
{
for(j=0;j<i;j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,j;
scanf("%d", &n);
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
printf(" ");
}
for(j=n;j>i;j--)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,j;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++)
{
printf(" ");
}
for(j=1;j<=2;j++)
{
printf("*");
}
printf("\n");
}
printf("\n");
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,j;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
for(j=0;j<i;j++)
{
printf("*");
}
for(j=0;j<n-i;j++)
{
}
printf("\n");
}
for(i=n;i>0;i--)
{
for(j=1;j<i;j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
1358
#include <stdio.h>
int main()
{
int n,i,j;
scanf("%d", &n);
for(i=1;i<=(n/2)+1;i++)
{
if(n%2==1)
{
for(j=1;j<=((n/2)+1)-i;j++)
{
printf(" ");
}
for(j=1;j<=n;j+=i)
{
printf("*");
}
}
printf("\n");
}
return 0;
}
*/
/*
1358
#include <stdio.h>
int main()
{
int n,i,j;
scanf("%d", &n);
for(i=1;i>=n/2+1;i--)
{
for(j=0-i;j>=n/2;j--)
{
printf(" ");
}
for(j=1;j<=n;j+=(i*2)-1)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
1368
#include <stdio.h>
int main()
{
int h,k,d,i,j;
scanf("%d %d %d", &h,&k,&d);
if(d=="L")
{
for(i=h;i>=1;i--)
{
for(j=1;j<i;j++)
{
printf(" ");
}
for(j=1;j<=k;j++)
{
printf("*");
}
printf("\n");
}
}
else
{
for(i=1;i<=h;i++)
{
for(j=1;j<i;j++)
{
printf(" ");
}
for(j=1;j<=k;j++)
{
printf("*");
}
printf("\n");
}
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,k,i,j;
scanf("%d %d", &n, &k);
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(i==1||i==n||j==1||j==n)
{
printf("*");
}
else
printf(" ");
}
for
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,a,min;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%d", &a);
if(a<min)
{
min=a;
}
}
printf("%d", min);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int h,r,i,j,k,a;
scanf("%d %d", &h,&r);
for(i=1;i<=r;i++)
{
for (j=1;j<=h;j++)
{
for(k=1;k<=j-1;k++)
{
printf(" ");
}
printf("*");
printf("\n");
}
for (j=h-1;j>=1;j--)
{
for(k=1;k<=j-1;k++)
{
printf(" ");
}
printf("*");
printf("\n");
}
}
return 0;
}
*/
/*
2371
#include <stdio.h>
int main()
{
int n,i,j;
scanf("%d", &n);
for(i=n;i>=0;i--)
{
for(j=1;j<=i; j++)
{
printf(" ");
}
for(j=1;j<=(n-i)*2;j++)
{
printf("*");
}
printf("\n");
}
for(i=0;i<=n;i++)
{
for(j=1;j<=i; j++)
{
printf(" ");
}
for(j=1;j<=(n-i)*2;j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
1378
#include <stdio.h>
int main()
{
int n,i,j,sum=0;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
sum = sum+j;
}
}
printf("%d", sum);
return 0;
}
*/
/*
1416
#include <stdio.h>
int main()
{
int arr[1001]={0};
int n,i=1;
scanf("%d", &n);
while(n>0)
{
arr[i]=n%2;
n=n/2;
i++;
}
while(1)
{
i--;
printf("%d", arr[i]);
if(i<=1) break;
}
return 0;
}
*/
/*
1677
#include <stdio.h>
int main()
{
int n,m,i,j;
scanf("%d %d", &n,&m);
for (i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
if((i==1&&j==1) || (i==1&&j==n) ||(i==m&&j==n)||(i==m&&j==1))
{
printf("+");
}
else if((i==1&&j!=1)||(i==1&&&j==n)||(i==m&&j!=1)||(i==m&&j==n))
{
printf("-");
}
else if((j==1&&i!=1) || (j==1&&i==m)||(j==n&&i!=1) || (j==n&&i==m))
{
printf("|");
}
else
{
printf(" ");
}
}
printf("\n");
}
return 0;
}
for(j=1;j<=n;j++)
{
if(arr[i-j]==1&&arr[i]==1)
{
sum=sum+j;
}
*/
/*
4626
#include <stdio.h>
int main()
{
int arr[101]={0};
int n,sum=0,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d", &arr[i]);
}
for(i=1;i<=n;i++)
{
if (arr[i-1]==1&&arr[i]==1)
{
sum=sum+i;
}
else if(arr[i]==1)
{
sum++;
}
else
{
sum=sum+0;
}
}
printf("%d", sum);
return 0;
}
*/