ABC 446

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    s[0] ^= 32;
    s = "Of" + s;
    cout << s << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;

    vvint cand(N);
    rep(i, N) {
        ll l;
        cin >> l;
        while (l--) {
            ll x;
            cin >> x;
            cand[i].push_back(x);
        }
    }

    vint ans(N);
    vint used(M + 1);
    rep(i, N) {
        for (ll x : cand[i]) {
            if (!used[x]) {
                used[x] = 1;
                ans[i] = x;
                break;
            }
        }
    }

    for (ll x : ans) cout << x << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        ll N, D;
        cin >> N >> D;
        vll A(N), B(N);
        rep(i, N) cin >> A[i];
        rep(i, N) cin >> B[i];

        // num, day
        using P = pair<ll, ll>;
        deque<P> deq;

        rep(i, N) {
            deq.push_back({A[i], i});

            ll b = B[i];
            while (b) {
                ll mi = min(b, deq.front().first);
                b -= mi;
                deq.front().first -= mi;
                if (deq.front().first == 0) deq.pop_front();
            }

            while (deq.size() && deq.front().second + D <= i) deq.pop_front();
        }

        ll ans = 0;
        for (auto [num, d] : deq) ans += num;
        cout << ans << endl;
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];

    map<ll, ll> dp;
    for (ll a : A) {
        chmax(dp[a], dp[a - 1] + 1);
    }

    ll ans = 0;
    for (auto [k, v] : dp) chmax(ans, v);
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll M, A, B;
    cin >> M >> A >> B;
    A %= M;
    B %= M;

    vvint ng(M, vint(M)), visited(M, vint(M));

    // dfs(s1, s2): s1, s2 から始めて M の倍数にならないかどうか判定
    // true  -> M の倍数にならない
    // false -> M の倍数になる
    auto dfs = [&](auto dfs, ll s1, ll s2) -> bool {
        if (s1 == 0 || s2 == 0 || ng[s1][s2]) return false;

        // NG となる状態(M の倍数となる状態)を経ずに同じ状態に戻ってきた場合は M の倍数になることはない
        if (visited[s1][s2]) {
            return true;
        }

        visited[s1][s2] = 1;
        ll s3 = (A * s2 + B * s1) % M;
        if (dfs(dfs, s2, s3)) {
            return true;
        }

        // M の倍数とならない場合はこれより前の時点で return されているのでここまで来たら NG 状態
        // 帰りがけ順に呼び出し元含めていままで通った経路はすべて NG にする
        ng[s1][s2] = 1;
        return false;
    };

    ll ans = 0;
    rep(x, M) rep(y, M) {
        if (dfs(dfs, x, y))
            ans++;
    }

    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll M, A, B;
    cin >> M >> A >> B;
    A %= M;
    B %= M;

    vvint ok(M, vint(M)), visited(M, vint(M));

    // dfs(s1, s2): s1, s2 から始めて M の倍数になるかどうか判定
    // true  -> M の倍数になる
    // false -> M の倍数にならない
    auto dfs = [&](auto dfs, ll s1, ll s2) -> bool {
        if (s1 == 0 || s2 == 0 || ok[s1][s2]) return true;

        if (visited[s1][s2]) {
            return false;
        }

        visited[s1][s2] = 1;
        ll s3 = (A * s2 + B * s1) % M;
        return ok[s1][s2] = dfs(dfs, s2, s3);
    };

    ll ans = 0;
    rep(x, M) rep(y, M) {
        if (!dfs(dfs, x, y))
            ans++;
    }

    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll M, A, B;
    cin >> M >> A >> B;

    auto nx = [&](int s2, int s1) -> int {
        return (A * s2 + B * s1) % M;
    };

    auto id = [&](int s2, int s1) -> int {
        return s2 * M + s1;
    };

    vvint graph(M * M);
    rep(s1, M) rep(s2, M) {
        int s3 = nx(s2, s1);
        graph[id(s3, s2)].push_back(id(s2, s1));
    }

    vint visited(M * M);
    auto dfs = [&](auto dfs, int s3, int s2) -> void {
        if (visited[id(s3, s2)]) return;
        visited[id(s3, s2)] = 1;

        for (int p : graph[id(s3, s2)]) {
            int y = p / M;
            int x = p % M;
            dfs(dfs, y, x);
        }
    };

    rep(i, M) {
        dfs(dfs, i, 0);
        dfs(dfs, 0, i);
    }

    ll ans = 0;
    rep(i, M) rep(j, M) ans += visited[id(i, j)] == 0;
    cout << ans << endl;
}