Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #pragma GCC optimize("Ofast,unroll-loops")
- #pragma GCC target("avx,avx2,fma")
- #define ll long long
- #define ld long double
- #define ar array
- typedef unsigned long long ull;
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
- template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
- void dbg_out() { cerr << endl; }
- template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
- #ifdef LOCAL
- #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
- #else
- #define dbg(...)
- #endif
- template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- #define vt vector
- #define pb push_back
- #define all(c) (c).begin(), (c).end()
- #define sza(x) ((int)x.size())
- #define sz(x) (int)(x).size()
- const int MAX_N = 1e5 + 5;
- const double PI = 3.141592653589793238463;
- const ll MOD = 1e9 + 7;
- const ll INF = 1e9;
- const ld EPS = 1e-9;
- #define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
- #define F_OR1(e) F_OR(i, 0, e, 1)
- #define F_OR2(i, e) F_OR(i, 0, e, 1)
- #define F_OR3(i, b, e) F_OR(i, b, e, 1)
- #define F_OR4(i, b, e, s) F_OR(i, b, e, s)
- #define GET5(a, b, c, d, e, ...) e
- #define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
- #define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
- #define EACH(x, a) for (auto& x: a)
- #define mp make_pair
- #define REP(i,n) for (int i = 0; i < n; i++)
- #define FORE(i,a,b) for (int i = a; i < b; i++)
- #define REPD(i,n) for (int i = n-1; i >= 0; i--)
- #define FORD(i,a,b) for (int i = a; i >= b; i--)
- #define remax(a,b) a = max(a,b)
- #define remin(a,b) a = min(a,b)
- // RANDOM NUMBER GENERATOR
- mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
- #define SHUF(v) shuffle(all(v), RNG);
- // BITWISE
- #define BIT_SET(a,b) ((a) |= (1ULL<<(b)))
- #define BIT_CLEAR(a,b) ((a) &= ~(1ULL<<(b)))
- #define BIT_FLIP(a,b) ((a) ^= (1ULL<<(b)))
- // '!!' to make sure this returns 0 or 1
- #define BIT_CHECK(a,b) (!!((a) & (1ULL<<(b))))
- #define BITMASK_SET(x, mask) ((x) |= (mask))
- #define BITMASK_CLEAR(x, mask) ((x) &= (~(mask)))
- #define BITMASK_FLIP(x, mask) ((x) ^= (mask))
- #define BITMASK_CHECK_ALL(x, mask) (!(~(x) & (mask)))
- #define BITMASK_CHECK_ANY(x, mask) ((x) & (mask))
- /****************** Prime Generator **********************/
- const int N=1e7+10; int prime[20000010];
- bool isprime[N];
- int nprime;
- template <typename T> void Sieve(T a)
- {nprime = 0;memset(isprime,true,sizeof(isprime));
- isprime[1]=false;for(int i=2;i<N;i++){
- if(isprime[i]){prime[nprime++]=i;for(int j=2;i*j<N;j++)
- isprime[i*j]=false;}}}
- ull mulmod(ull a, ull b, ull c) {
- ull x = 0, y=a%c;
- while(b>0) {
- if (b&1)
- x = (x+y)%c;
- y = (y<<1)%c;
- b >>= 1;
- }
- return x;
- }
- ull pow(ull a, ull b, ull c) {
- ull x = 1, y = a;
- while(b > 0) {
- if (b&1) x = mulmod(x,y,c);
- y = mulmod(y,y,c);
- b >>= 1;
- }
- return x;
- }
- template <typename T> bool miller_rabin(ull p, int it){
- if(p<2) return false;
- if(p==2) return true;
- if((p&1)==0) return false;
- ull s = p-1;
- while(s%2==0) s >>= 1;
- while(it--){
- ull a = rand()%(p-1)+1,temp = s;
- ull mod = pow(a,temp,p);
- if(mod==-1 || mod==1) continue;
- while(temp!=p-1 && mod!=p-1){
- mod = mulmod(mod,mod,p);
- temp <<= 1;
- }
- if(mod!=p-1) return false;
- }
- return true;
- }
- template <typename T> inline T PrimeFactors(T n)
- {ll cnt=0,sum=1;for(int i=0; prime[i]*prime[i]<=n
- and i<nprime;i++){cnt=0;while(n%prime[i]==0)
- {cnt++;n/=prime[i];}sum*=(cnt+1);}
- if(n>1)sum*=2;return sum;}
- /****************** Prime Generator End **********************/
- // ----------------------<MATH>---------------------------
- template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
- template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
- int add(int a, int b, int c = MOD){int res=a+b;
- return(res>=c?res-c:res);}
- int mod_neg(int a, int b, int c = MOD){int res;
- if(abs(a-b)<c)res=a-b;else res=(a-b)%c;
- return(res<0?res+c:res);}
- int mul(int a, int b, int c = MOD){ll res=(ll)a*b;
- return(res>=c?res%c:res);}
- int muln(int a, int b, int c = MOD){ll res=(ll)a*b;
- return ((res%c)+c)%c;}
- ll mulmod(ll a,ll b, ll m = MOD){ll q = (ll)(((ld)a*(ld)b)/(ld)m);
- ll r=a*b-q*m;if(r>m)r%=m;if(r<0)r+=m;return r;}
- template<typename T>T expo(T e, T n){T x=1,p=e;while(n)
- {if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
- template<typename T>T power(T e, T n, T m = MOD){T x=1,p=e;while(n)
- {if(n&1)x=mul(x,p,m);p=mul(p,p,m);n>>=1;}return x;}
- template<typename T>T extended_euclid(T a, T b, T &x, T &y)
- {T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
- template<typename T>T mod_inverse(T a, T n = MOD){T x,y,z=0;
- T d=extended_euclid(a,n,x,y);return(d>1?-1:mod_neg(x,z,n));}
- template<class T> bool umin(T& a, const T& b) {
- return b<a?a=b, 1:0;
- }
- template<class T> bool umax(T& a, const T& b) {
- return a<b?a=b, 1:0;
- }
- ll power(ll a, ll b, ll mod) {
- ll x=1, y=a;
- while(b>0) {
- if (b%2){
- x = (x*y)%mod;
- }
- y = (y*y)%mod;
- b/=2;
- }
- return x%mod;
- }
- ll modular_inverse(ll n, ll mod) {
- return power(n, mod-2, mod);
- }
- ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
- while(lb<rb) {
- ll mb=(lb+rb)/2;
- f(mb)?rb=mb:lb=mb+1;
- }
- return lb;
- }
- ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
- while(lb<rb) {
- ll mb=(lb+rb+1)/2;
- f(mb)?lb=mb:rb=mb-1;
- }
- return lb;
- }
- const int FACSZ = 1;
- int fact[FACSZ], ifact[FACSZ];
- void precom(int c=MOD){
- fact[0] = 1;
- FORE(i, 1, FACSZ) fact[i] = mul(fact[i-1], i, c);
- ifact[FACSZ-1] = mod_inverse(fact[FACSZ-1], c);
- REPD(i, FACSZ-1){
- ifact[i] = mul(i+1, ifact[i+1], c);
- }
- }
- int ncr(int n, int r, int c = MOD) {
- return mul(mul(ifact[r], ifact[n-r], c), fact[n], c);
- }
- template<class A> void read(vt<A>& v);
- template<class A, size_t S> void read(ar<A, S>& a);
- template<class T> void read(T& x) {
- cin >> x;
- }
- void read(double& d) {
- string t;
- read(t);
- d=stod(t);
- }
- void read(long double& d) {
- string t;
- read(t);
- d=stold(t);
- }
- template<class H, class... T> void read(H& h, T&... t) {
- read(h);
- read(t...);
- }
- template<class A> void read(vt<A>& x) {
- EACH(a, x)
- read(a);
- }
- template<class A, size_t S> void read(array<A, S>& x) {
- EACH(a, x)
- read(a);
- }
- string to_string(char c) {
- return string(1, c);
- }
- string to_string(bool b) {
- return b?"true":"false";
- }
- string to_string(const char* s) {
- return string(s);
- }
- string to_string(string s) {
- return s;
- }
- string to_string(vt<bool> v) {
- string res;
- FOR(sz(v))
- res+=char('0'+v[i]);
- return res;
- }
- template<size_t S> string to_string(bitset<S> b) {
- string res;
- FOR(S)
- res+=char('0'+b[i]);
- return res;
- }
- template<class T> string to_string(T v) {
- bool f=1;
- string res;
- EACH(x, v) {
- if(!f)
- res+=' ';
- f=0;
- res+=to_string(x);
- }
- return res;
- }
- template<class A> void write(A x) {
- cout << to_string(x);
- }
- template<class H, class... T> void write(const H& h, const T&... t) {
- write(h);
- write(t...);
- }
- void print() {
- write("\n");
- }
- template<class H, class... T> void print(const H& h, const T&... t) {
- write(h);
- if(sizeof...(t))
- write(' ');
- print(t...);
- }
- template<class T> void offset(ll o, T& x) {
- x+=o;
- }
- template<class T> void offset(ll o, vt<T>& x) {
- EACH(a, x)
- offset(o, a);
- }
- template<class T, size_t S> void offset(ll o, ar<T, S>& x) {
- EACH(a, x)
- offset(o, a);
- }
- mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
- ll randint(ll a, ll b) {
- return uniform_int_distribution<ll>(a, b)(mt_rng);
- }
- template<class T, class U> void vti(vt<T> &v, U x, size_t n) {
- v=vt<T>(n, x);
- }
- template<class T, class U> void vti(vt<T> &v, U x, size_t n, size_t m...) {
- v=vt<T>(n);
- EACH(a, v)
- vti(a, x, m);
- }
- /****************** Geometry *****************/
- template <typename T> inline T PointDistanceHorVer(T x1,T y1,T x2, T y2)
- {return abs(x1-x2)+abs(y1-y2);}
- template <typename T> inline T PointDistanceDiagonally(T x1,T y1,T x2, T y2)
- {return sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));}
- template <typename T> inline T PointDistanceMinimum(T x1,T y1,T x2, T y2)
- { T tmp1=abs(x1-x2); T tmp2=abs(y1-y2); T tmp3=abs(tmp1-tmp2);
- T tmp4=min(tmp1, tmp2); return tmp3+tmp4; }
- template <typename T> inline T PointDistance3D(T x1,T y1,T z1,T x2,T y2,T z2)
- {return sqrt(square(x2-x1)+square(y2-y1)+square(z2-z1));}
- template <typename T> inline T Cube(T a){return a*a*a;}
- template <typename T> inline T RectengularPrism(T a,T b,T c)
- {return a*b*c;}
- template <typename T> inline T Pyramid(T base, T height)
- {return (1/3)*base*height;}
- template <typename T> inline T Ellipsoid(T r1,T r2,T r3)
- {return (4/3)*PI*r1*r2*r3;}
- template <typename T> inline T IrregualarPrism(T base, T height)
- {return base*height;}
- template <typename T> inline T Sphere(T radius)
- { return (4/3)*PI*radius*radius*radius;}
- template <typename T> inline T CylinderB(T base, T height)
- {return base*height;} // base and height
- template <typename T> inline T CylinderR(T radius, T height)
- {return PI*radius*radius*height;} // radius and height
- template <typename T> inline T Cone (T radius,T base, T height)
- {return (1/3)*PI*radius*radius*height;}
- /****************** Geometry end *****************/
- const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
- const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
- void solve() {
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t=1;
- read(t);
- FOR(t) {
- write("Case #", i+1, ": ");
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement