#define _USE_MATH_DEFINES #include using namespace std; using ll = long long; using ld = long double; constexpr ll MOD = 1000000007; #define ONLINE_JUDGE #ifndef ONLINE_JUDGE 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 multiset&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;} ostream &operator<<(ostream &o, const string &obj) {o << "\""; o << obj.c_str(); o << "\""; return o;} template ostream &operator<<(ostream &o, const pair&obj) {o << "(" << obj.first << ", " << obj.second << ")"; return o;} template