#include using namespace std; typedef long long int LL; typedef unsigned long long int uLL; inline int _Int() { int x; scanf("%d",&x); return x; } LL bigMod(LL A,LL P,int M){ LL R=1; for(A%=M; P; P>>=1) { if(P&1) R=(R*A)%M; A=(A*A)%M; } return R; } /** (A^P) % M **/ LL bigMul(LL A,LL B,LL M) { LL R=0; for(A%=M; B; B>>=1) { if(B&1) R=(R+A)%M; A=(A+A)%M; } return R; } /** (A*B) % M **/ LL negMod(LL A,LL B) { return ( ( ( A % B ) + B) % B ); } /** (A % B) when A is negative or positive **/ LL invMod(LL A,LL M) { return bigMod( A , M-2, M ); } /** (A^(-1)) % M */ uLL _pow(uLL A,int P) { uLL R=1; for(; P; P>>=1) { if(P&1) R=(R*A); A=(A*A); } return R; } /** (A^P) **/ templateT GCD(T x, T y) { while(x) x^=y^=x^=y%=x; return y; } /** Greatest Common Divisor( a , b ) **/ template bool inRng( T u, T v, T x ) { return u<=x && x<=v; } /** check ( u <= x <=v ) */ #define myMemset(a,b) memset(a,b,sizeof(a)) #define pi acos(-1) #define pb push_back #define myDebug(x) cout<<#x<<" : "<