bool DBG = false; // #pragma GCC optimize("Ofast") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") // #pragma GCC optimize("unroll-loops") #include //#include //#include using namespace std; using ll = long long; using ld = long double; //using i128 = __int128_t; //using bint = boost::multiprecision::cpp_int; //using d1024 = boost::multiprecision::number>; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define IFOR(i,a,b) for(int i=((b)-1);i>=(a);--i) #define RPT(i,a,b) for(int i=(a);i<((a)+(b));++i) #define IRPT(i,a,b) for(int i=((a)+(b)-1);i>=(a);--i) #define ALL(x) x.begin(),x.end() #define RALL(x) x.rbegin(),x.rend() #define fs first #define sd second #define couts(x) cout << (x) << (" ") #define coutn(x) cout << (x) << ("\n") #define ncouts(x) numout(x),outst[outst_N++] = ' ' #define ncoutn(x) numout(x),outst[outst_N++] = '\n' #define scouts(x) strout(x),outst[outst_N++] = ' ' #define scoutn(x) strout(x),outst[outst_N++] = '\n' #define dcouts(x) if(DBG) couts(x) #define dcoutn(x) if(DBG) coutn(x) #define endl "\n" #define psb push_back #define ppb pop_back #define eb emplace_back #define lb lower_bound #define ub upper_bound #define LBIT(x,a) (((x)>>(a))&1LL) #define IBIT(x,a) (((x)>>(a))&1) #define BCOUNT(x) (__builtin_popcount(x)) template std::istream &operator>>(std::istream &is, std::vector &vec){ for (auto &v : vec) is >> v; return is; } template std::istream &operator>>(std::istream &is, std::pair &p){is >> p.first >> p.second; return is; } template std::ostream &operator<<(std::ostream &os, const std::vector &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template std::ostream &operator<<(std::ostream &os, const std::deque &vec){ os << "deque["; for (auto v : vec) os << v << ","; os << "]"; return os; } template std::ostream &operator<<(std::ostream &os, const std::set &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template std::ostream &operator<<(std::ostream &os, const std::unordered_set &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template std::ostream &operator<<(std::ostream &os, const std::multiset &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template std::ostream &operator<<(std::ostream &os, const std::unordered_multiset &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template std::ostream &operator<<(std::ostream &os, const std::pair &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; } template std::ostream &operator<<(std::ostream &os, const std::map &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template std::ostream &operator<<(std::ostream &os, const std::unordered_map &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } /* std::ostream &operator<<(std::ostream &os, const i128 nu){ i128 co = nu; if(co==0){cout << '0';} else{ string ous; if(co<0){cout<<'-'; co*=-1;} while(co){ ous += (co%10)+'0'; co /= 10; } reverse(ALL(ous)); cout<>(std::istream &is, i128 &nu){ string cs; cin >> cs; nu=0;int mn=1; for(auto &x:cs) { if(x!='-'){nu*=10;nu+=(x-'0');} else mn *= -1;} nu *= mn; return is; } */ template using V = vector; template using V2 = V>; template using V3 = V>; template using V4 = V>; char outst[20'000'000]; int outst_N = 0; char outst_tmp[200]; template void numout(NUM n){ if(n<0) { n*=-1; outst[outst_N++] = '-';} if(n==0){ outst[outst_N++] = '0'; return;} int cnt = 0; while(n>0){ outst_tmp[cnt++] = '0' + (n % 10); n /= 10; } IFOR(i,0,cnt){ outst[outst_N++] = outst_tmp[i]; } } void strout(std::string s){ for(auto x: s){ outst[outst_N++] = x; } } constexpr ll LINF = 1LL << 60; constexpr int IINF = 1 << 28; constexpr ll mod = 1'000'000'007; //constexpr ll mod = 998244353; void solve(){ int a, b; cin >> a >> b; if(a