#include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef map mii; typedef pair pii; typedef pair pdd; typedef set si; typedef set sll; typedef vector vi; typedef vector > vii; typedef vector vll; typedef vector vld; typedef vector vvi; typedef vector vvii; typedef vector vvll; #define Sort(x) sort(x.begin(),x.end()) #define Reverse(x) reverse(x.begin(),x.end()) #define ABS(a,b) ((a)<(b)?(b)-(a):(a)-(b)) constexpr ll MOD = 1e9+7; // constexpr int INF = 1<<25; // constexpr ll INF = 1LL<<50; // Returns minimum of a and b. // If a is less b, a is set to b. template T checkmin(T& a, T b) { if (a > b) { a = b; } return a; } // Returns maximum of a and b. // If a is less b, a is set to b. template T checkmax(T& a, T b) { if (a < b) { a = b; } return a; } // a = (a+b)%MOD; void addmod(ll& a, ll b) { a = (a+b)%MOD; } // Forward declaration template void dumpContents(const T& v, const string& msg=""); template void dumpContents(const T& v, const string& msg) { cerr << "### " << msg << " ###\n"; for (const auto& x : v) { cerr << x << " "; } cerr << endl; } struct before_main_function { before_main_function() { cin.tie(0); ios::sync_with_stdio(false); cout<