//#include <stdio.h>
//int n, arr[1001][3] = {},memo[1001][3] = {0};
//int min(int a, int b)
//{
// return a>b? b : a;
//}
//int re(int k, int cnt)
//{
//
// int a, b;
// if(k==0)
// {
// a = 1, b = 2;
// }
// if(k==1)
// {
// a = 0, b = 2;
// }
// if(k==2)
// {
// a = 0, b = 1;
// }
// if(cnt==n-1)
// {
// return arr[cnt][k];
// }
//
// if(memo[cnt][k]!=0)
// {
// return memo[cnt][k];
// }
// else
// {
// return memo[cnt][k] = min(arr[cnt][k] + re(a, cnt+1), arr[cnt][k] + re(b, cnt+1));
// }
//
//}
//
//
//int main()
//{
// int i, j;
// scanf("%d", &n);
// for(i=0; i<n; i++)
// {
// for(j=0; j<3; j++)
// {
// scanf("%d", &arr[i][j]);
// }
// }
// printf("%d", min(min(re(0, 0), re(1, 0)), re(2, 0)));
// return 0;
//}
//r,b=1;main(a){for(scanf("%d",&a);a>b*4;a-=b*=2)r+=2;for(r+=a/b;a%=b;a/=2)r+=a%2;printf("%d",r);}
//#include<stdio.h>
//int main()
//{
// int n,i,j;
// int arr[105][3] = {},c[6] = {};
// scanf("%d",&n);
//
// for(i=0;i<n;i++)
// {
// for(j=0;j<3;j++)
// {
// scanf("%d ",&arr[i][j]);
// }
// }
//// for(i=0;i<5;i++)
//// {
//// scanf("%d",&c[i]);
//// }
//// for(i=0;i<n;i++)
//// {
//// for(j=0;j<3;j++)
//// {
//// printf("%d ",arr[i][j]);
//// }
//// puts("");
//// }
//}
//#include <iostream>
//#include <vector>
//#include <map>
//#include <algorithm>
//using namespace std;
//
//
//int N;
//
//struct Data{
// int number;
// string name;
//};
//
//bool cmp(const Data &v1, const Data &v2){
// return v1.number<v2.number;
//}
//
//map<int,int>check;
//
//int main(){
// cin>>N;
// vector<Data>v;
// for(int i=0; i<N; i++){
// char cmd; int number; string name;
// cin>>cmd>>number>>name;
// if(cmd=='I'){
// if(check[number]==0){
// check[number]=1;
// v.push_back({number,name});
// }
// }
// else if(cmd=='D'){
// if(check[number]==1){
// check[number]=0;
// for(int i=0; i<v.size(); i++){
// if(v[i].number==number) v.erase(v.begin()+i);
// }
// }
// }
// }
// sort(v.begin(),v.end(),cmp);
//
//
// for(int i=0; i<5; i++){
// int find; cin>>find;
// cout<<v[find-1].number<<' '<<v[find-1].name<<'\n';
//
// }
//
//
//}
//#include<stdio.h>
//#include<string.h>
//int main()
//{
// int arr[8] = {},k = 0;
// int a,b,c,d,e,f,g,min=101;
//
// for(int i=0; i<7; i++)
// {
// scanf("%d",&a);
// if(a%2==1)
// {
// k+=a;
// if(min>a)
// {
// min = a;
// }
// }
// }
// if(k !=0)
// {
// printf("%d\n",k);
// printf("%d",min);
// }
// else
// {
// printf("-1");
// }
//}
//#include<stdio.h>
//#include<string.h>
//int main()
//{
// int arr[8] = {},k = 0;
// int a,max=-1;
// for(int i=0; i<9; i++)
// {
// scanf("%d",&a);
// if(max<a)
// {
// max = a;
// k = i+1;
// }
// }
// printf("%d\n",max);
// printf("%d",k);
//}
//#include<stdio.h>
//#include<math.h>
//int main()
//{
// int m,n,i;
// int min = 10005,sum = 0;
// scanf("%d",&m);
// scanf("%d",&n);
// for(i=(int)sqrt(m);i<=(int)sqrt(n);i++)
// {
// if(i*i>=m &&i*i<=n)
// {
// if(min > i*i)
// {
// min = i*i;
// }
// sum +=i*i;
// }
// }
// printf("%d\n",sum);
// printf("%d",min);
//}
//#include<stdio.h>
//int main()
//{
// int a[3][4] = {},k = 0,i,j;
// for(i=0;i<3;i++)
// {
// for(j=0;j<4;j++)
// {
// scanf("%d",&a[i][j]);
// }
// }
// for(i=0;i<3;i++)
// {
// for(j=0;j<4;j++)
// {
// k += a[i][j];
// }
// if(k == 0)
// {
// puts("D");
// }
// if(k == 1)
// {
// puts("C");
// }
// if(k == 2)
// {
// puts("B");
// }
// if(k == 3)
// {
// puts("A");
// }
// if(k == 4)
// {
// puts("E");
// }
// k = 0;
// }
//}
//#include<stdio.h>
//int main()
//{
// int i, arr[5] = {},s = 0;
// for(i=0;i<5;i++)
// {
// scanf("%d",&arr[i]);
// }
// for(i=0;i<5;i++)
// {
// s += arr[i] * arr[i];
// }
// printf("%d", s % 10);
//}
//#include<stdio.h>
//int main()
//{
// int max = 0,i,j,arr[9][9] = {},i_i,j_j;
// for(i=0;i<9;i++)
// {
// for(j=0;j<9;j++)
// {
// scanf("%d",&arr[i][j]);
// }
// }
// for(i=0;i<9;i++)
// {
// for(j=0;j<9;j++)
// {
// if(max < arr[i][j])
// {
// max = arr[i][j];
// i_i = i;
// j_j = j;
// }
// }
// }
// printf("%d\n",max);
// printf("%d %d", i_i+1,j_j+1);
//}
//#include<stdio.h>
//int x,y;
//int gcd(int a, int b)
//{
// return b ? gcd(b, a%b) : a;
//}
//int lcm(int a, int b)
//{
// return (int)x * y/gcd(x,y);
//}
//int main()
//{
// scanf("%d %d", &x, &y);
// printf("%d\n%d", gcd(x,y), lcm(x,y));
//}
//#include<stdio.h>
//int main()
//{
// int n,i,b;
// scanf("%d",&n);
// int binary[20] = {};
// int position = 0;
// b =n;
// while (1)
// {
// binary[position] = n % 2;
// n/=2;
// position++;
// if (n == 0)
// {
// break;
// }
// }
// printf("2 ");
// for (i = position - 1; i >= 0; i--)
// {
// printf("%d", binary[i]);
// }
// puts("");
// n = b;
// printf("8 %o\n",n);
// printf("16 %X",n);
//}
# from itertools import combinations_with_replacement
# n, m = map(int, input().split())
# k = 0
# b = n
# data_3 = []
# num = 1
# if n >= 0:
# data = [0] * n
# for i in range(2, n):
# for j in range(n//i):
# if n % i == 0:
# n /= i
# n = int(n)
# data[i] += 1
# if n == 1:
# break
# n = b
# for i in range(n):
# k += data[i]
# data_2 = [1] * k
# # print(data_2)
# for i in range(n):
# for cwr in combinations_with_replacement(data_2, data[i]):
# data_3.append(len(cwr))
# # print(data_3)
# num = sum(data_3)
# print((num*2)%1000000007)
#
#
# else:
# n = -n
# data = [0] * n
# for i in range(2, n):
# for j in range(n//i):
# if n % i == 0:
# n /= i
# n = int(n)
# data[i] += 1
# if n == 1:
# break
# n = -b
# k = sum(data)
# data_2 = [1] * k
# print(data_2)
# for i in range(n):
# for cwr in combinations_with_replacement(data_2, data[i]):
# data_3.append(len(cwr))
# # print(data_3)
# num = sum(data_3)
# print((num * 2)%1000000007)
#
# # -201160001 32915
# # 130544594
# n = int(input())
# data = list(map(int, input().split()))
# data.sort()
# print(data[len(data)-1]-data[0])