//Author:: Satish Srinivas
#include<bits/stdc++.h>
 
#define foi(i,m,n) for(int i=(m);i<=(n);i++)
#define fol(i,m,n) for(ll i=(m);i<=(n);i++)
#define fri(i,m,n) for(int i=(m);i>=(n);i--)
#define frl(i,m,n) for(ll i=(m);i>=(n);i--)
//#define mp make_pair
//#define pb push_back
#define pi 3.1415926536
#define mo 1000000007
 
typedef long long int ll;
 
ll gcd(ll a,ll b){return (b)?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(std::max(a,b),std::min(a,b));}
 
using namespace std;
 
//brute force
int findMin(int ar[],int l,int r)
{
 
   if(r>l)

//Author:: Satish Srinivas
#include<bits/stdc++.h>
 
#define foi(i,m,n) for(int i=(m);i<=(n);i++)
#define fol(i,m,n) for(ll i=(m);i<=(n);i++)
#define fri(i,m,n) for(int i=(m);i>=(n);i--)
#define frl(i,m,n) for(ll i=(m);i>=(n);i--)
//#define mp make_pair
//#define pb push_back
#define pi 3.1415926536
#define mo 1000000007
 
typedef long long int ll;
 
ll gcd(ll a,ll b){return (b)?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(std::max(a,b),std::min(a,b));}
 
using namespace std;
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);