/*#include<stdio.h>
int main(){
int a,c,d,e,t;
char b;
scanf("%d",&a);
c=a;
while(b!='='){
scanf("%c",&b);
if(b=='='){
break;
}
scanf("%d",&a);
if(b=='+'){
c+=a;
}
if(b=='-'){
c-=a;
}
if(b=='*'){
c*=a;
}
if(b=='/'){
c/=a;
}
}
printf("%d",c);
}
*/
/*
//#include<stdio.h>
//
//int main(){
// int s=0, n;
// char q='+';
//
// while(1) {
// scanf("%d%c", &n, &p);
//
// if(q=='+') {
// s+= n;
// }
//
//
// q = p;
// // +a+b
// }
//
*/
/*
#include<stdio.h>
int main(){
long long int a,b,t,s,q,i,j;
scanf("%lld",&a);
q=0;
for(i=0;i<=a;i++){
t=a-i;
for(j=1;j<=t;j++){
if(j*j>t){
break;
}
if(t==j*j){
q=3;
break;
}
}
if(q==3){
break;
}
}
printf("%lld %lld",i,j);
return 0;
}
*/
/*
#include<stdio.h>
int main(){
int a,stop,c,t,i;
scanf("%d",&a);
i=0;
c=0;
for(i;i*i<a;i++){
}
if(i*i>a){
i-=1;
}
c=a-i*i;
printf("%d %d",c,i);
}
*/
/*
//#include<stdio.h>
//
//int main() {
// int n, k, i;
//
// scanf("%d", &n);
//
// for(i=1; ; i++) {
// if(i*i>=n) {
// k = i-1;
// printf("%d %d", n - (k*k), k);
// break;
// }
// }
//
//}
/*
사각형 출력하기 1~4
*/
/*
넓이 좌표 개념 사용 하셈
*/
/*
#include <stdio.h>
int main(){
int a,b;
scanf("%d",&a);
for(int i=1;i<=a;i++){
for(int j=1;j<=a;j++){
printf("*");
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main(){
int a,b;
scanf("%d",&a);
for(int i=1;i<=a;i++){
for(int j=1;j<=a;j++){
if(i==1||i==a){
printf("*");
}
else{
if(j==1||j==a){
printf("*");
}
else{
printf(" ");
}
}
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main(){
int a,b;
scanf("%d",&a);
for(int i=1;i<=a;i++){
for(int j=1;j<=a;j++){
if(i==1||i==a){
printf("*");
}
else{
if(j==1||j==a||j==i||j==a-i+1){
printf("*");
}
else{
printf(" ");
}
}
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main(){
int a;
scanf("%d",&a);
for(int i=1;i<=a;i++){
for(int j=1;j<=a;j++){
if(i==1||i==a||i==a/2+1){
printf("*");
}
else{
if(j==1||j==a||j==i||j==a-i+1||j==a/2+1){
printf("*");
}
else{
printf(" ");
}
}
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main(){
int a,b,c;
c=1;
scanf("%d %d",&a,&b);
for(int i=1;i<=a;i++){
for(int j=1;j<=a;j++){
if(i==1||i==a||j==1||j==a){
printf("*");
}
else if(j==c*b-(i%b)+1){
printf("*");
c+=1;
}
else{
printf(" ");
}
}
printf("\n");
c=1;
}
return 0;
}
(i+j-1)%k==0
*/
/*
#include <stdio.h>
int main() {
int i, j, n;
scanf("%d", &n);
for(i=1; i<=n; i++) {
for(j=1; j<=i; j++) {
printf("*");
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main() {
int a;
scanf("%d",&a);
for(int i=1;i<=a;i++){
for(int j=1;j<=i;j++){
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main() {
int a;
scanf("%d", &a);
for(int i=1;i<=a;i++){
for(int j=a;j>=i;j--){
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main() {
int a;
scanf("%d",&a);
for(int i=1;i<=a;i++){
for(int k=1;k<=i-1;k++){
printf(" ");
}
for(int j=a;j>=i;j--){
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main() {
int a, i, j, k;
scanf("%d",&a);
for(i=1;i<=a;i++){
for(j=1;j<=i;j++){
printf("*");
}
printf("\n");
}
for(i=i-2;i>=0;i--){
for(j=1;j<=i;j++){
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main() {
int a;
scanf("%d",&a);
for(int i=1;i<=a/2+1;i++){
for(int j=a/2;j>=i;j--){
printf(" ");
}
for(int j=1;j<=i*2-1;j++){
printf("*");
}
printf("\n");
}
return 0;
}
*/