// #define FAST_EXECUTION // #define INTERACTIVE_MODE #include #include #include #include #include #include #include #include #include #include #include using namespace std; // https://github.com/coder3101/cf-template/blob/master/template.cc const long long INF = 9223372036854775807; const long long MOD = 1e9 + 7; #ifndef ONLINE_JUDGE #define WATCH(key, val)\ printf("Watched %s -> %s \n", key, to_string(val).c_str()); #define WATCH_CONTAINER(key, val)\ printf("Watched %s : ", key);\ for (auto e : val)\ printf(" %s", to_string(e).c_str());\ printf("\n"); #define WATCH_MAP(map)\ printf("Watching Map\n");\ for (auto e : map)\ printf("%s -> %s\n", to_string(e.first).c_str(),\ to_string(e.second).c_str());\ printf("\n"); #else #define WATCH(key, val)\ do {\ } while (false); #define WATCH_CONTAINER(key, val)\ do {\ } while (false); #define WATCH_MAP(map)\ do {\ } while (false); #endif #ifdef FAST_EXECUTION #pragma GCC optimize("O3") #pragma comment(linker, "/stack:247474112") #endif #define REP(n) for(int t=0; t= 0; i--) #define RFOR_S(i, n, k) for (i = n - 1; i >= 0; i -= k) #define MAX_OF(x, y) ((x > y) ? x : y) #define MIN_OF(x, y) ((x > y) ? y : x) #define MIN_IN(A) *(min_element(A.begin(), A.end())) #define MAX_IN(A) *(max_element(A.begin(), A.end())) #define MAX_AT(A) (max_element(A.begin(), A.end()) - A.begin()) #define MIN_AT(A) (min_element(A.begin(), A.end()) - A.begin()) #define TESTCASE\ int testcase;\ cin>>testcase;\ while(testcase--) #define GCD(a,b) __gcd(a,b) #define LCM(a,b) (a)*((b)/__gcd(a,b)) #define SORT(A) sort(A.begin(), A.end()); #define RSORT(A) sort(A.rbegin(), A.rend()); #define REVERSE(A) reverse(A.begin(), A.end()); #define ANY(container, result, condition)\ result = false;\ for (const auto &e : container)\ if (condition(e)) {\ result = true;\ break;\ } #define ALL(container, result, condition)\ result = true;\ for (const auto &e : container)\ if (!condition(e)) {\ result = false;\ break;\ } #ifdef INTERACTIVE_MODE #define iprint(...)\ printf(__VA_ARGS__);\ fflush(stdout); #else #define iprint(...) printf(__VA_ARGS__); #endif #define LL long long #define L long #define ULL unsigned long long #define I int #define D double #define UI unsigned int #define VEC(i) vector #define MAP(a, b) map #define UMAP(a, b) unordered_map #define SET(a) set #define USET(a) unordered_set #define MSET(a) multiset #define STR string #define PAIR(a,b) pair #define PAIRI pair #define READ_INT(var) scanf("%d", &var); #define READ_STR(var) cin >> var; #define READ_LONG(var) scanf("%lld", &var); #define WRITE_INT(var) printf("%d", var); #define WRITE_LONG(var) printf("%lld", var); #define WRITE_STR(var) cout << var; #define WRITE_VEC_LL(val)\ for (auto e : val)\ printf("%lld ", e); #define WRITE_VEC_I(val)\ for (auto e : val)\ printf("%d ", e); #define pb push_back #define eb emplace_back LL power(LL x, ULL y) { LL res = 1; x = x % MOD; while (y > 0) { if (y & 1) res = (res*x) % MOD; y = y>>1; x = (x*x) % MOD; } return res; } const int N = 1e9; int main() { TESTCASE { } return 0; }