結果
問題 |
No.8115 What day of week is it in N days?
|
ユーザー |
|
提出日時 | 2025-04-01 21:21:14 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 25,716 bytes |
コンパイル時間 | 11,211 ms |
コンパイル使用メモリ | 355,656 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-04-01 21:21:26 |
合計ジャッジ時間 | 8,784 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using ull = unsigned long long; using ld = long double; template<typename T> using vc = vector<T>; template<typename T> using vv = vc<vc<T>>; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vc<vvl>; using vs = vc<string>; using vvs = vv<string>; using vb = vc<bool>; using vvb = vv<bool>; using vvvb = vc<vvb>; using lP = pair<ll, ll>; using sP = pair<string, string>; using vlP = vc<lP>; using vsP = vc<sP>; using RLEs = vc<pair<char, ll>>; #define rep(i,n) for(ll i=0;i<(n);++i) #define rrep(i,n) for(ll i=1;i<=(n);++i) #define drep(i,n) for(ll i= (n)-1;i>=0;--i) #define nfor(i,s,n) for(ll i=s;i<n;++i) #define nall(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define YES cout<<"Yes"<<'\n' #define NO cout<<"No"<<'\n' #define OK cout<<"ok"<<'\n' #define YN {cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';} #define dame cout<<-1<<'\n' #define LAST(i, n) (i+1==n?"\n":" ") #define RLAST(i, n) (i==n?"\n":" ") const ll INF = (1LL << 62) - (1LL << 31) - 1; const ll MOD = 998244353; const ll MMOD = 1000000007; const double PI = acos(0) * 2; string atoz = "abcdefghijklmnopqrstuvwxyz"; string TA = "Takahashi"; struct Edge { ll to; ll weight; Edge(ll t, ll w) : to(t), weight(w) { } }; using Graph = vector<vector<Edge>>; //////////////////////////////////////////////////////////////////////////////////////////////// struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;} template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;} template<class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); } template<class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); } template<class T> void sort_unique(std::vector<T> &vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());} //////////////////////////////////////////////////////////////////////////////////////////////// //maths ll floor(ll n, ll a){ return n / a - (n % a < 0); } ll ceil(ll n, ll a){ return n / a + ((n ^ a) >= 0) * (n % a != 0); } //xとyの最大公約数 ll gcd(ll x, ll y){ if(x % y == 0)return y; else return gcd(y, x % y); } //xとyの最小公倍数 ll lcm(ll x, ll y){ return x / gcd(x, y) * y; } ll floor_sqrt(ll N){ assert(N >= 0); ll ok = 0; ll ng = N + 1; while(abs(ok - ng) > 1){ ll mid = (ok + ng) / 2; (mid <= N / mid ? ok : ng) = mid; } return ok; } ll isqrt(ll n){ ll x = n; ll y = (x + 1) / 2; while(y < x){ x = y; y = (x + n / x) / 2; } return x; } ll log2_ceil(ll x){ ll val = 1; while((1LL << val) <= x)++val; return val; } //xの逆元 ll mod_inv(ll x, ll mod){ ll b = mod, u = 1, v = 0; while(b){ ll t = x / b; x -= t * b; swap(x, b); u -= t * v; swap(u, v); } u %= mod; if(u < 0)u += mod; return u; } ll pow_ll(ll x, ll n){ ll ans = 1; while(n > 0){ if(n & 1)ans *= x; x *= x; n >>= 1; } return ans; } ll pow_ll(ll x, ll n, ll mod){ ll ans = 1; while(n > 0){ if(n & 1)ans = ans * x % mod; x = x * x % mod; n >>= 1; } return ans; } ll comb(ll n, ll k, ll mod){ ll x = 1; for(ll i = n - k + 1; i <= n; ++i)x = x * i % mod; ll y = 1; for(ll i = 1; i <= k; ++i)y = y * i % mod; y = pow_ll(y, mod - 2, mod); return x * y % mod; } ll mod_n(ll N, ll mod){ if(N == abs(N))return N % mod; else return (N % mod + mod) % mod; } double rad(double d){return d * PI / 180.;} double deg(double r){return r * 180. / PI;} //not_sqrt ll dist(ll sx, ll sy, ll ex, ll ey){ ll dx = ex - sx, dy = ey - sy; return dx * dx + dy * dy; } ll dist_M(ll sx, ll sy, ll ex, ll ey){ return abs(sx - ex) + abs(sy - ey); } ll count_range(ll n, ll m){ return ((m - n + 1) * (n + m)) / 2; } ll count_range(ll n, ll m, ll mod){ ll len = (m - n + 1) % mod; ll sum = (n + m) % mod; return len * sum % mod * mod_inv(2, mod) % mod; } ll mul(ll a, ll b) {ll infl = 1LL << 60; if (a == 0 || b == 0) return 0; if (infl / a < b) return infl; return min(infl, a * b); } ll count_sum(ll A, ll D, ll L, ll N){ if(A == -1)return (N * (2 * L - (N - 1) * D)) / 2; else if(L == -1)return (N * (2 * A + (N - 1) * D)) / 2; else if(N == -1)return (((L - A) / D + 1) * (A + L)) / 2; else return (N * (A + L)) / 2; } ll count_sum(ll A, ll D, ll L, ll N, ll mod){ ll inv2 = mod_inv(2, mod); if(A == -1){ return (N % mod) * (((2 * L % mod - ((N - 1) % mod) * D % mod + mod) % mod) * inv2 % mod) % mod; }else if(L == -1){ return (N % mod) * (((2 * A % mod + ((N - 1) % mod) * D % mod) % mod) * inv2 % mod) % mod; }else if(N == -1){ ll num = (((L - A + mod) % mod) * mod_inv(D, mod)) % mod + 1; return (num % mod) * ((A + L) % mod) % mod * inv2 % mod; }else{ return (N % mod) * ((A + L) % mod) % mod * inv2 % mod; } } //素数判定 bool is_Prime(ll num){ if(num == 1)return false; for(ll i = 2; i * i <= num; ++i){ if(num % i == 0)return false; } return true; } //約数列挙 vl enum_divisors(ll N){ vl res; for(ll i = 1; i * i <= N; ++i){ if(N % i == 0){ res.push_back(i); if(N/i != i)res.push_back(N/i); } } sort(res.begin(), res.end()); return res; } //素因数分解 vlP prime_factorize(ll N){ vlP res; for(ll a = 2; a * a <= N; ++a){ if(N % a != 0)continue; ll ex = 0; while(N % a == 0){ ++ex; N /= a; } res.push_back({a, ex}); } if(N != 1)res.push_back({N, 1}); return res; } ll count_Multiple(ll R, ll div, ll mod){ if(R == 0)return 0; ll res = R / div; if(mod <= R % div && 0 < mod)++res; return res; } //[L,R]をdivで割ったあまりがmodになる個数 ll count_Multiple(ll L, ll R, ll div, ll mod){ return count_Multiple(R, div, mod) - count_Multiple(L - 1, div, mod); } //n進数のstrをm進数に変換する string ntom(string str, const string S, const string T){ const ll n = ssize(S), m = ssize(T); vector<ll> ns(130); for(ll i = 0; i < n; ++i)ns[S[i]] = i; long long sum = 0; for(char c : str)sum = sum * n + ns[c]; string res; do{ res = T[sum % m] + res; sum /= m; }while(sum); return res; } string ntom(string str, const ll n, const ll m){ string S, T; for(ll i = 0; i < n; ++i)S.push_back((i >= 10 ? 'A' - 10 : '0') + i); for(ll i = 0; i < m; ++i)T.push_back((i >= 10 ? 'A' - 10 : '0') + i); return ntom(str, S, T); } ll ntom(ll N, const ll n, const ll m){return stoll(ntom(to_string(N), n, m));} ll popcount(ll x){ ll cnt = 0; while(x){ cnt += (x & 1); x >>= 1; } return cnt; } //RSBが何桁目にあるか -> 2で割り切れる回数 ll RSB(ll x){ ll cnt = 0; while((x & 1) == 0){ ++cnt; x >>= 1; } return cnt; } struct Vector{ ll x, y; ll cross(const Vector &other)const{ return x * other.y - y * other.x; } ll dot(const Vector &other)const{ return x * other.x + y * other.y; } }; //<AOB 0:時計 1:反時計 bool is_lessthan180(const Vector &OA, const Vector &OB, bool o){ if(o)return (OA.cross(OB) > 0); else return (OA.cross(OB) < 0); } //二次元座標上の点を反時計回りにd(rad)回転させる struct rotate_xy{ double x, y; rotate_xy(double x_, double y_) : x(x_), y(y_) {} //rad void rotate(double d){ double nx = x * cos(d) - y * sin(d); double ny = x * sin(d) + y * cos(d); x = nx, y = ny; } }; //not 1/2 ll triArea(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){ return abs((x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3)); } //string string S_lower(string &str){ for(ll i = 0; i < ssize(str); ++i)str[i] = tolower(str[i]); return str; } ll S_count(string &S, char c){ ll cnt = 0; for(char s : S)if(s == c)++cnt; return cnt; } vc<pair<char, ll>> RLE(string &S){ ll len = ssize(S); vc<pair<char, ll>> ret; for(ll i = 0; i < len;){ ll j = i + 1; while(j < len && S[i] == S[j])++j; ret.push_back({S[i], j - i}); i = j; } return ret; } string RLE_D(vc<pair<char, ll>> &ret){ string S; for(auto x : ret){ for(ll i = 0; i < x.second; ++i)S.push_back(x.first); } return S; } template<class T>string to_string(T N, ll len, char c){ string val = to_string(N); return string(len - ssize(val), c) + val; } //graphs void count_Cycles_sub(Graph &G, ll v, vb &seen, vb &finished, ll &count, bool YM, ll parent){ seen[v] = true; for(Edge &e : G[v]){ ll nv = e.to; if(!YM && nv == parent)continue; if(finished[nv])continue; if(seen[nv] && !finished[nv])++count; if(seen[nv])continue; count_Cycles_sub(G, nv, seen, finished, count, YM, v); } finished[v] = true; } //1:有向 0:無向 ll count_Cycles(Graph &G, ll s, bool YM){ ll count = 0; vb seen(ssize(G)), finished(ssize(G)); count_Cycles_sub(G, s, seen, finished, count, YM, -1); return count; } vl count_ConnectedComponents(Graph &G){ vl ans; vb seen(ssize(G)); for(ll i = 0; i < ssize(G); ++i){ if(seen[i])continue; queue<ll> que; seen[i] = true; que.push(i); while (!que.empty()) { ll v = que.front(); que.pop(); for(Edge &e : G[v]){ if (seen[e.to]) continue; seen[e.to] = true; que.push(e.to); } } ans.push_back(i); } return ans; } bool is_GraphPath(Graph &G){ ll N = ssize(G); vl val = count_ConnectedComponents(G); if(ssize(val) != 1)return false; ll o = 0, t = 0; for(ll i = 0; i < N; ++i){ if(ssize(G[i]) == 1)++o; else if(ssize(G[i]) == 2)++t; else return false; } if(o != 2 || o + t != N)return false; return true; } //s == -1 : all v vl BFS(Graph &G, ll s){ vl dist(ssize(G), -1); vl val = count_ConnectedComponents(G); for(auto p : val){ queue<ll> que; dist[(s==-1?p:s)] = 0; que.push((s==-1?p:s)); while (!que.empty()) { ll v = que.front(); que.pop(); for(const Edge &e : G[v]){ if (dist[e.to] != -1) continue; dist[e.to] = dist[v] + e.weight; que.push(e.to); } } if(s != -1)break; } return dist; } vvl BFS_grid(vs &G, ll sx, ll sy, char s, char f){ vl DX = {-1, 0, 1, 0}, DY = {0, 1, 0, -1}; ll H = ssize(G), W = ssize(G[0]); vvl dist(H, vl(W, -1)); queue<lP> que; if(s == ' '){ que.push({sx, sy}), dist[sx][sy] = 0; }else{ for(ll i = 0; i < H; ++i){ for(ll j = 0; j < W; ++j){ if(G[i][j] == s)que.push({i, j}), dist[i][j] = 0; } } } while(!que.empty()){ auto [x, y] = que.front(); que.pop(); for(ll d = 0; d < ssize(DX); ++d){ ll nx = x + DX[d], ny = y + DY[d]; if(nx < 0 || nx >= H || ny < 0 || ny >= W)continue; if(G[nx][ny] == f)continue; if(dist[nx][ny] != -1)continue; que.push({nx, ny}); dist[nx][ny] = dist[x][y] + 1; } } return dist; } vvl BFS_grid(vs &G, char f){return BFS_grid(G, 0, 0, ' ', f);} vvl BFS_grid(vs &G, char s, char f){return BFS_grid(G, -1, -1, s, f);} vvl BFS_grid(vs &G, ll sx, ll sy, char f){return BFS_grid(G, sx, sy, ' ', f);} vl dijkstra(Graph &G, ll s){ vl dist(ssize(G), INF); priority_queue<lP, vlP, greater<lP>> que; dist[s] = 0; que.push({0, s}); while (!que.empty()) { auto [d, v] = que.top(); que.pop(); if(d > dist[v])continue; for(auto &e : G[v]){ if(d + e.weight < dist[e.to]){ dist[e.to] = d + e.weight; que.push({dist[e.to], e.to}); } } } return dist; } vvl Floyd_Warshall(Graph &G){ ll N = ssize(G); vvl D(N, vl(N, INF)); for(ll i = 0; i < N; ++i){ D[i][i] = 0; for(Edge &e : G[i])D[i][e.to] = e.weight; } for(ll k = 0; k < N; ++k){ for(ll i = 0; i < N; ++i){ for(ll j = 0; j < N; ++j)chmin(D[i][j], D[i][k] + D[k][j]); } } return D; } void DFS_tree(Graph &G, ll v, ll p, ll d, vl &depth, vl &size){ depth[v] = d; for(auto &e : G[v]){ if(e.to == p)continue; DFS_tree(G, e.to, v, d + 1, depth, size); } size[v] = 1; for(auto &e : G[v]){ if(e.to == p)continue; size[v] += size[e.to]; } } vl eulerTour(Graph &G, ll s){ for(auto &v : G){ sort(v.begin(), v.end(), [](const Edge &a, const Edge &b){ return a.to < b.to; }); } vl val; function<void(ll, ll)> f = [&](ll v, ll pre){ val.push_back(v); for (auto &e : G[v]) { if (e.to != pre) { f(e.to, v); val.push_back(v); } } }; f(s, -1); return val; } //トポロジカルソートをし、辞書順最小を返す vl topological_sort(Graph &G){ ll N = ssize(G); vl indeg(N); for(ll i = 0; i < N; ++i){ for(auto &e : G[i])indeg[e.to]++; } priority_queue<ll, vl, greater<ll>> pq; for(ll i = 0; i < N; ++i){ if(indeg[i] == 0)pq.push(i); } vl val; val.reserve(N); while(!pq.empty()){ ll v = pq.top(); pq.pop(); val.push_back(v); for(auto &e : G[v]){ indeg[e.to]--; if(indeg[e.to] == 0){ pq.push(e.to); } } } if(ssize(val) != N)return {-1}; return val; } struct UnionFind{ private: vl par, rank, siz; ll cntset; public: UnionFind(ll N) : par(N), rank(N), siz(N, 1), cntset(N){ for(ll i = 0; i < N; i++) par[i] = i; } ll root(ll x){ if (par[x] == x) return x; return par[x] = root(par[x]); } bool unite(ll x, ll y){ x = root(x); y = root(y); if(x == y)return false; if(rank[x] < rank[y]){ par[x] = y; siz[y] += siz[x]; }else{ par[y] = x; siz[x] += siz[y]; if(rank[x] == rank[y])++rank[x]; } --cntset; return true; } bool same(ll x, ll y){ return root(x) == root(y); } ll size(ll x){ return siz[root(x)]; } ll countSets(){return cntset;} vvl groups(){ ll N = ssize(par); vl leader_buf(N), group_size(N); for(ll i = 0; i < N; i++){ leader_buf[i] = root(i); group_size[leader_buf[i]]++; } vvl result(N); for (ll i = 0; i < N; i++){ result[i].reserve(group_size[i]); } for (ll i = 0; i < N; i++){ result[leader_buf[i]].push_back(i); } result.erase( remove_if(result.begin(), result.end(), [&](const vl &v) { return v.empty(); }), result.end()); return result; } }; //prints template<class... A> void prints() { std::cout << '\n'; } template<class... A> void prints_rest() { std::cout << '\n'; } template<class T, class... A> void prints_rest(const T& first, const A&... rest) { std::cout << " " << first; prints_rest(rest...); } template<class T, class... A> void prints(const T& first, const A&... rest) { std::cout << first; prints_rest(rest...); } template<class T> void PrintContainer(const T &C){ cout << "[ "; for(auto c : C)cout << c << ' '; cout << "]\n"; } template<class T> void PrintContainer(const set<T> &st){ cout << "[ "; for(auto c : st)cout << c << ' '; cout << "]\n"; } template<class T> void PrintContainer(const multiset<T> &st){ cout << "[ "; for(auto c : st)cout << c << ' '; cout << "]\n"; } template<class T> void PrintContainer(const queue<T> &que){ queue<T> que_ = que; cout << "[ "; while(!que_.empty()){cout << que_.front() << ' ';que_.pop();} cout << "]\n"; } template<class T> void PrintContainer(const priority_queue<T> &pq){ priority_queue<T> pq_ = pq; cout << "[ "; while(!pq_.empty()){cout << pq_.top() << ' ';pq_.pop();} cout << "]\n"; } template<class T> void PrintContainer(const priority_queue<T, vector<T>, greater<T> > &pq){ priority_queue<T, vector<T>, greater<T> > pq_ = pq; cout << "[ "; while(!pq_.empty()){cout << pq_.top() << ' ';pq_.pop();} cout << "]\n"; } template<class T> void PrintContainer(const stack<T> &sta){ stack<T> sta_ = sta; cout << "[ "; while(!sta_.empty()){cout << sta_.top() << ' ';sta_.pop();} cout << "]\n"; } template <typename T> void print_var(const std::string& name, const T& value) { std::cout << name << ": " << value << '\n'; } std::string extract_name(const std::string& names, size_t& pos) { size_t start = pos; int brackets = 0; while (pos < names.size()) { char ch = names[pos]; if (ch == '(') ++brackets; if (ch == ')') --brackets; if (ch == ',' && brackets == 0) break; ++pos; } std::string name = names.substr(start, pos - start); name.erase(0, name.find_first_not_of(" \t")); name.erase(name.find_last_not_of(" \t") + 1); ++pos; return name; } #define DEBUG(...) prints_impl(#__VA_ARGS__, __VA_ARGS__) template <typename... Args> void prints_impl(const std::string& names, Args&&... args) { size_t pos = 0; ((print_var(extract_name(names, pos), std::forward<Args>(args))), ...); } //others //trueならcontinue bool out_grid(ll i, ll j, ll h, ll w){ return (!(0 <= i && i < h && 0 <= j && j < w)); } template<typename T> vector<T> partial_sum(vector<T> &v){ vector<T> val(ssize(v) + 1); for(ll i = 0; i < ssize(v); ++i)val[i + 1] = val[i] + v[i]; return val; } template<typename T> T median(vector<T> &A){ T N = ssize(A); sort(A.begin(), A.end()); return (N % 2 ? A[N / 2] : (A[N / 2 - 1] + A[N / 2]) / 2); } template<typename T> void vector_append(vector<T> &destination, const vector<T> &source){ ranges::copy(source, back_inserter(destination)); } struct CircularRing{ private: ll N; public: CircularRing(ll N_) : N(N_) {} //0:時計1:反時計[s, e] bool cross(ll s, ll e, ll x, ll rote){ if(rote == 0){ if(s > e)return (s <= x || x <= e); else return (s <= x && x <= e); }else{ if(s < e)return (s <= x || x <= e); else return (e <= x && x <= s); } } //0:時計1:反時計[s, e] ll dist(ll s, ll e, ll m, ll rote){ if(rote == -1 && s > e)swap(s, e); if(m == -1){ if(rote == -1){ return min(e - s, N - (e - s)); }else if(rote == 0){ if(s < e)return e - s; else return N - (s - e); }else{ if(s > e)return s - e; else return N - (e - s); } }else{ if(rote == -1){ if(e - s <= N - (e - s)){ if(s < m && m < e)return N - (e - s); else return e - s; }else{ if(e < m || m < s)return e - s; else return N - (e - s); } }else{ if(cross(s, e, m, rote))return -1; else return dist(s, e, -1, rote); } } } }; template<typename T> vector<T> press_xy(vector<T> &A){ vector<T> B = A; sort(B.begin(), B.end()); B.erase(unique(B.begin(), B.end()), B.end()); vector<T> res(ssize(A)); for(ll i = 0; i < ssize(A); ++i){ res[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin(); } return res; } //mh, Mh, mw, Mw tuple<ll, ll, ll, ll> min_rectangle(vs &G, char c){ ll H = ssize(G), W = ssize(G[0]); ll mh = INF, Mh = -INF, mw = INF, Mw = -INF; for(ll i = 0; i < H; ++i){ for(ll j = 0; j < W; ++j){ if(G[i][j] == c)chmax(Mh, i), chmin(mh, i), chmax(Mw, j), chmin(mw, j); } } return {mh, Mh, mw, Mw}; } //1:時計0:反時計 vs vector2D_rotate(vs A, bool clockwise = false, char leading = 0){ ll N = ssize(A); if(N == 0)return A; ll M = 0; for(ll i = 0; i < N; ++i)M = max(M, ll(ssize(A[i]))); vs B(M, string(N, leading)); for(ll i = 0; i < N; ++i){ for(ll j = 0; j < ssize(A[i]); ++j){ if(clockwise)B[j][N - 1 - i] = A[i][j]; else B[M - 1 - j][i] = A[i][j]; } } return B; } template <class T> void reverse(T &C, ll L, ll R){ auto itl = next(C.begin(), L); auto itr = next(C.begin(), R + 1); reverse(itl, itr); } template <class T> bool is_reverse(T &C, ll s, ll e){ ll len = e - s + 1; for(ll i = 0; i < len / 2; ++i)if(C[i + s] != C[len - i - 1 + s])return false; return true; } template <class T> bool is_reverse(T &C){return is_reverse(C, 0, ssize(C));} template<typename T> ll binary_search_index(vector<T> &C, T key){ auto it = lower_bound(C.begin(), C.end(), key); if(it != C.end() && *it == key)return (it - C.begin()); else return -1; } //v.size() == r; bool next_combination(ll n, ll r, vl &v){ ll i = ssize(v) - 1; while(i >= 0 && v[i] == i + n - r)--i; if(i < 0)return false; v[i]++; for (ll j = i + 1; j < r; j++){ v[j] = v[j - 1] + 1; } return true; } struct BIT{ private: ll n; vl a; public: BIT(ll n) : n(n), a(n + 1, 0){} void add(ll i, ll x){ i++; if(i == 0)return; for(ll k = i; k <= n; k += (k & -k))a[k] += x; } void update(ll i, ll x){add(i, x - sum(i, i));} ll sum_sub(ll i){ i++; ll s = 0; if(i == 0)return s; for(ll k = i; k > 0; k -= (k & -k)){ s += a[k]; } return s; } //[i, j] ll sum(ll i, ll j){return sum_sub(j) - sum_sub(i - 1);} ll lower_bound(ll x){ if(x <= 0){ return 0; }else{ ll i = 0; ll r = 1; while(r < n) r = r << 1; for(ll len = r; len > 0; len = len >> 1){ if(i + len < n && a[i + len] < x){ x -= a[i + len]; i += len; } } return i; } } }; ll count_inversions(vl &A){ vl B = press_xy(A); ll N = ssize(B), M = *max_element(B.begin(), B.end()); BIT tree(M + 1); ll ans = 0; for(ll i = 0; i < N; ++i){ ans += tree.sum(B[i] + 1, M); tree.add(B[i], 1); } return ans; } template<typename T> ll count_inversions(vector<T> &S, vector<T> &E){ assert(ssize(S) == ssize(E)); ll N = ssize(S); map<T, ll> mp; for(ll i = 0; i < N; ++i)mp[E[i]] = i; vl A(N); for(ll i = 0; i < N; ++i)A[i] = mp[S[i]]; return count_inversions(A); } ll count_inversions(string &S, string &E){ ll N = ssize(S); vector<char> A(N), B(N); for(ll i = 0; i < N; ++i)A[i] = S[i], B[i] = E[i]; return count_inversions(A, B); } //1-indexed struct Kthset{ private: multiset<ll>L, R; ll K; public: Kthset(ll k) : K(k){} void insert(ll v){ R.insert(v); if(ssize(L) < K){ L.insert(*R.begin()); R.erase(R.begin()); }else if(*R.begin() < *L.rbegin()){ L.insert(*R.begin()); R.erase(R.begin()); R.insert(*L.rbegin()); L.erase(--L.end()); } } void erase(ll v){ auto itl = L.find(v), itr = R.find(v); if(itl != L.end()){ L.erase(itl); }else if(itr != R.end()){ R.erase(itr); } if(ssize(L) < K && !R.empty()){ L.insert(*R.begin()); R.erase(R.begin()); } } ll getKth(){return *L.rbegin();} }; template <typename T> class TreeList{ private: struct Node{ T value; Node* left; Node* right; ll bias; ll height; ll size; Node(const T& val) : value(val), left(nullptr), right(nullptr), bias(0), height(1), size(1) {} }; Node* root; ll heightOf(Node* node){ return node ? node->height : 0; } ll sizeOf(Node* node) const{ return node ? node->size : 0; } void update(Node* node){ if (!node) return; node->height = std::max(heightOf(node->left), heightOf(node->right)) + 1; node->size = sizeOf(node->left) + sizeOf(node->right) + 1; node->bias = heightOf(node->left) - heightOf(node->right); } Node* rotateLeft(Node* node){ Node* right = node->right; node->right = right->left; right->left = node; update(node); update(right); return right; } Node* rotateRight(Node* node){ Node* left = node->left; node->left = left->right; left->right = node; update(node); update(left); return left; } Node* balance(Node* node){ if(!node)return nullptr; update(node); if(node->bias > 1){ if(node->left->bias < 0){ node->left = rotateLeft(node->left); } return rotateRight(node); } if(node->bias < -1){ if(node->right->bias > 0){ node->right = rotateRight(node->right); } return rotateLeft(node); } return node; } Node* insertRecursive(Node* node, ll index, const T& value){ if(!node)return new Node(value); ll leftSize = sizeOf(node->left); if(index <= leftSize){ node->left = insertRecursive(node->left, index, value); }else{ node->right = insertRecursive(node->right, index - leftSize - 1, value); } return balance(node); } T& getByIndexRecursive(Node* node, ll index){ if(!node) throw std::out_of_range("Index out of range"); ll leftSize = sizeOf(node->left); if(index == leftSize)return node->value; if(index < leftSize)return getByIndexRecursive(node->left, index); return getByIndexRecursive(node->right, index - leftSize - 1); } public: TreeList() : root(nullptr) {} ll count() const { return sizeOf(root); } void insert(ll index, const T& value){ if(index < 0 || index > count()){ throw std::out_of_range("Index out of range"); } root = insertRecursive(root, index, value); } T getElementAt(ll index){ if(index < 0 || index >= count()){ throw std::out_of_range("Index out of range"); } return getByIndexRecursive(root, index); } T& operator[](ll index){ if(index < 0 || index >= count()){ throw std::out_of_range("Index out of range"); } return getByIndexRecursive(root, index); } const T& operator[](ll index) const { if(index < 0 || index >= count()){ throw std::out_of_range("Index out of range"); } return getByIndexRecursive(root, index); } }; //////////////////////////////////////////////////////////////////////////////////////////////// int main(){ ll N;cin >> N; cout << "Wednesday" << '\n'; }