#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; #define REP(i,n) for(long long i = 0; i < (n); i++) #define FOR(i, m, n) for(long long i = (m);i < (n); ++i) #define ALL(obj) (obj).begin(),(obj).end() template using V = vector; template using P = pair; const ll MOD = (ll)1e9 + 7; const ll MOD2 = 998244353; const ll LLINF = (ll)1e18; const ll INTINF = (ll)1e9; const long double PI = 3.1415926535897932384626433; template void corner(bool flg, T hoge) { if (flg) { cout << hoge << endl; exit(0); } } template ostream &operator<<(ostream &o, const map&obj) { o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o; } template ostream &operator<<(ostream &o, const set&obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; } template ostream &operator<<(ostream &o, const vector&obj) { o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o; } template ostream &operator<<(ostream &o, const pair&obj) { o << "{" << obj.first << ", " << obj.second << "}"; return o; } template