#include using namespace std; //#include //using namespace atcoder; //using mint = modint998244353; //using mint = modint1000000007; #pragma region template using ll = long long; template using V = vector; template using VV = V>; #define overload4(_1,_2,_3,_4,name,...) name #define overload3(_1,_2,_3,name,...) name #define rep1(n) for(ll i=0;i void view(T e){std::cerr << e << std::endl;} template void view(const std::vector& v){for(const auto& e : v){ std::cerr << e << " "; } std::cerr << std::endl;} template void view(const std::vector >& vv){cerr << endl;int cnt = 0;for(const auto& v : vv){cerr << cnt << "th : "; view(v); cnt++;} cerr << endl;} std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } ll power(ll a, ll p){ll ret = 1; while(p){if(p & 1){ret = ret * a;} a = a * a; p >>= 1;} return ret;} ll modpow(ll a, ll p, ll mod){ll ret = 1; while(p){if(p & 1){ret = ret * a % mod;} a = a * a % mod; p >>= 1;} return ret;} templatebool chmax(T &a, const K b) { if (abool chmin(T &a, const K b) { if (b> a >> b; cout << a*b + b << endl; }