#ifndef EXT_H
#ifndef LIB
#define EXT_H
#include<bits/stdc++.h>
using namespace std;
template<typename T>
T floor_sqrt(T x,T l=1,T r=-1){
if(r==-1) r=x;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(mid*mid<=x){
l=mid+1;
ans=mid;
}
else{
r=mid-1;
}
}
return ans;
}
template<typename T>
void print(T x,bool first=true){
if(x<0){
putchar('-');
print(-x,false);
return;
}
if(x==0){
if(first) putchar('0');
return;
}
print(x/10,false);
putchar((int)(x%10)+'0');
}
template<typename T>
inline void read(T& x){
x=0;bool sym=0;char c=std::getchar();
while(!isdigit(c)){sym^=(c=='-');c=std::getchar();}
while(isdigit(c)){x=x*10+c-48;c=std::getchar();}
if(sym)x=-x;
}
istream& operator >>(istream &in,__int128 &x){
read(x);
return in;
}
ostream& operator <<(ostream &out,__int128 &x){
print(x);
return out;
}
long long power(long long a,long long n,long long mod=LLONG_MAX){
long long ans=1,base=a;
while(n){
if(mod){ if(n&1) ans=ans*base%mod;}
else{ if(n&1) ans=ans*base;}
if(mod) base=base*base%mod;
else base=base*base;
n>>=1;
}
return ans;
}
int floor_log(int base,int x){
int l=0,r=x,ans=-1;
while(l<=r){
int mid=(l+r)/2;
int res=power(base,mid);
if(res<=0 or res>x){
r=mid-1;
}
else{
l=mid+1;
ans=mid;
}
}
return ans;
}
double _log(int base,int x){
return std::log(x)/std::log(base);
}
long long __C(long long n,long long m,long long p){
if(n<m){
return 0;
}
if(m>n-m){
m=n-m;
}
long long a=1,b=1;
for(int i=0;i<m;++i){
a=(a*(n-i))%p;
b=(b*(i+1))%p;
}
return a*power(b,p-2,p)%p;
}
//Lucas
long long C(long long n,long long m,long long p){
if(!m) return 1;
return C(n/p,m/p,p)*__C(n%p,m%p,p)%p;
}
long long phi(int n){
long long ans=n;
for(int i=2;i<=sqrt(n+0.5);i++){
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0){
n/=i;
}
}
}
if(n>1){
ans=ans/n*(n-1);
}
return ans;
}
#define sqrt sqrtl
#define pow powl
#define sqrt_int floor_sqrt
#define pow_int power
#endif
#endif