#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class Xorshift { private: uint32_t x, y, z, w; public: Xorshift(uint32_t seed=88675123, int32_t loop=50){ x = 123456789; y = 362436069; z = 521288629; w = seed; while(--loop >= 0){ (*this)(); } } uint32_t operator()(){ uint32_t t=(x^(x<<11)); x=y; y=z; z=w; return w=(w^(w>>19))^(t^(t>>8)); } uint32_t operator()(uint32_t size){ return (*this)() % size; } uint64_t get64(){ uint64_t a = (*this)(); uint64_t b = (*this)(); return (a << 32) | b; } uint64_t get64(uint64_t size){ return get64() % size; } template void shuffle(vector& v){ uint32_t n = v.size(); for(uint32_t i=0; i> n; char prev = 'a'; for(int i=0; i