///Bismillahir Rahmanir Rahim #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /**Define file I/O **/ #define f_input freopen("input.txt","r",stdin) #define f_output freopen("output.txt","w",stdout) /**Define memory set function**/ #define mem(x,y) memset(x,y,sizeof(x)) #define CLEAR(x) memset(x,0,sizeof(x)) /**Define function and object**/ #define pb push_back #define Sort(v) sort(v.begin(),v.end()) #define RSort(v) sort(v.rbegin(),v.rend()) #define CSort(v,C) sort(v.begin(),v.end(),C) #define all(v) (v).begin(),(v).end() #define sqr(x) ((x)*(x)) #define find_dist(a,b) sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)) /**Define constant value**/ #define ERR 1e-9 #define pi (2*acos(0)) #define PI 3.141592653589793 /**Define input**/ #define scanint(a) scanf("%d",&a) #define scanLLD(a) scanf("%lld",&a) #define scanstr(s) scanf("%s",s) #define scanline(l) scanf(" %[^\n]",l) #define scandouble(d) scanf("%lf",&d) #define scanchar(c) scanf("%c",&c) /**Define Bitwise operation**/ #define check(n, pos) (n & (1ll<<(pos))) #define biton(n, pos) (n | (1ll<<(pos))) #define bitoff(n, pos) (n & ~(1ll<<(pos))) /**Define color**/ enum {WHITE,GREY,BLACK}; /**Sync off with stdio**/ #define __ cin.sync_with_stdio(false);\ cin.tie(); /**Debug tools**/ #define what_is(x) cerr<<(#x)<<" is "< vint; typedef vector< vint > vint2D; typedef vector vstr; typedef vectorvchar; typedef vector< vchar >vchar2D; typedef queue Qi; typedef queue< Qi > Qii; typedef map Mii; typedef map Msi; typedef map Mis; typedef stack stk; typedef pair pp; typedef pair ppp; typedef long long int ll; ll inf=1e18; /**Template & structure**/ templateT gcd(T a,T b){return b == 0 ? a : gcd(b, a % b);} templateT lcm(T a, T b) {return a / gcd(a,b) * b;} templateT last_bit(T n) { return n & 1; } templateT big_mod(T n,T p,T m){if(p==0)return (T)1;T x=big_mod(n,p/2,m);x=(x*x)%m;if(p&1)x=(x*n)%m;return x;} templateT modInv(T a, T m){T x, y; extgcd(a, m, x, y); x %= m; while (x < 0){x += m;} return x;} template T extgcd(T a,T b,T& x,T& y){if(b==0){x=1;y=0;return a;}else{int g=extgcd(b,a%b,y,x);y-=a/b*x;return g;}} templateT multiplication(T n,T p,T m){if(p==0)return (T)0;T x=multiplication(n,p/2,m);x=(x+x)%m;if(p&1)x=(x+n)%m;return x;} templateT my_pow(T n,T p){if(p==0)return 1;T x=my_pow(n,p/2);x=(x*x);if(p&1)x=(x*n);return x;} ///n to the power p template double getdist(T a, T b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}/// distance between a & b template T extract(string s, T ret) {stringstream ss(s); ss >> ret; return ret;}/// extract words or numbers from a line template string tostring(T n) {stringstream ss; ss << n; return ss.str();}/// convert a number to string template T Mod(T n,T m) {return (n%m+m)%m;} ///For Positive Negative No. template T MIN3(T a,T b,T c) {return min(a,min(b,c));} /// minimum of 3 number template T MAX3(T a,T b,T c) {return max(a,max(b,c));} ///maximum of 3 number template void print_vector(T &v){int sz=v.size();if(sz)cout< R Josephus(R n,R k){R ans=1;for(R i=2;i<=n;i++)ans=(ans+k-1)%i+1;return ans;} template R toitent_Phi2(R a){R result = a;for(R i=2;i*i<=a;i++){if(a%i==0) result=result-result/i;while(a%i==0) a=a/i;}if(a>1) result=result-result/a;return result;} template T Angle(T x1,T y1,T x2, T y2){ return atan( double(y1-y2) / double(x1-x2));} //namespace debug{ // int sum(){return 0;} // template T sum(T a,Args... args) {return a+sum(args...);} // void print(){cout<<"\n";return;}templatevoid print(T a,Args... args){cout<>n; ll x=n*(n-1); x++; while(n){ s+=x; n--; x=x+2; } cout<