#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //#include //#include //#include //#include //#include //#include //#include //using namespace atcoder; using namespace std; // マクロ&定数&関数 ================================================ typedef int Int; typedef int INt; typedef unsigned int uint; typedef long long ll; typedef long double ld; typedef pair pll; typedef pair pint; typedef vector vint; typedef vector vll; typedef vector vdouble; typedef vector vbool; typedef vector vstring; typedef vector> vpint; typedef vector> vpll; typedef vector> vpdouble; typedef vector> vvint; typedef vector> vvll; typedef vector vvpint; typedef vector vvpll; typedef vector> vvdouble; typedef vector> vvstring; typedef vector> vvbool; typedef vector>> vvvll; typedef vector>> vvvpll; typedef vector>> vvvbool; typedef vector>> vvvdouble; typedef vector>>> vvvvdouble; const ll LLINF = 1e18 + 1; const int DX[9] = { 0, 0, 1, -1, 1, 1, -1, -1, 0 }; // 4;4近傍 const int DY[9] = { 1, -1, 0, 0, 1, -1, 1, -1, 0 }; // 8:8近傍 9:(0,0)を含む const double PI = 3.14159265358979323846264338327950288; const double EPS = 1e-7; //VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV const ll MOD = 1000000007; //10^9 + 7 //VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV templatebool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } else return false; } templatebool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } else return false; } //--------------------------------------------------------------- // オーバーフローチェック //--------------------------------------------------------------- bool is_overflow(ll a, ll b) { ll M = numeric_limits::max(); return (a >= M / b); } //--------------------------------------------------------------- // 整数の乱数生成 //--------------------------------------------------------------- ll random_int(ll start, ll last) { return start + rand() % (last - start + 1); } //--------------------------------------------------------------- // 2次元配列の表示(デバッグ用) //--------------------------------------------------------------- template void print2D(vector> A) { for (vector aa : A) { for (T a : aa) cout << a << " "; cout << endl; } cout << endl; } //--------------------------------------------------------------- // x∈[a, b) //--------------------------------------------------------------- bool is_in(ll x, ll a, ll b) { return (a <= x && x < b); } //--------------------------------------------------------------- // 文字系 → 整数 //--------------------------------------------------------------- ll to_int(string S) { return stoll(S); } ll to_int(char c) { return int(c) - int('0'); } ll to_int(const char *c) { return atoi(c); } //--------------------------------------------------------------- // 2次元累積和 (ゼロパディング有り) //--------------------------------------------------------------- template vector> get_accum(vector> A) { T H = A.size(); T W = A[0].size(); vector> accum(H + 1, vector(W + 1, 0)); for (int h = 0; h < H; h++) for (int w = 0; w < W; w++) accum[h + 1][w + 1] = A[h][w]; for (int h = 0; h <= H; h++) for (int w = 0; w < W; w++) accum[h][w + 1] += accum[h][w]; for (int h = 0; h < H; h++) for (int w = 0; w <= W; w++) accum[h + 1][w] += accum[h][w]; return accum; } //--------------------------------------------------------------- // 約数列挙 O(√N) //--------------------------------------------------------------- vll divisor(ll n) { vll ret; for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i); if (i * i != n) ret.push_back(n / i); } } sort(begin(ret), end(ret)); return (ret); } //--------------------------------------------------------------- // N未満のすべての素数判定(エラトステネスの篩) //--------------------------------------------------------------- vbool searchSosuu(ll N) { vbool sosuu; for (ll i = 0; i < N; i++) { sosuu.emplace_back(true); } sosuu[0] = false; sosuu[1] = false; for (ll i = 2; i < N; i++) { if (sosuu[i]) { for (ll j = 2; i * j < N; j++) { sosuu[i * j] = false; } } } return sosuu; } //--------------------------------------------------------------- // 素因数分解 O(√N) //--------------------------------------------------------------- vpll to_prime(ll n) { vpll prime_factor; for (ll i = 2; i * i <= n; i++) { ll count = 0; while (n % i == 0) { count++; n /= i; } if (count) { pair temp = { i, count }; prime_factor.emplace_back(temp); } } if (n != 1) { pair temp = { n, 1 }; prime_factor.emplace_back(temp); } return prime_factor; } //--------------------------------------------------------------- // 高速素因数分解(前処理O(N), 分解O(logN)) //--------------------------------------------------------------- class FastPrime { public: vll div; // i の約数のうちの1つ。 vbool is_sosuu; // i が素数であるか。 FastPrime(ll N) : div(N + 10, -1), is_sosuu(N + 10, true) { for (ll i = 2; i < N; i++) if (div[i] == -1) for (ll j = 2; i * j <= N; j++) { div[i * j] = i; is_sosuu[i * j] = false; } } vpll to_prime(ll N) { if (N == 1) return vpll({}); vll divs; while (div[N] != -1) { divs.emplace_back(div[N]); N /= div[N]; } if (N > 1) divs.emplace_back(N); sort(divs.begin(), divs.end()); vpll primes; ll count = 1; for (int i = 1; i < divs.size(); i++) { if (divs[i] > divs[i - 1]) { primes.emplace_back(pll(divs[i - 1], count)); count = 0; } count++; } primes.emplace_back(pll(divs[divs.size() - 1], count)); return primes; } }; //--------------------------------------------------------------- // 最大公約数(ユークリッドの互除法) //--------------------------------------------------------------- ll gcd(ll a, ll b) { if (a < b) { ll tmp = a; a = b; b = tmp; } ll r = a % b; while (r != 0) { a = b; b = r; r = a % b; } return b; } //--------------------------------------------------------------- // 約分 //--------------------------------------------------------------- pll reduce(ll a, ll b) { ll g = gcd(a, b); return pll(a / g, b / g); } //--------------------------------------------------------------- // 最小公倍数 //--------------------------------------------------------------- ll lcm(ll a, ll b) { ll temp = gcd(a, b); return temp * (a / temp) * (b / temp); } //--------------------------------------------------------------- // 階乗 //--------------------------------------------------------------- ll factorial(ll n, ll mod = MOD) { if (n <= 1) { return 1; }return (n * (factorial(n - 1))) % mod; } //--------------------------------------------------------------- // 高速コンビネーション計算(前処理:O(N) 計算:O(1)) //--------------------------------------------------------------- // テーブルを作る前処理 ll comb_const = 3000005; vll fac(comb_const), finv(comb_const), inv(comb_const); bool COMineted = false; void COMinit(ll mod = MOD) { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (ll i = 2; i < comb_const; i++) { fac[i] = fac[i - 1] * i % mod; inv[i] = mod - inv[mod % i] * (mod / i) % mod; finv[i] = finv[i - 1] * inv[i] % mod; } COMineted = true; } // 二項係数計算 ll COM(ll n, ll k, ll mod = MOD) { if (COMineted == false) COMinit(mod); if (n < k) return 0; if (n < 0 || k < 0) return 0; return (fac[n] * (finv[k] * finv[n - k] % mod)) % mod; } //--------------------------------------------------------------- // 繰り返し2乗法 base^sisuu //--------------------------------------------------------------- ll RepeatSquaring(ll base, ll sisuu, ll mod = MOD) { if (sisuu < 0) { cout << "RepeatSquaring: 指数が負です!" << endl; return 0; } if (sisuu == 0) return 1; if (sisuu % 2 == 0) { ll t = RepeatSquaring(base, sisuu / 2, mod) % mod; return (t * t) % mod; } return (base * RepeatSquaring(base, sisuu - 1, mod)) % mod; } //--------------------------------------------------------------- // 高速単発コンビネーション計算(O(logN)) //--------------------------------------------------------------- ll fast_com(ll a, ll b, ll mod = MOD) { ll bunshi = 1; ll bunbo = 1; for (ll i = 1; i <= b; i++) { bunbo *= i; bunbo %= mod; bunshi *= (a - i + 1); bunshi %= mod; } ll ret = bunshi * RepeatSquaring(bunbo, mod - 2, mod); ret %= mod; while (ret < 0) { ret += mod; } return ret; } //--------------------------------------------------------------- // 整数をビットのリストに変換する ll->vbool //--------------------------------------------------------------- vbool to_bitlist(ll bit, ll fixed_size = 1) { if (bit == 0) return vbool(fixed_size, 0); vbool list; while (bit > 0) { list.emplace_back(bit & 1); bit /= 2; } while (list.size() < fixed_size) { list.emplace_back(0); } return list; } //--------------------------------------------------------------- // 立っているビットの数をカウントする //--------------------------------------------------------------- ll bit_count(ll bit) { ll ret = 0; while (bit) { ret += bit % 2; bit /= 2; } return ret; } //--------------------------------------------------------------- // XORの階乗 0^1^...^N (O(1)) //--------------------------------------------------------------- ll xor_fac(ll N) { if (N == 0) return 0; ll n_pair = (N - 1) / 2; ll n_one = n_pair + 1; if (n_pair * 2 + 1 == N) { return n_one % 2; } else { return (n_one % 2) ^ N; } } //--------------------------------------------------------------- // 座標圧縮(O(NlogN)) 0スタートになることに注意! //--------------------------------------------------------------- class PosPress { public: vll pressed; map func; // 圧縮後を知りたい map rev; // 圧縮前を知りたい PosPress(vll P) { pressed = P; sort(P.begin(), P.end()); func[P[0]] = 0; rev[0] = P[0]; ll next = 1; for (int i = 1; i < P.size(); i++) { if (P[i] != P[i - 1]) { func[P[i]] = next; rev[next] = P[i]; next++; } } for (int i = 0; i < P.size(); i++) { pressed[i] = func[pressed[i]]; } } }; //--------------------------------------------------------------- // 行列積(O(N^3)) //--------------------------------------------------------------- vvll mat_cross(vvll A, vvll B) { ll N = A.size(); ll K = B.size(); ll M = B[0].size(); vvll C(N, vll(M)); // 行列積の計算(+, * は |, & でもOK) for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) for (int k = 0; k < K; k++) C[i][j] += A[i][k] * B[k][j]; return C; } //--------------------------------------------------------------- // 2直線の交差判定(直線(x1, y1)->(x2, y2) と 直線(X1, Y1)->(X2, Y2)) //--------------------------------------------------------------- bool is_cross(ll x1, ll y1, ll x2, ll y2, ll X1, ll Y1, ll X2, ll Y2) { ll dx_ai = X1 - x1; ll dy_ai = Y1 - y1; ll dx_bi = X1 - x2; ll dy_bi = Y1 - y2; ll dx_ai2 = X2 - x1; ll dy_ai2 = Y2 - y1; ll dx_bi2 = X2 - x2; ll dy_bi2 = Y2 - y2; ll si = dx_ai * dy_bi - dy_ai * dx_bi; ll si2 = dx_ai2 * dy_bi2 - dy_ai2 * dx_bi2; ll si3 = dx_ai * dy_ai2 - dy_ai * dx_ai2; ll si4 = dx_bi * dy_bi2 - dy_bi * dx_bi2; return (si * si2 < 0 && si3 * si4 < 0); } //--------------------------------------------------------------- // 最長増加部分列の長さ(O(NlogN)) //--------------------------------------------------------------- ll LSI(vll vec) { ll size = vec.size(); vll lsi(size + 1, LLINF); // 長さjを作った時の右端の最小値 lsi[0] = 0; lsi[1] = vec[0]; for (ll i = 1; i < size; i++) { // 初めてvec[i]の方が小さくなるところを探す auto Iter = lower_bound(lsi.begin(), lsi.end(), vec[i]); ll idx = Iter - lsi.begin(); if (idx > 0 && lsi[idx - 1] < vec[i]) { lsi[idx] = vec[i]; } } for (ll i = size; i >= 0; i--) { if (lsi[i] < LLINF) { return i; } } } //--------------------------------------------------------------- // LCS(最長共通部分列) O(|S||T|) //--------------------------------------------------------------- string LCS(string S, string T) { vvll dp(S.length() + 1); for (int i = 0; i < dp.size(); i++) { vll t(T.length() + 1, 0); dp[i] = t; } for (int i = 0; i < S.length(); i++) { for (int j = 0; j < T.length(); j++) { dp[i + 1][j + 1] = max({ dp[i][j] + ll(S[i] == T[j]), dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1] }); } } ll len = dp[S.length()][T.length()]; string ans = ""; ll i = dp.size() - 1; ll j = dp[0].size() - 1; while (len > 0) { if (dp[i - 1][j] == len) { i--; } else if (dp[i][j - 1] == len) { j--; } else { ans += S[i - 1]; i--; j--; len--; } } reverse(ans.begin(), ans.end()); return ans; } vll LCS(vll S, vll T) { vvll dp(S.size() + 1); for (int i = 0; i < dp.size(); i++) { vll t(T.size() + 1, 0); dp[i] = t; } for (int i = 0; i < S.size(); i++) { for (int j = 0; j < T.size(); j++) { dp[i + 1][j + 1] = max({ dp[i][j] + ll(S[i] == T[j]), dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1] }); } } ll len = dp[S.size()][T.size()]; vll ans; ll i = dp.size() - 1; ll j = dp[0].size() - 1; while (len > 0) { if (dp[i - 1][j] == len) { i--; } else if (dp[i][j - 1] == len) { j--; } else { ans.emplace_back(S[i - 1]); i--; j--; len--; } } reverse(ans.begin(), ans.end()); return ans; } //--------------------------------------------------------------- // 木の根からの深さ //--------------------------------------------------------------- vll tree_depth(vvll edge, ll root) { ll n_node = edge.size(); vll dist(n_node, LLINF); dist[root] = 0; stack S; S.push({ root, 0 }); while (!S.empty()) { ll node = S.top().first; ll d = S.top().second; dist[node] = d; S.pop(); for (int i = 0; i < edge[node].size(); i++) { if (dist[edge[node][i]] == LLINF) { S.push({ edge[node][i], d + 1 }); } } } return dist; } //--------------------------------------------------------------- // ワーシャルフロイド法(O(N^3)) d: 正方行列(N*N) //--------------------------------------------------------------- vvll warshall_floyd(vvll d) { ll n = d.size(); for (int k = 0; k < n; k++) { // 経由する頂点 for (int i = 0; i < n; i++) { // 始点 for (int j = 0; j < n; j++) { // 終点 d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } return d; } //--------------------------------------------------------------- // Union Find //--------------------------------------------------------------- class UnionFind { private: vll siz; // 素集合のサイズを表す配列(1 で初期化) public: ll n_group; // 集合の数 vll par; // 各元の親を表す配列 // Constructor UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) { for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 n_group = sz_; } void init(ll sz_) { par.resize(sz_); siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかった for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } // Member Function // Find ll root(ll x) { // 根の検索 while (par[x] != x) { x = par[x] = par[par[x]]; // x の親の親を x の親とする } return x; } // Union(Unite, Merge) bool merge(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; // merge technique(データ構造をマージするテク.小を大にくっつける) if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; n_group--; return true; } // 連結判定 bool issame(ll x, ll y) { return root(x) == root(y); } // x を含むグループの大きさ ll size(ll x) { return siz[root(x)]; } }; //--------------------------------------------------------------- // ダイクストラ(O(ElogV)) edge: 隣接リスト from->pair{to, cost} //--------------------------------------------------------------- class Dijkstra { private: vll past; // (iまで最短で行くときの一つ前) public: vll dist; // iまでの最短距離 // edge[i] -> {to, cost} Dijkstra(vvpll edge, ll start) : dist(edge.size(), LLINF), past(edge.size(), -1) { using Pi = pll; priority_queue< Pi, vector< Pi >, greater< Pi > > que; dist[start] = 0; que.emplace(dist[start], start); while (!que.empty()) { ll cost; int idx; tie(cost, idx) = que.top(); que.pop(); if (dist[idx] < cost) continue; for (int i = 0; i < edge[idx].size(); i++) { ll next_cost = cost + edge[idx][i].second; if (dist[edge[idx][i].first] <= next_cost) continue; dist[edge[idx][i].first] = next_cost; past[edge[idx][i].first] = idx; que.emplace(dist[edge[idx][i].first], edge[idx][i].first); } } } // goalまでの最短経路 vll shortest(ll goal) { vll ret; while (goal != -1) { ret.emplace_back(goal); goal = past[goal]; } reverse(ret.begin(), ret.end()); return ret; } }; //--------------------------------------------------------------- // LCA: 最近共通祖先 (O()) //--------------------------------------------------------------- class Lca { private: vvll doubling; ll n_bit = 30; public: vll depth; // 根0からiまでの最短距離 // edge[i] -> {to, cost} Lca(vvll edge, ll root = 0) : doubling(50, vll(edge.size(), -1)) { // 深さ depth = tree_depth(edge, root); // ダブリングで親を辿れるようにする // jから2^i回親を辿ったノード doubling[0][0] = -1; for (int i = 1; i < edge.size(); i++) for (int j : edge[i]) if (depth[i] > depth[j]) { doubling[0][i] = j; break; } for (int i = 1; i < n_bit; i++) for (int j = 0; j < edge.size(); j++) { if (doubling[i - 1][j] != -1) doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]; else doubling[i][j] = -1; } } // aとbの最近共通祖先 ll get_lca(ll a, ll b) { // depth[a] >= depth[b]にする if (depth[a] < depth[b]) swap(a, b); ll oa = a; ll ob = b; ll d = depth[a] - depth[b]; // aをdだけさかのぼる。 vbool bit = to_bitlist(d, n_bit); for (int i = 0; i < n_bit; i++)if (bit[i]) a = doubling[i][a]; // depth[a] == depth[b]になっている。 for (int i = n_bit - 1; i >= 0; i--) { if (doubling[i][a] == doubling[i][b]) continue; a = doubling[i][a]; b = doubling[i][b]; } return a == b ? a : doubling[0][a]; } // パスの長さ ll path_len(ll a, ll b) { return depth[a] + depth[b] - 2 * depth[get_lca(a, b)]; } // パスに含まれる頂点集合 vll nodes_on_path(ll a, ll b) { if (a == b) return vll({ a }); vll ret; ll lca = get_lca(a, b); while (a != lca) { ret.emplace_back(a); a = doubling[0][a]; } while (b != lca) { ret.emplace_back(b); b = doubling[0][b]; } ret.emplace_back(lca); return ret; } }; //--------------------------------------------------------------- // Z-algorithm(SとS[i:]の最長接頭辞長) O(|S|) //--------------------------------------------------------------- vll Zalgorithm(string S) { ll n = S.size(); vll Z(n, 0); ll start = -1; ll last = -1; for (ll i = 1; i < n; i++) { if (start >= 0) { Z[i] = min(Z[i - start], last - i); chmax(Z[i], 0LL); } while (i + Z[i] < S.size() && S[Z[i]] == S[i + Z[i]]) Z[i] ++; if (last < i + Z[i]) { last = i + Z[i]; start = i; } } Z[0] = n; return Z; } vll Zalgorithm(vll S) { ll n = S.size(); vll Z(n, 0); ll start = -1; ll last = -1; for (ll i = 1; i < n; i++) { if (start >= 0) { Z[i] = min(Z[i - start], last - i); chmax(Z[i], 0LL); } while (i + Z[i] < S.size() && S[Z[i]] == S[i + Z[i]]) Z[i] ++; if (last < i + Z[i]) { last = i + Z[i]; start = i; } } Z[0] = n; return Z; } //--------------------------------------------------------------- // 二部グラフ判定(O(E)) edge -> リスト //--------------------------------------------------------------- class Bipartite { private: ll N; public: vll color; // 2色に塗り分けた時の塗り分け方 bool is_bipartite; // 2部グラフであるか Bipartite(vvll edge) : color(edge.size(), -1) { N = edge.size(); color[0] = 0; queue Q; Q.push(0); while (!Q.empty()) { ll now = Q.front(); Q.pop(); for (int i : edge[now]) { if (color[i] == -1) { color[i] = (color[now] == 0 ? 1 : 0); Q.push(i); } else if (color[i] == color[now]) { is_bipartite = false; return; } } } is_bipartite = true; } }; //--------------------------------------------------------------- // ダブリング (行先のリスト, コスト) ← コストは任意 //--------------------------------------------------------------- class Doubling { private: ll M = 100; vvll doubling; vvll cost; bool have_cost = false; public: // to[i]: i から1回移動した先 // fee[i]: i から to[i]へと移動するコスト(任意) Doubling(vll to, vll fee = {}) : doubling(M, vll(to.size(), -1)), cost(M, vll(to.size(), 0)) { ll N = to.size(); have_cost = fee.size() > 0; for (int i = 0; i < N; i++) { doubling[0][i] = to[i]; if (have_cost) cost[0][i] = fee[i]; } for (int i = 1; i < M; i++) { for (int j = 0; j < N; j++) { doubling[i][j] = doubling[i - 1][doubling[i - 1][j]]; if (have_cost) cost[i][j] = cost[i - 1][j] + cost[i - 1][doubling[i - 1][j]]; } } } // from から K 回移動した先 ll destination(ll from, ll K) { vbool bits = to_bitlist(K); ll now = from; ll sum = 0; for (int i = 0; i < bits.size(); i++) { if (bits[i]) { now = doubling[i][now]; } } return now; } // from から K 回移動するコストの合計 ll get_cost(ll from, ll K) { vbool bits = to_bitlist(K); ll now = from; ll sum = 0; for (int i = 0; i < bits.size(); i++) { if (bits[i]) { sum += cost[i][now]; now = doubling[i][now]; } } return sum; } }; //--------------------------------------------------------------- // ベルマンフォード(O(EV)) edge, from, to -> (cost, have_neg_roop) //--------------------------------------------------------------- pair BelmanFord(vvpll edge, ll from, ll to) { ll N = edge.size(); //頂点の数 vll d(N, LLINF); //始点から添え字の頂点に行くのにかかるコスト d[from] = 0; //始点を0にする bool have_negroop = false; for (ll i = 0; i < N; i++) { for (ll j = 0; j < N; j++) { for (int k = 0; k < edge[j].size(); k++) { ll from = j; ll to = edge[j][k].first; ll cost = edge[j][k].second; if (d[to] > d[from] + cost) { //移動した後のコストが小さいと、頂点のコストを更新 d[to] = d[from] + cost; //頂点の数と同じ回数ループすると、負の閉路があるのでループをぬける if (i == N - 1) { have_negroop = true; break; } } } } } return pll(d[to], have_negroop); } //--------------------------------------------------------------- // 遅延セグ木(構築O(N), 更新・取得(logN)) //--------------------------------------------------------------- /* <コンストラクタ> lazy_segtree seg(A); <構築> (pos に x を代入) seg.set(int pos, ll x); <単一取得> seg.get(int pos); <区間取得> ([l, r)を取得) seg.prod(int l, int r); <全区間取得> seg.all_prod(); <更新> seg.apply(int pos, ll x); seg.apply(int l, int r, ll x); <二分探索> (g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最大の r) seg.max_right(int l); <二分探索> (g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小の l) seg.min_left(int r); */ template struct lazy_segtree { private: int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } public: lazy_segtree() : lazy_segtree(0) {} lazy_segtree(int n) : lazy_segtree(std::vector(n, e())) {} lazy_segtree(const std::vector &v) : _n(int(v.size())) { log = ceil_pow2(_n); size = 1 << log; d = std::vector(2 * size, e()); lz = std::vector(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push(r >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; std::vector lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; // モノイドの型 //struct S { // ll value; // 値 // int size; // 区間の大きさ //}; // //// 写像の定義(data部分に用いる関数, 区間の合成) //S op(S l, S r) { return S{ max(l.value, r.value), l.size + r.size }; } // //// 単位元 //S e() { return S{ 0, 0 }; } // //// F(x) (遅延評価するときの関数・加算or代入, lazyのretへの当て方) //S mapping(ll f, S x) { return S{ max(x.value, f), x.size }; } // //// 作用素(lazy同士)の合成 //ll composition(ll l, ll r) { return max(l, r); } // //// lazyの単位元 //ll id() { return 0; } // //// 二分探索の関数 //ll V; //bool g(S v) { // return V > v.value; //} int main() { //////================================== cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(25); //////================================== /*    ~思いついたことはとりあえず絶対メモする!!~      ~オーバーフローに注意!!!~ */ ll N; cin >> N; vll grundy(N + 10, 0); for (int i = 1; i <= N; i++) { vbool used(N + 10, false); used[grundy[i / 2] ^ grundy[i - (i / 2)]] = true; if(i % 3 == 0) used[grundy[i / 3]] = true; if (i % 3 == 1) used[grundy[i / 3 + 1]] = true; if (i % 3 == 2) used[grundy[i / 3]] = true; for (int j = 0; j < N + 10; j++) { if (!used[j]) { grundy[i] = j; break; } } } cout << (grundy[N] != 0 ? "A" : "B") << endl; }