/*
#include <stdio.h>
int main()
{
int i,s=0,n;
char str[42]={};
int arr[42]={};
scanf("%s",str);
n=strlen(str);
for(i=0;i<n;i++){
if(i%2==1){
if(str[i]=='I'){
arr[i]=1;
continue;
}
else if(str[i]=='V'){
arr[i]=5;
continue;
}
else if(str[i]=='X'){
arr[i]=10;
continue;
}
else if(str[i]=='L'){
arr[i]=50;
continue;
}
else if(str[i]=='C'){
arr[i]=100;
continue;
}
else if(str[i]=='D'){
arr[i]=500;
continue;
}
else if(str[i]=='M'){
arr[i]=1000;
continue;
}
}
else arr[i]=str[i]-48;
}
for(i=1;i<n;i+=2){
if(arr[i]>=arr[i+2]) s+=arr[i-1]*arr[i];
else s-=arr[i-1]*arr[i];
}
printf("%d ",s);
}
*/
/*
#include <stdio.h>
int arr[10002]={};
void f(int i){
if(i==1) {
arr[i]=1;
return ;
}
if(i==2){
arr[i]=1;
f(i-1);
return ;
}
f(i-1);
arr[i]=arr[arr[i-1]]+arr[i-arr[i-1]];
return ;
}
int main()
{
int n;
scanf("%d",&n);
f(n);
printf("%d",arr[n]);
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
char s[100]={},str[100]={};
void f(){
for(int i=0;s[i]!='\0';i+=6){
s[i]=(s[i]-48)*(s[i+4]-48);
s[i+4]-=49;
if(s[i+4]==0) s[i+4]=-1;
}
return ;
}
void g(){
for(int i=0;str[i]!='\0';i+=6){
if(str[i+4]=='\0'){
str[i]='\0';
str[i-1]='\0';
}
else{
str[i]=(str[i]-48)/(str[i+4]-47);
str[i+4]-=47;
}
}
return ;
}
int main()
{
int n,i,j,k;
scanf("%d",&n);
for(i=0;i<n;i++){
if(i!=0){
for(j=0;s[j]!='\0';j++){
s[j]='\0';
}
for(j=0;str[j]!='\0';j++){
str[j]='\0';
}
}
scanf("%s",s);
for(j=0;s[j]!='\0';j++){
str[j]=s[j];
}
f();
for(j=0;s[j]!='\0';j++){
if(j%6==0||(j+2)%6==0){
if(s[j]==-1) printf("0");
else printf("%d",s[j]);
}
else printf("%c",s[j]);
}
printf(" ");
g();
for(k=0;str[k]!='\0';k++){
if(k%6==0||(k+2)%6==0) printf("%d",str[k]);
else printf("%c",str[k]);
}
printf("+c\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a,b,l,i,k=0,m=1;
char s[8]={};
scanf("0.%s",s);
l=strlen(s);
for(i=0;i<l;i++){
k+=s[i]-48;
k*=10;
m*=10;
}
k/=10;
for(i=2;k%2==0;){
if(m%i==0){
k/=i;
m/=i;
}
else break;
}
for(i=5;k%5==0;){
if(m%i==0){
k/=i;
m/=i;
}
else break;
}
printf("%d %d",k,m);
return 0;
}
*/
/*
//nCr
#include <stdio.h>
int main()
{
int i,n,r,t,ma,mi;
long long int k=1;
scanf("%d %d",&n,&r);
t=n-r;
if(t>r){
ma=t;
mi=r;
}
else{
ma=r;
mi=t;
}
for(i=ma+1;i<=n;i++){
k*=i;
}
for(i=1;i<=mi;i++){
k/=i;
}
k=k%100000007;
printf("%lld",k);
}
*/
/*
//우박수
#include <stdio.h>
int arr[10000001]={};
int c(int n) {
if(n==1)return 1;
if(arr[n]!=0)return arr[n];
int t;
if(n%2==0)t=c(n/2)+1;
else t=c(3*n+1)+1;
arr[n]=t;
return t;
}
int main() {
int max=0,q=0;
int a,b,p;
scanf("%d %d",&a,&b);
for(int i=a;i<=b;i++){
p=c(i);
if(p>q){
q=p;
max=i;
}
}
printf("%d %d",max,q);
return 0;
}
*/
/*
#include <stdio.h>
int main(){
int n,i,j;
int s[201]={},r[201]={};
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&s[i]);
r[i]=1;
}
for(i=0;i<n;i++){
for (j=0;j<n;j++){
if (s[i]<s[j]){
r[i]++;
}
}
}
for(i=0;i<n;i++){
printf("%d %d\n",s[i],r[i]);
}
return 0;
}
*/
/*
//두 용액
#include <stdio.h>
int main()
{
int n,i,j,k,a,b,t;
int arr[100001]={};
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&arr[i]);
}
if(arr[0]+arr[1]>=0) k=arr[0]+arr[1];
else k=-arr[0]-arr[1];
a=arr[0];
b=arr[1];
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(arr[i]+arr[j]==k) continue;
else if(arr[i]+arr[j]==0){
k=0;
a=arr[i];
b=arr[j];
break;
}
else if(arr[i]+arr[j]>=0){
if(arr[i]+arr[j]<k){
k=arr[i]+arr[j];
a=arr[i];
b=arr[j];
}
else continue;
}
else if(arr[i]+arr[j]<0){
if(-arr[i]-arr[j]<k){
k=-arr[i]-arr[j];
a=arr[i];
b=arr[j];
}
else continue;
}
}
if(k==0) break;
}
if(a>b){
t=a;
a=b;
b=t;
}
printf("%d %d",a,b);
return 0;
}
*/