// ببِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم
/*
───────────────────────────────────────────────────────────────────────────────────────────────────────────
─████████████████───██████████████─████████──████████─██████──██████─██████████████─██████──────────██████─
─██░░░░░░░░░░░░██───██░░░░░░░░░░██─██░░░░██──██░░░░██─██░░██──██░░██─██░░░░░░░░░░██─██░░██████████──██░░██─
─██░░████████░░██───██░░██████░░██─████░░██──██░░████─██░░██──██░░██─██░░██████░░██─██░░░░░░░░░░██──██░░██─
─██░░██────██░░██───██░░██──██░░██───██░░░░██░░░░██───██░░██──██░░██─██░░██──██░░██─██░░██████░░██──██░░██─
─██░░████████░░██───██░░██████░░██───████░░░░░░████───██░░██████░░██─██░░██████░░██─██░░██──██░░██──██░░██─
─██░░░░░░░░░░░░██───██░░░░░░░░░░██─────████░░████─────██░░░░░░░░░░██─██░░░░░░░░░░██─██░░██──██░░██──██░░██─
─██░░██████░░████───██░░██████░░██───────██░░██───────██░░██████░░██─██░░██████░░██─██░░██──██░░██──██░░██─
─██░░██──██░░██─────██░░██──██░░██───────██░░██───────██░░██──██░░██─██░░██──██░░██─██░░██──██░░██████░░██─
─██░░██──██░░██████─██░░██──██░░██───────██░░██───────██░░██──██░░██─██░░██──██░░██─██░░██──██░░░░░░░░░░██─
─██░░██──██░░░░░░██─██░░██──██░░██───────██░░██───────██░░██──██░░██─██░░██──██░░██─██░░██──██████████░░██─
─██████──██████████─██████──██████───────██████───────██████──██████─██████──██████─██████──────────██████─
───────────────────────────────────────────────────────────────────────────────────────────────────────────
Search In Google rayhan50001 or rayhan5000 you can Find all information about me
Bangladesh University of Business & Technology(BUBT)
CSE,29th Intake,Section-05
*/
//*If You Have a Good Personality,You Don’t Need To Describe Yourself*\\
#include
using namespace std;
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define SZ(A) A.size()
#define CLR(a) memset(a,0,sizeof(a))
#define PB push_back
#define PI acos(-1.0)
#define MP(a,b) make_pair(a,b)
#define PII pair
#define PCC pair
#define PIC pair
#define PCI pair
#define VS vector
#define VI vector
#define SC vector
#define SS set
#define SI set
#define SC set
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define READ freopen(“input.txt”, “r”, stdin)
#define WRITE freopen(“output.txt”, “w”, stdout)
#define LL long long
#define FOR(i,a,b) for(int i=a;i=b;i–)
#define For(i,a) for(int i=0;i<a;i++)
#define S(a) scanf("%d",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define S3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define SLL(a) scanf("%lld",&a)
#define SLL2(a,b) scanf("%lld%lld",&a,&b)
#define SLL3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
//#define SS(a) scanf("%s",&a)
#define SC(a) scanf("%c",&a)
#define SD(a) scanf("%lf",&a)
#define P(a) printf("%d",a)
#define PLL(a) printf("%lld",a)
#define PD(a) printf("%lf",a)
#define PC(a) printf("%c",a)
#define PS(a) printf("%s",a)
#define KS printf("Case %d: ",kk++)
#define KN printf("Case %d:\n",kk++)
#define KH printf("Case #%d: ",kk++)
#define NL printf("\n")
#define DB cout<<"done"<<endl;
#define YES() cout<<"YES\n";
#define NO() cout<<"NO\n";
#define Yes() cout<<"Yes\n";
#define No() cout<<"No\n";
#define EPS 1e-9
#define MOD 1000000007
#define INF INT_MAX/3
#define MX 100010
#define DIST(x1,x2, y1, y2) (((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)))
#define DIST3D(x1,x2, y1, y2, z1, z2) (((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)) + ((z1-z2)*(z1-z2)))
#define ansmax -9999999999999999999
templateinline string tostring(T a){ostringstream os("");os <>res;return res;}
templateinline VI parse(T str){VI res;int s;istringstream os(str);while(os>>s)res.PB(s);return res;}
template inline T _sqrt(T x) { return (T) sqrt( (double) x); }
template inline T _bigmod(T n,T m) {T ans=1,mult=n%MOD; while(m){ if(m & 1) ans=(ans*mult)%MOD; m>>=1; mult=(mult*mult)%MOD; } ans%=MOD; return ans;}
template inline T _modinv(T x) {return _bigmod(x,(T) MOD-2)%MOD;}
inline int LEN(string a) {return a.length();}
inline int LEN(char a[]) {return strlen(a);}
template inline T _gcd(T a, T b){return (b==0) ? a : _gcd(b, a % b);}
template inline T _lcm(T x,T y) { return x*y/_gcd(x,y);}
//set function to order a tree
//typedef treepbd_set;
//end set function to order a tree
int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction
bool compare(const pair&i, const pair&j)
{
return i.first > j.first;
}
int in_c() { int c; for (; (c = getchar()) <= ' '; ) { if (!~c) throw ~0; } return c; }
const int mx = 1e5 + 7;
int EQ(double d) {
if ( fabs(d) EPS ? 1 : -1 ;
}
//int n, ans = 0;
//string s[100009];
//vector r, b;
//
//int conv(string t)
//{
// int res = 0;
// for(int i = 0; i =0 && y>=0 && x return true;
else
return false;
}
int main()
{
clock_t begin = clock();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
///your code goes here
///end here
clock_t end = clock();
double time_spent = (double)(end – begin) / CLOCKS_PER_SEC;
cerr<<"Running Time: "<<time_spent<<" Seconds"<<endl;
return 0;
}