/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
char arr[100000];
int a=0, b=0;
scanf("%s",arr);
for(int i=0; i<strlen(arr); i++)
{
if(arr[i]=='(')
{
a=a+1;
}
if(arr[i]==')')
{
b=b+1;
}
}
printf("%d %d",a,b);
return 0;
}
*/
/*
#include <stdio.h>
int n, d[110];
int f()
{
int max=d[0],mi=0;
for(int i=1; i<n; i++)
{
if(max<d[i])
{
max = d[i];
mi = i;
}
}
return mi+1;
}
int main()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &d[i]);
printf("%d", f());
return 0;
}
*/
/*
#include <stdio.h>
int n, d[100010], k;
int f(int k)
{
int a=-1;
for(int i=0; i<n; i++)
{
if(d[i]==k)
{
return i;
}
}
return a;
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &d[i]);
scanf("%d", &k);
printf("%d\n", f(k));
}
*/
/*
#include <stdio.h>
int n;
long long int f(int n)
{
long long int a=0;
for(int i=0; i<n; i++)
{
a=a+n-i;
}
return a;
}
int main()
{
scanf("%d", &n);
printf("%lld\n", f(n));
}
*/
/*
int gcd(int p, int q){ if(p==0) return q; return gcd(q%p, p);}
long long int lcm(int a, int b)
{
long long int c,d;
c=(long long int)a*b;
d=c/gcd(a,b);
return d;
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%lld\n", lcm(a, b));
}
*/
/*
#include <stdio.h>
long long int n;
int sqrt(long long int n)
{
long long int a=0;
if(n>1000000)
{
a=1000;
}
for(long long int i=a; i<n+1; i++)
{
if(i*i<=n && (i+1)*(i+1)>n)
{
return i;
}
}
}
int main()
{
scanf("%lld", &n);
printf("%d\n", sqrt(n));
return 0;
}
*/
/*
#include <stdio.h>
long long int n;
long long int f(long long int n)
{
long long int m=0;
for (int i=0; i<100; i++)
{
m=10*m+(n%10);
n=n/10;
if(n==0)
{
return m;
}
}
}
int main()
{
scanf("%lld", &n);
printf("%lld\n", f(n));
}
*/