/*
#include <stdio.h>
#include <stdlib.h>
int n,m,a[101][101]={};
int cnt=0;
void b(int x, int y) {
if(x<1||x>n||y<1||y>m) return ;
cnt++;
a[x][y]=cnt;
b(x-1,y+1);
}
int main()
{
scanf("%d %d",&n,&m);
for(int j=1;j<=m;j++) {
for(int i=1;i<=n;i++) {
if(a[i][j]==0) b(i,j);
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
printf("%d ",a[i][j]);
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
#include <stdlib.h>
int n,m,a[101][101]={};
int cnt=0;
void b(int x, int y, int t) {
if(x<1||x>n||y<1||y>m||a[x][y]!=0) {
if(t==1) b(x+1,y-1,(t+1)%4);
else if(t==2) b(x-1,y-1,(t+1)%4);
else if(t==3) b(x-1,y+1,(t+1)%4);
else b(x+1,y+1,(t+1)%4);
return ;
}
cnt++;
a[x][y]=cnt;
switch(t) {
case 1:
b(x,y+1,t);
break;
case 2:
b(x+1,y,t);
break;
case 3:
b(x,y-1,t);
break;
case 4:
b(x-1,y,t);
break;
}
}
int main()
{
scanf("%d %d",&n,&m);
b(1,1,1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) {
printf("%2d ",a[i][j]);
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main() {
int n,a[101],s[101],t=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
s[i]=t+a[i];
t+=a[i];
}
for(int i=1;i<=n;i++) printf("%d ",s[i]);
}
*/
/*
#include <stdio.h>
int main() {
int n,k,s,e,u,d[101]={},m[101]={},t=0;
scanf("%d %d",&k,&n);
for(int i=1;i<=n;i++) {
scanf("%d %d %d",&s,&e,&u);
d[s] = d[s]+u;
d[e+1] = d[e+1]-u;
}
for(int i=1;i<=k;i++) printf("%d ",d[i]);
for(int i=1;i<=k;i++) {
m[i]=t+d[i];
t+=d[i];
} printf("\n");
for(int i=1;i<=k;i++) printf("%d ",m[i]);
}
*/
/*
#include <stdio.h>
int a[1001][1001]={};
int main()
{
int n,m,k,sum=0;
int x1,y1,x2,y2,u;
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=k;i++){
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&u);
a[x1][y1]=a[x1][y1]+u;
a[x2+1][y2+1]=a[x2+1][y2+1]+u;
a[x1][y2+1]=a[x1][y2+1]-u;
a[x2+1][y1]=a[x2+1][y1]-u;
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) printf("%d ",a[i][j]);
printf("\n");
}
for(int i=0; i<n;i++){
for(int j=0; j<m;j++){
sum+=a[i][j];
a[i][j]=sum;
} sum=0;
} sum=0;
for(int j=0;j<m;j++){
for(int i=0;i<n;i++){
sum+=a[i][j];
a[i][j]=sum;
} sum=0;
} printf("\n");
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
printf("%d ",a[i][j]);
} printf("\n");
}
}
*/
/*
#include <stdio.h>
int main() {
int a[101] = {};
int n,g,min;
scanf("%d %d",&n, &g);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<n;i+=g) {
min = a[i];
for(int j=i;j<i+g;j++) {
if(j<n) if(min>a[j]) min = a[j];
}
printf("%d ",min);
}
}
*/
/*
#include <stdio.h>
int n,cnt=0,a[100][100]={};
void view() {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) printf("%d ",a[i][j]);
printf("\n");
}
}
void z(int x, int y, int t) {
if(x<1||x>n||y<1||y>n) {
switch(t) {
case 1:
z(x+2,y-1,2);
break;
case 2:
z(x-1,y+2,1);
break;
}
}
else {
cnt++;
a[x][y]=cnt;
if(x==n&&y==n) return ;
if(t==1) z(x-1,y+1,1);
else z(x+1,y-1,2);
}
}
int main() {
scanf("%d",&n);
z(n,1,1);
view();
}
*/
/*
#include <stdio.h>
int main() {
int map[22][22]={};
int player[9][2]={};
int n;
for(int i=1;i<=10;i++){
for(int j=1;j<=10;j++) scanf("%d ",&map[i][j]);
}
for(int i=1;i<=10;i++){
for(int j=1;j<=10;j++){
if(map[i][j] > 0){
int ballon=map[i][j];
int up=0;
int down=0;
int right=0;
int left=0;
for(int k=1;k<=ballon;k++) {
map[i][j]=-2;
if(map[i+k][j]!=-1&&down==0&&map[i+k][j]<=0) map[i+k][j] = -2;
else if(map[i+k][j]==-1) down=1;
if(map[i-k][j]!=-1&&up==0&&map[i-k][j]<=0) map[i-k][j] = -2;
else if(map[i-k][j]==-1) up=1;
if(map[i][j+k]!=-1&&right==0&&map[i][j+k]<=0) map[i][j+k] = -2;
else if(map[i][j+k] == -1) right=1;
if(map[i][j-k]!=-1&&left==0&&map[i][j-k]<=0) map[i][j-k] = -2;
else if(map[i][j-k]==-1) left=1;
}
}
}
}
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&player[i][0],&player[i][1]);
if(map[player[i][0]][player[i][1]] == 0) map[player[i][0]][player[i][1]] = i;
}
for(int i=1;i<=10;i++){
for(int j=1;j<=10;j++) printf("%d ",map[i][j]);
printf("\n");
}
printf("Character Information\n");
for(int i=1;i<=n;i++){
int x,y;
x = player[i][0];
y = player[i][1];
if(map[x][y]==i) printf("player %d survive\n",i);
else printf("player %d dead\n",i);
}
}
*/
/*
#include<stdio.h>
#include<string.h>
char* solution(int n)
{
// 리턴할 값은 메모리를 동적 할당해주세요.
char* answer = (char*)malloc(sizeof(char)*(n*2+10));
for(int i=0; i<n*2+10; i++)
{
answer[i] = 0;
}
for(int i=0; i<n; i++)
{
if(i%2==0)
strncpy(&answer[i*2],"수", 2);
else
strncpy(&answer[i*2],"박", 2);
}
return answer;
}
int main()
{
printf("%s", solution(3));
}
*/