/*#include <stdio.h>
long long int n;
long long int f(long long int k) {
while (k>9) {
printf("%d", k%10);
k/=10;
}
return k;
}
int main()
{
scanf("%lld", &n);
printf("%lld\n", f(n));
}
*/
/*
#include <stdio.h>
long long int n, m;
long long int f(long long int a, long long int b)
{
if(a>b){return (long long int)a-b;}
else{ return (long long int)b-a;}
}
int main()
{
scanf("%lld%lld", &n, &m);
printf("%lld\n", f(n, m));
}
*/
/*
#include <stdio.h>
int n, m;
int min(int a, int b)
{
return a<=b?a:b;
}
int main()
{
scanf("%d%d", &n, &m);
printf("%d\n", min(n, m));
}
*/
/*
#include <stdio.h>
int a, b;
int gcd(int n, int m){
int i,j,l;
if(n<=m){
i=m;
}
else{
i=n;
}
for(j=1; j<=i; j++){
if(n%j==0 && m%j==0){
l=j;
}
}
return l;
}
int main()
{
scanf("%d%d", &a, &b);
printf("%d\n", gcd(a, b));
}
*/
/*
#include <stdio.h>
int a, n;
long long int pow(int a, int n) {
long long int b=1;
int i;
if(a==1) {
b=1;
}
else{
for(i=1; i<=n; i++) {
b*=a;
}
}
return b;
}
int main()
{
scanf("%d%d", &a, &n);
printf("%lld\n", pow(a, n));
}
*/
/*
#include <stdio.h>
int n, d[110];
int f(){
int i,a=0;
for(i=0; i<n; i++){
if(d[i]>a){
a=d[i];
}
}
for(i=0; i<n; i++){
if(d[i]==a){
return i+1;
break;
}
}
}
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 N) {
int i,a=0;
for(i=0;i<=100000; i++){
if(d[i]==N){
a=i;
break;
}
else{
a=-1;
}
}
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;
int i;
for(i=0; i<=N; i++){
a+=i;
}
return a;
}
int main()
{
scanf("%d", &n);
printf("%lld\n", f(n));
}
두 수의 곱은 두 수의 최대공약수와 최소공배수의 곱과 같다
*/
/*
#include <stdio.h>
int gcd(int p, int q){ if(p==0) return q; return gcd(q%p, p);}
long long int lcm(int a, int b){
return (long long int)a*b/gcd(a,b);
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%lld\n", lcm(a, b));
}
*/
/*
#include <stdio.h>
int n, a, b, d[1010];
int maxi(int a, int b){
int k=a;
int l=d[a];
for(int i=a; i<=b; i++){
if(d[i]>l){
k=i;
l=d[i];
}
}
return k;
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &d[i]);
scanf("%d%d", &a, &b);
printf("%d\n", maxi(a, b));
}
*/