結果

問題 No.8115 What day of week is it in N days?
ユーザー はまー01
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

#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';
}
0