// ¿Í 5¿ù 1ÀÏ
/*
#include <stdio.h>
#include <stdlib.h>
int arr[20]={};
int cnt = 0;
int index = 0;
int n,k;
int ok = 1;
void back(int j, int findex) {
if(j==0) {
for(int i=0;;i++) {
index = findex+arr[j]+i;
if(index > n) {
return ;
}
else if(j == k-1) {
cnt++;
}
else {
back(j+1,index);
}
}
}
else {
for(int i=1;;i++) {
index = findex+arr[j]+i;
if(index >n) {
return;
}
else if(j == k-1) {
cnt++;
}
else {
back(j+1,index);
}
}
}
index = findex;
}
int main()
{
scanf("%d %d",&n,&k);
for(int i=0;i<k;i++) scanf("%d",&arr[i]);
back(0,0);
printf("%d",cnt);
}
*/
/*
#include <stdio.h>
int soil[100][100];
int main() {
int n,m,x,y;
int max = -1;
scanf("%d %d %d %d",&n,&m,&x,&y);
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
scanf("%d",&soil[i][j]);
}
}
for(int i=0;i<m-y+1;i++) {
for(int j=0;j<n-x+1;j++) {
int cnt = 0;
for(int k=i;k<i+y;k++) {
for(int l=j;l<j+x;l++) {
cnt += soil[k][l];
}
}
if(cnt > max) {
max = cnt ;
}
}
}
printf("%d",max);
}
*/
/*
#include <stdio.h>
#include <string.h>
typedef struct {
char name[100];
int isempty;
} number;
int n;
number p[10000];
int main() {
scanf("%d ",&n);
for(int i=0;i<n;i++) {
char code;
int en;
char name[100] = {};
scanf("%c %d %s ",&code,&en,name);
if(code == 'I') {
if(p[en].isempty != 1000) {
strcpy(p[en].name,name);
p[en].isempty = 1000;
}
}
else {
if(p[en].isempty == 1000) {
p[en].isempty = 1;
}
}
}
int cnt = 0;
int j=0;
for(int i=0;i<5;i++) {
int en;
scanf("%d",&en);
for(;j<10000;j++) {
if(p[j].isempty == 1000) cnt++;
if(cnt == en) break;
}
printf("%d %s\n",j,p[j].name);
j++;
}
}
*/
/*
#include <stdio.h>
#include <string.h>
char a[100] = {};
char b[100] = {};
int astack[100] = {};
int bstack[100] = {};
int aindex = -1;
int bindex = -1;
int fstsum[100] = {};
void enqueue(char num, char ab) {
if(ab == 'a') astack[++aindex] = num-48;
else bstack[++bindex] = num - 48;
}
int pop(char ab) {
if(ab == 'a') {
if(aindex == -1) return 0;
return astack[aindex--];
}
else {
if(bindex == -1) return 0;
return bstack[bindex--];
}
}
int main() {
int plm = 1;
gets(a);
gets(b);
for(int i=0;a[i]!=NULL;i++) {
enqueue(a[i], 'a');
}
for(int i=0;b[i]!=NULL;i++) {
enqueue(b[i], 'b');
}
int cnt = 0;
for(int i=0;a[i]!=NULL || b[i]!=NULL;i++) {
fstsum[i] = pop('a')-pop('b');
cnt++;
}
int endofit = 0;
int index = cnt-1;
for(int i=0;i<cnt;i++) {
if(endofit == 0 && fstsum[i] == 0) {}
else index = i;
}
if(fstsum[index]<0) {
for(int i=0;i<cnt;i++) {
fstsum[i]*=-1;
}
plm = -1;
}
for(int i=0;i<cnt;i++) {
if(fstsum[i]<0) {
fstsum[i] = 10+fstsum[i];
fstsum[i+1] -= 1;
}
}
int printed = 0;
for(int i=cnt-1;i>=0;i--) {
if(i == cnt-1 && plm == -1) {
printf("-");
}
if(printed == 0 && fstsum[i] == 0) {
}
else {
printf("%d",fstsum[i]);
printed++;
}
}
if(printed == 0) {
printf("0");
}
}
*/
/*
#include <stdio.h>
int n;
int stx,sty,ndx,ndy;
int cnt = 0;
int index = -1;
int head = -1;
int running = 1;
int visited[1001][1001] = {};
typedef struct {
int x, y, len;
} queue;
queue q[2000];
queue qq[2000];
void enqueue(int x, int y, int len) {
if(x == ndx && y == ndy) {
printf("%d",len);
running = 0;
return ;
}
if(x >= 0 && x < n && y >= 0 && y < n && visited[x][y]==0) {
if(++index < 2000) {
q[index%2000].x = x;
q[index%2000].y = y;
q[index%2000].len = len;
} else if(index < 4000) {
qq[index%2000].x = x;
qq[index%2000].y = y;
qq[index%2000].len = len;
}
else {
index%=2000;
q[index%2000].x = x;
q[index%2000].y = y;
q[index%2000].len = len;
}
visited[x][y] = 1;
}
}
queue dequeue() {
if(++head < 2000) {
return q[head];
}
else if(head < 4000) {
return qq[head%2000];
}
else {
head %= 2000;
return q[head];
}
}
int main() {
scanf("%d %d %d %d %d",&n,&stx,&sty,&ndx,&ndy);
stx--;
sty--;
ndx--;
ndy--;
enqueue(stx,sty,0);
while(running) {
queue dq = dequeue();
int x = dq.x;
int y = dq.y;
enqueue(x+2,y+1,dq.len+1);
enqueue(x+2,y-1,dq.len+1);
enqueue(x-1,y+2,dq.len+1);
enqueue(x-1,y-2,dq.len+1);
enqueue(x+1,y+2,dq.len+1);
enqueue(x+1,y-2,dq.len+1);
enqueue(x-2,y+1,dq.len+1);
enqueue(x-2,y-1,dq.len+1);
}
}*/
/*
#include <stdio.h>
#include <string.h>
char sntns[4000];
char ch;
int pos[4000];
int index = 0;
int main() {
gets(sntns);
scanf(" %c",&ch);
for(int i=0;sntns[i]!=NULL;i++) {
if(sntns[i] == ch || (sntns[i]+32 == ch && sntns[i] >= 'A' ) || sntns[i]-32 == ch) {
pos[index++] = i+1;
}
}
int sum = 0;
for(int i=0;i<index-1;i++) {
sum+=pos[i+1]-pos[i];
}
printf("%d\n",index);
printf("%d",sum);
}
*/