/*#include <stdio.h>
#include <string.h>
int num(char x){
if(x>='0'&&x<='9'){
return 1;
}else{
return 0;
}
}
void push(int *stack,int *top,int k){
stack[*top]=k;
(*top)++;
return;
}
void pop(int *stack,int *top){
(*top)--;
stack[*top]=0;
return;
}
int main()
{
char s[201]={};
int stack[101]={};
fgets(s,200,stdin);
int k;
int top=0;
for(int i=0;i<=strlen(s);i+=2){
if(num(s[i])){
k=s[i]-48;
while(s[i+1]!=' '){
i++;
k*=10;
k+=s[i]-48;
}
push(stack,&top,k);
}else if(s[i]=='+'){
k=stack[top-2]+stack[top-1];
pop(stack,&top);
pop(stack,&top);
push(stack,&top,k);
}else if(s[i]=='-'){
k=stack[top-2]-stack[top-1];
pop(stack,&top);
pop(stack,&top);
push(stack,&top,k);
}else if(s[i]=='*'){
k=stack[top-2]*stack[top-1];
pop(stack,&top);
pop(stack,&top);
push(stack,&top,k);
}else if(s[i]=='/'){
k=stack[top-2]/stack[top-1];
pop(stack,&top);
pop(stack,&top);
push(stack,&top,k);
}
}
printf("%d",stack[0]);
return 0;
}*/
/*#include<stdio.h>
int q[10]={};
void push(int *head, int *tail, int k){
if(*tail==10){
if(*head==0){
printf("full!!\n");
return;
}else{
for(int i=*head;i<10;i++){
q[i-*head]=q[i];
q[i]=0;
}
*tail=10-*head;
*head=0;
}
}
q[*tail]=k;
(*tail)++;
return;
}
void pop(int *head, int *tail){
if(*head==*tail){
printf("empty!\n");
return;
}
q[*head]=0;
(*head)++;
return;
}
void print(int *head,int *tail){
if(*head==*tail){
printf("-nothing-\n");
return;
}
for(int i=*head;i<*tail;i++){
printf("%d ",q[i]);
}
printf("\n");
return;
}
int main(){
int head=0;
int tail=0;
int k;
int n;
printf("length:10\n");
while(1){
printf("1:push,2:pop,3:print,4:end->");
scanf("%d",&n);
switch(n){
case 1:
printf("input number:");
scanf("%d",&k);
push(&head,&tail,k);
break;
case 2:
pop(&head,&tail);
break;
case 3:
print(&head,&tail);
break;
case 4:
printf("The End");
return 0;
default:
printf("error!!!!!!!!!!!\n");
}
}
return 0;
}*/
//#include<stdio.h>
//int q[11]={};
//void push(int *head, int *tail, int k){
// if(*tail+1==*head||(*tail==10&&*head==0)){
// printf("full!\n");
// return;
// }
// q[*tail]=k;
// (*tail)++;
// if(*tail==11)*tail=0;
// return;
//}
//void pop(int *head, int *tail){
// if(*tail==*head){
// printf("empty!\n");
// return;
// }
// q[*head]=0;
// (*head)++;
// if(*head==11)*head=0;
// return;
//}
//void print(int *head,int *tail){
// if(*tail==*head){
// printf("-nothing-\n");
// return;
// }
// for(int i=*head;i!=*tail;i++){
// printf("q[%d]:%d\n",i,q[i]);
// if(i==10)i=-1;
// }
// return;
//}
//int main(){
// int head=0;
// int tail=0;
// int k;
// int n;
// printf("length:10\n");
// while(1){
// printf("1:push,2:pop,3:print,4:end->");
// scanf("%d",&n);
// switch(n){
// case 1:
// printf("input number:");
// scanf("%d",&k);
// push(&head,&tail,k);
// break;
// case 2:
// pop(&head,&tail);
// break;
// case 3:
// print(&head,&tail);
// break;
// case 4:
// printf("The End");
// return 0;
// default:
// printf("error!!!!!!!!!!!\n");
// }
// }
// return 0;
//}
//0 ascii: 48
// log (n)
// O(log(n))
// O(n^2)
// bubble sort, insertion sort, selection sort,
// quick sort, merge sort, heap sort
/*#include <stdio.h>
int a[10001];
int n, i, j, temp,asdf;
int main() {
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%d", &a[i]);
for(i=1; i<n; i++)
{
for(int j=1;j<=n-i;j++)
{
if (a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
asdf=0;
for(int j=1;j<n;j++){
if(a[j+1]<a[j]){
asdf=1;
break;
}
}
if(asdf==0){
printf("%d",i);
break;
}
}
return 0;
}*/
/*#include <stdio.h>
int a[100001];
int n,t;
int piv(int begin,int end){
int pivot=begin;
int l=begin+1;
int r=end;
//printf("[%d]", a[pivot]);
while(l<r){
while(a[l]<a[pivot] && l<r)l++;
while(a[r]>=a[pivot] && l<r)r--;
t=a[r];
a[r]=a[l];
a[l]=t;
}
if(a[pivot]>a[l]){
t=a[pivot];
a[pivot]=a[l];
a[l]=t;
}
//printf("[%d, %d][%d] ", begin, end, a[pivot]);
return r;
}
void quick(int begin,int end){
if(begin>=end)return;
int p=piv(begin,end);
quick(begin,p-1);
quick(p,end);
}
int main() {
scanf("%d", &n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
quick(1,n);
for(int i=1;i<=n;i++){
printf("%d\n",a[i]);
}
return 0;
}*/
/*#include<stdio.h>
int a[100001]={};
int main(){
int n;
scanf("%d",&n);
int k,m=100001,M=0;
for(int i=0;i<n;i++){
scanf("%d",&k);
if(k<m)m=k;
if(k>M)M=k;
a[k]++;
}
for(int i=m;i<=M;i++){
for(int j=0;j<a[i];j++){
printf("%d ",i);
}
}
}*/