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

    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];
    vint depth(N);
    vll B(N);
    B[0] = A[0];
    rep2(i, 1, N) {
        int p;
        cin >> p;
        p--;
        depth[i] = depth[p] + 1;
        B[depth[i]] += A[i];
    }

    string ans = "0";
    for (int i = N - 1; i >= 0; i--) {
        if (B[i] == 0)
            continue;
        if (B[i] < 0)
            ans = "-";
        if (B[i] > 0)
            ans = "+";
        break;
    }
    cout << ans << endl;
}

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

    int N, M;
    cin >> N >> M;
    vvll A(M);
    rep(i, M) {
        int K;
        cin >> K;
        rep(j, K) {
            ll a;
            cin >> a;
            a--;
            A[i].push_back(a);
        }
    }

    vll B(N);
    rep(i, N) {
        cin >> B[i];
        B[i]--;
    }

    // shokuzai[i]: 食材 i を使っている料理の番号
    vvll shokuzai(N);
    rep(i, M) {
        for (ll a : A[i]) {
            shokuzai[a].push_back(i);
        }
    }

    // nums[i]: 料理 i に含まれる苦手な食材の数
    vll nums(M, 0);
    rep(i, M) nums[i] = A[i].size();

    ll ans = 0;
    for (ll b : B) {
        for (ll i : shokuzai[b]) {
            nums[i]--;
            if (nums[i] == 0)
                ans++;
        }
        cout << ans << endl;
    }
}

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

    ll n, m;
    cin >> n >> m;
    vll a(n), b(n), c(n);
    rep(i, n) cin >> a[i] >> b[i] >> c[i];

    vector<vector<pair<ll, ll>>> lec(5001);
    rep(i, n) {
        lec[b[i]].push_back({a[i], c[i]});
    }

    vvll dp(5001, vll(m + 1, INF));
    dp[0][0] = 0;
    rep2(i, 1, 5001) {
        rep(j, m + 1) {
            // i 限目の科目を取らない場合
            chmin(dp[i][j], dp[i - 1][j]);

            // i 限目の科目を取る場合
            rep(k, lec[i].size()) {
                chmin(dp[i][j], dp[i - 1][max(0ll, j - lec[i][k].second)] + lec[i][k].first);
            }
        }
    }

    ll ans = dp[5000][m];
    if (ans == INF)
        ans = -1;
    cout << ans << endl;
}

vector<pair<char, int>> runLengthEncode(const string& input) {
    vector<pair<char, int>> encoded;
    int size = input.size();
    for (int i = 0; i < size; ++i) {
        int count = 1;
        while (i + 1 < size && input[i] == input[i + 1]) {
            ++i;
            ++count;
        }
        encoded.emplace_back(input[i], count);
    }
    return encoded;
}

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

    ll N, K;
    string S;
    cin >> N >> K >> S;

    rep(i, N) {
        if (i + 1 < N && S[i] == '?' && S[i + 1] == 'o') {
            S[i] = '.';
        }
        if (i + 1 < N && S[i] == 'o' && S[i + 1] == '?') {
            S[i + 1] = '.';
        }
    }

    int no = 0;
    for (char c : S)
        if (c == 'o')
            no++;
    if (no == K) {
        rep(i, N) if (S[i] == '?') S[i] = '.';
        cout << S << endl;
        return;
    }

    auto ps = runLengthEncode(S);
    int m = 0;
    for (auto [c, num] : ps) {
        if (c == 'o')
            m += num;
        if (c == '?')
            m += (num + 1) / 2;
    }

    if (m > K) {
        cout << S << endl;
        return;
    }

    for (auto [c, num] : ps) {
        if (c != '?') {
            rep(i, num) cout << c;
            continue;
        }

        if (num % 2 == 0) {
            rep(i, num) cout << '?';
        } else {
            rep(i, num) {
                cout << (i % 2 == 0 ? 'o' : '.');
            }
        }
    }
    cout << endl;
}

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

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

    set<ll> check, stock;
    stock.insert(0);

    while ((int)check.size() != K + 1) {
        auto it = stock.begin();
        ll x = *it;
        stock.erase(it);

        check.insert(x);
        for (ll a : A)
            stock.insert(x + a);
    }
    cout << *check.rbegin() << endl;
}

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

    int N, M, K;
    cin >> N >> M >> K;
    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vll powers(N, -1);
    rep(i, K) {
        int p, h;
        cin >> p >> h;
        p--;
        powers[p] = h;
    }

    // power, node id
    using P = pair<ll, int>;
    priority_queue<P> pq;
    rep(i, N) {
        if (powers[i] > 0)
            pq.push({powers[i], i});
    }

    while (pq.size()) {
        auto [power, id] = pq.top();
        pq.pop();

        if (powers[id] > power)
            continue;

        for (int nx : graph[id]) {
            if (powers[nx] >= power - 1)
                continue;
            powers[nx] = power - 1;
            pq.push({powers[nx], nx});
        }
    }

    vint ans;
    rep(i, N) {
        if (powers[i] >= 0)
            ans.push_back(i + 1);
    }
    cout << ans.size() << endl;
    print(ans);
}

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

    int n, k;
    cin >> n >> k;
    vll a(n);
    rep(i, n) cin >> a[i];

    vint v;

    auto dfs = [&](auto dfs, int used) -> void {
        if (__builtin_popcount(used) == k) {
            v.push_back(used);
            return;
        }

        int id = -1;
        rep(i, n) {
            if ((used >> i) & 1)
                id = i;
        }
        rep2(i, id + 1, n) {
            dfs(dfs, used | (1 << i));
        }
    };

    dfs(dfs, 0);

    ll ans = 0;
    for (int used : v) {
        rep(i, n) {
            if ((used >> i) & 1)
                ans += a[i];
        }
    }
    cout << ans << endl;
}

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

    int N;
    cin >> N;
    vint A(N);
    rep(i, N) cin >> A[i];

    map<int, vint> mp;
    rep(i, N) {
        mp[A[i]].push_back(i);
    }

    int cnt = 1;
    vint ans(N);
    for (auto it = mp.begin(); it != mp.end(); it++) {
        auto [_, ids] = *it;
        for (int id : ids) {
            ans[id] = cnt++;
        }
    }
    print(ans);
}

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

    int N, M;
    cin >> N >> M;
    vvint as(M), bs(M);
    rep(i, M) {
        int k;
        cin >> k;
        rep(j, k) {
            int a, b;
            cin >> a >> b;
            a--;
            as[i].push_back(a);
            bs[i].push_back(b);
        }
    }

    rep(t, 1 << N) {
        vint xs;
        rep(i, N) {
            xs.push_back((t >> i) & 1);
        }

        int cnt = 0;
        rep(i, M) {
            int ok = 0;
            int ki = as[i].size();
            rep(j, ki) {
                if (xs[as[i][j]] == bs[i][j])
                    ok = 1;
            }
            if (ok)
                cnt++;
        }

        if (cnt == M) {
            yesno(true);
            return;
        }
    }
    yesno(false);
}

// DP 解放
void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    int n = S.size();
    if (n == 1) {
        yesno(true);
        return;
    }

    vint v(n);
    rep(i, n) {
        v[i] = S[i] - '0';
    }

    vvint dp(n + 1, vint(10, INF));
    rep2(i, 1, 10) {
        if (v[0] != i)
            dp[0][i] = 1;
        else
            dp[0][i] = 0;
    }

    rep2(i, 1, n) {
        rep(j, 10) {
            int change = v[i] != j;
            if (j - 1 >= 0) {
                chmin(dp[i][j], dp[i - 1][j - 1] + change);
            }
            if (j + 1 <= 9) {
                chmin(dp[i][j], dp[i - 1][j + 1] + change);
            }
            chmin(dp[i][j], dp[i - 1][j] + change);
        }
    }

    int ok = 0;
    rep(i, 10) {
        if (dp[n - 1][i] <= 1)
            ok = 1;
    }
    yesno(ok);
}

// 全探索解法
void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    int n = S.size();

    vint v(n);
    rep(i, n) {
        v[i] = S[i] - '0';
    }

    auto check = [](vint& v) -> bool {
        bool ok = true;
        int n = v.size();
        if (n == 1)
            return true;

        if (v[0] == 0)
            return false;

        rep(i, n - 1) {
            if (abs(v[i] - v[i + 1]) > 1)
                ok = false;
        }

        return ok;
    };

    rep(i, n) {
        vint t = v;
        rep(j, 10) {
            t[i] = j;
            if (check(t)) {
                yesno(true);
                return;
            }
        }
    }

    yesno(false);
}

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

    int N;
    string S;
    cin >> N >> S;

    S = "_" + S;

    vll C(N + 1), D(N + 1);
    rep(i, N) cin >> C[i + 1];
    rep(i, N) cin >> D[i + 1];

    // dp[i][j]: i 文字目まで見たときの、対応が取れていない左カッコの数が j のときの最小コスト
    vvll dp(N + 1, vll(N + 1, INF));
    dp[0][0] = 0;
    rep2(i, 1, N + 1) {
        rep(j, N) {
            if (S[i] == '(') {
                chmin(dp[i][j + 1], dp[i - 1][j]);

                // 反転
                if (j - 1 >= 0)
                    chmin(dp[i][j - 1], dp[i - 1][j] + C[i]);
            } else {
                if (j - 1 >= 0)
                    chmin(dp[i][j - 1], dp[i - 1][j]);

                // 反転
                chmin(dp[i][j + 1], dp[i - 1][j] + C[i]);
            }

            // i 番目の要素を削除
            chmin(dp[i][j], dp[i - 1][j] + D[i]);
        }
    }
    cout << dp[N][0] << endl;
}

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

    int n;
    cin >> n;
    vector<pair<int, int>> ps(n);
    rep(i, n) {
        int x;
        cin >> x;
        ps[i].first = x;
    }
    rep(i, n) {
        int x;
        cin >> x;
        ps[i].second = x;
    }

    sort(all(ps));

    ll ans = n;
    vint v(n + 1, INF);
    rep(i, n) {
        auto it = upper_bound(all(v), ps[i].second);
        *it = ps[i].second;
    }

    ans += lower_bound(all(v), INF) - v.begin();
    cout << ans << endl;
}

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

    int n;
    cin >> n;
    vll a(n + 1);
    rep(i, n) cin >> a[i + 1];

    // dp[i][j]: i 回目の操作で操作 j を行ったときの S の総和の最大値
    // j = 0: 何もしない
    // j = 1: a[i] を入れる
    vvll dp(n + 1, vll(2, -INF));
    dp[0][1] = 0;
    rep2(i, 1, n + 1) {
        chmax(dp[i][1], dp[i - 1][1] + a[i]);
        chmax(dp[i][1], dp[i - 1][0] + a[i]);
        if (i - 2 >= 0) {
            // i-1 回目で要素を入れて、i 回目で要素を取り出すと何もしていないのと同じ
            chmax(dp[i][0], dp[i - 2][1]);
            chmax(dp[i][0], dp[i - 2][0]);
        }
    }
    cout << max(dp[n][0], dp[n][1]) << '\n';
}

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

    ll N, M, K, S, T, X;
    cin >> N >> M >> K >> S >> T >> X;
    S--, T--, X--;
    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    // dp[k][i][j]: k 回移動後、頂点 i にたどり着くまでに頂点 X を偶数(j=0)/奇数(j=1)回訪れる経路の数
    vector<vector<vector<mint>>> dp(K + 1, vector<vector<mint>>(N, vector<mint>(2)));
    dp[0][S][0] = 1;

    rep2(i, 1, K + 1) {
        rep(j, N) {
            for (int nx : graph[j]) {
                if (nx == X) {
                    dp[i][nx][0] += dp[i - 1][j][1];
                    dp[i][nx][1] += dp[i - 1][j][0];
                } else {
                    dp[i][nx][0] += dp[i - 1][j][0];
                    dp[i][nx][1] += dp[i - 1][j][1];
                }
            }
        }
    }

    cout << dp[K][T][0].val() << endl;
}

if (dist[i][j] > dist[i][k] + dist[k][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
    value[i][j] = value[i][k] + value[k][j] - prices[k];
}
if (dist[i][j] == dist[i][k] + dist[k][j]) {
    chmax(value[i][j], value[i][k] + value[k][j] - prices[k]);
}

if (dist[i][j] >= dist[i][k] + dist[k][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
    chmax(value[i][j], value[i][k] + value[k][j] - prices[k]);
}

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

    int n, m;
    cin >> n >> m;

    vll ans(n);
    priority_queue<int, vint, greater<int>> people;

    // time, id
    using P = pair<ll, int>;
    priority_queue<P, vector<P>, greater<P>> tpq;

    rep(i, n) people.push(i);
    rep(i, m) {
        ll t, w, s;
        cin >> t >> w >> s;

        // そうめんが流れてくるまでに列に戻ってくる人を列に戻す
        while (tpq.size() && tpq.top().first <= t) {
            auto [t, id] = tpq.top();
            tpq.pop();
            people.push(id);
        }

        // 列に誰もいなかったら何もしない
        if (people.size() == 0)
            continue;

        auto p = people.top();
        people.pop();
        ans[p] += w;
        tpq.push({t + s, p});
    }

    for (ll x : ans)
        cout << x << '\n';
}

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

    ll n, row, col;
    cin >> n >> row >> col;
    string s;
    cin >> s;

    using P = pair<ll, ll>;
    set<P> memo;
    memo.insert({0, 0});

    int si = 0, sj = 0;

    for (char c : s) {
        if (c == 'N') {
            si++;
            row++;
        }
        if (c == 'W') {
            sj++;
            col++;
        }
        if (c == 'S') {
            si--;
            row--;
        }
        if (c == 'E') {
            sj--;
            col--;
        }
        memo.insert({si, sj});
        if (memo.count({row, col})) {
            cout << 1;
        } else {
            cout << 0;
        }
    }
    cout << endl;
}

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

    int n;
    cin >> n;
    vector<vector<char>> B(n, vector<char>(n, '_')), R(n, vector<char>(n, '_'));
    rep(i, n) {
        rep(j, n) {
            char c;
            cin >> c;
            if (c == 'R')
                R[i][j] = c;
            else
                B[i][j] = c;
        }
    }

    vint di = {1, 0, -1, 0};
    vint dj = {0, -1, 0, 1};

    auto cal = [&](vector<vector<char>>& grid, int si, int sj, int ti, int tj) -> ll {
        vvll dist(n, vll(n, INF));
        dist[si][sj] = 0;

        using P = tuple<int, int, int>;
        priority_queue<P, vector<P>, greater<P>> que;
        que.push({0, si, sj});

        while (que.size()) {
            auto [cost, i, j] = que.top();
            que.pop();

            if (dist[i][j] < cost)
                continue;

            rep(d, 4) {
                int ni = i + di[d], nj = j + dj[d];
                if (clamp(ni, 0, n - 1) != ni || clamp(nj, 0, n - 1) != nj)
                    continue;
                if (grid[ni][nj] == '_') {
                    if (dist[ni][nj] <= dist[i][j] + 1)
                        continue;
                    dist[ni][nj] = dist[i][j] + 1;
                } else {
                    if (dist[ni][nj] <= dist[i][j])
                        continue;
                    dist[ni][nj] = dist[i][j];
                }
                que.push({dist[ni][nj], ni, nj});
            }
        }

        return dist[ti][tj];
    };

    ll ans = cal(R, 0, 0, n - 1, n - 1) + cal(B, 0, n - 1, n - 1, 0);
    cout << ans << endl;
}

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

    int n, q;
    cin >> n >> q;
    vint P(q), V(q);
    rep(i, q) {
        cin >> P[i] >> V[i];
        P[i]--;
    }

    // kind[i]: i 回目にどの操作を必要があるか
    // -1 左操作
    // 1  右操作
    // 0  どちらでも良い
    vint kind(q);

    auto change = [&](int i, int op) -> bool {
        if (kind[i] == 0) {
            kind[i] = op;
            return true;
        }
        if (kind[i] != op) {
            // 操作が矛盾
            return false;
        }
        return true;
    };

    rep(i, q) {
        rep2(j, i + 1, q) {
            if (V[i] <= V[j])
                continue;
            if (P[i] == P[j]) {
                cout << 0 << endl;
                return;
            }

            bool ok = true;
            if (P[i] < P[j]) {
                // i 番目の操作で左操作
                // j 番目の操作で右操作
                // をしなければならない
                ok = ok && change(i, -1);
                ok = ok && change(j, 1);
            }
            if (P[i] > P[j]) {
                // i 番目の操作で右操作
                // j 番目の操作で左操作
                // をしなければならない
                ok = ok && change(i, 1);
                ok = ok && change(j, -1);
            }
            if (!ok) {
                cout << 0 << endl;
                return;
            }
        }
    }

    mint two = 2;
    ll cnt = 0;
    rep(i, q) cnt += kind[i] == 0;
    cout << two.pow(cnt).val() << endl;
}

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

    int n, k, p;
    cin >> n >> k >> p;
    vll c(n + 1);
    vvll A(n + 1, vll(k));
    rep(i, n) {
        cin >> c[i + 1];
        rep(j, k) {
            cin >> A[i + 1][j];
        }
    }

    vector<map<vll, ll>> dp(n + 1);
    dp[0][vll(k, 0)] = 0;
    rep2(i, 1, n + 1) {
        dp[i] = dp[i - 1];
        for (auto [v, val] : dp[i - 1]) {
            vll t = v;
            rep(j, k) {
                t[j] += A[i][j];
                if (t[j] > p)
                    t[j] = p;
            }
            if (dp[i].count(t)) {
                chmin(dp[i][t], val + c[i]);
            } else {
                dp[i][t] = val + c[i];
            }
        }
    }

    vll v(k, p);
    if (dp[n].count(v)) {
        cout << dp[n][v] << endl;
    } else {
        cout << -1 << endl;
    }
}

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

    int n;
    cin >> n;
    vvint graph(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vint sz;

    auto dfs = [&](auto dfs, int now, int p, int label) -> void {
        if (label == 1) {
            sz.push_back(graph[now].size());
        }

        for (int nx : graph[now]) {
            if (nx == p)
                continue;
            dfs(dfs, nx, now, (label + 1) % 3);
        }
    };

    rep(i, n) if (graph[i].size() == 1) {
        dfs(dfs, i, -1, 0);
        break;
    }

    sort(all(sz));
    print(sz);
}

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

    int n, k;
    string s;
    cin >> n >> k >> s;

    ll ans = n;
    rep2(d, 1, n) {
        if (n % d)
            continue;

        int sum = 0;
        rep(i, d) {
            vint cnt(26, 0);
            for (int j = i; j < n; j += d) {
                cnt[s[j] - 'a']++;
            }
            sum += *max_element(all(cnt));
        }
        if (n - sum <= k)
            chmin(ans, d);
    }
    cout << ans << endl;
}

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

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

    A.insert(A.begin(), 0);
    A.push_back(L);
    vll diff;
    rep(i, N + 1) {
        diff.push_back(A[i + 1] - A[i]);
    }

    int m = diff.size();
    ll ac = 0, wa = L + 1;
    while (abs(ac - wa) > 1) {
        ll wj = (ac + wa) / 2;
        int i = 0;
        ll cnt = 0;
        ll sum = 0;
        rep(i, m) {
            sum += diff[i];
            if (sum >= wj) {
                sum = 0;
                cnt++;
            }
        }

        if (cnt >= K + 1) {
            ac = wj;
        } else {
            wa = wj;
        }
    }
    cout << ac << endl;
}

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

    ll n, k;
    cin >> n >> k;
    vll a(n);
    rep(i, n) cin >> a[i];

    map<ll, ll> mp;
    for (ll x : a)
        mp[x]++;

    ll ans = 0;
    while (mp.rbegin() != mp.rend() && k) {
        auto it = mp.rbegin();
        auto nit = next(it);

        ll v1 = it->first;
        ll n1 = it->second;
        ll v2 = 0;
        if (nit != mp.rend())
            v2 = nit->first;

        if ((v1 - v2) * n1 <= k) {
            k -= (v1 - v2) * n1;
            ans += cal(v2, v1) * n1;
            mp.erase(v1);
            if (v2)
                mp[v2] += n1;
        } else {
            ll q = k / n1;
            ll r = k % n1;
            ans += cal(v1 - q, v1) * n1;
            v1 -= q;
            ans += v1 * r;
            k = 0;
        }
    }
    cout << ans << endl;
}

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

    ll a, b, k;
    cin >> a >> b >> k;

    int m = a + b;
    vvll dp(m + 1, vll(m + 1, 0));
    dp[0][0] = 1;
    rep(i, m + 1) {
        rep(j, m + 1) {
            if (i > 0)
                dp[i][j] += dp[i - 1][j];
            if (j > 0)
                dp[i][j] += dp[i][j - 1];
        }
    }

    string ans = "";
    auto dfs = [&](auto dfs, ll na, ll nb, ll rem) {
        if (na == 0 && nb == 0) {
            return;
        }

        if (na == 0) {
            ans.push_back('b');
            dfs(dfs, na, nb - 1, rem);
            return;
        }
        if (nb == 0) {
            ans.push_back('a');
            dfs(dfs, na - 1, nb, rem);
            return;
        }

        ll v = dp[na - 1][nb];
        if (rem <= v) {
            ans.push_back('a');
            dfs(dfs, na - 1, nb, rem);
            return;
        }

        ans.push_back('b');
        dfs(dfs, na, nb - 1, rem - v);
    };

    dfs(dfs, a, b, k);

    cout << ans << endl;
}

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

    int n;
    cin >> n;
    double ans = 0;
    rep2(i, 1, n) {
        ans += 1.0 / i;
    }
    printf("%.9lf\n", ans * n);
}

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

    int n;
    cin >> n;
    vll a(n + 1);
    rep(i, n) cin >> a[i + 1];

    vvll dp(n + 1, vll(2, -INF));
    dp[0][1] = 0;
    rep2(i, 1, n + 1) {
        chmax(dp[i][1], dp[i - 1][1] + a[i]);
        chmax(dp[i][1], dp[i - 1][0] + a[i]);
        if (i - 2 >= 0) {
            chmax(dp[i][0], dp[i - 2][1]);
            chmax(dp[i][0], dp[i - 2][0]);
        }
    }
    cout << max(dp[n][0], dp[n][1]) << '\n';
}

struct Edge {
    ll to, cost;
};

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

    int n, a, b, c;
    cin >> n >> a >> b >> c;

    vvll D(n, vll(n));
    rep(i, n) rep(j, n) cin >> D[i][j];

    vector<vector<Edge>> graph(n * 2);
    rep(i, n) rep(j, n) {
        if (i == j)
            continue;
        graph[i].push_back({j, D[i][j] * a});
        graph[j].push_back({i, D[i][j] * a});
        graph[n + i].push_back({n + j, D[i][j] * b + c});
        graph[n + j].push_back({n + i, D[i][j] * b + c});
    }
    rep(i, n) graph[i].push_back({n + i, 0});

    vll dist(n * 2, INF);
    dist[0] = 0;

    // cost, pos
    using P = pair<ll, ll>;
    priority_queue<P, vector<P>, greater<P>> pq;

    pq.push({0, 0});
    while (pq.size()) {
        auto [cost, now] = pq.top();
        pq.pop();

        if (dist[now] < cost)
            continue;

        for (auto [to, cost] : graph[now]) {
            if (dist[to] <= dist[now] + cost)
                continue;

            dist[to] = dist[now] + cost;
            pq.push({dist[to], to});
        }
    }

    cout << min(dist[n - 1], dist[n * 2 - 1]) << '\n';
}

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

    int n, m;
    cin >> n >> m;

    vll b(n), w(m);
    rep(i, n) cin >> b[i];
    rep(i, m) cin >> w[i];

    sort(rall(b));
    sort(rall(w));

    ll ans = 0;
    int nb = 0;
    rep(i, n) {
        if (b[i] >= 0) {
            ans += b[i];
            nb++;
        }
    }

    int nw = 0;
    while (nw < m && nb > nw && w[nw] > 0) {  // コンテスト中のコードだと nw < m を入れ忘れた
        ans += w[nw];
        nw++;
    }
    while (nw < m && nb < n && w[nw] + b[nb] >= 0) {
        ans += w[nw] + b[nb];
        nw++;
        nb++;
    }
    cout << ans << endl;
}

struct SegmentTree {
    vll seg;
    int len;

    SegmentTree(int n) {
        rep(i, 30) {
            if (n <= (1 << i)) {
                len = 1 << i;
                break;
            }
        }
        seg.resize(len * 2, 0);
    }

    ll get(int p) {
        p += len;
        ll ans = seg[p];
        while (p / 2) {
            p /= 2;
            ans += seg[p];
        }

        return ans;
    }

    void add(int l, int r, ll x) {
        l += len, r += len;
        while (l < r) {
            if (l & 1) {
                seg[l] += x;
                l++;
            }
            l /= 2;
            if (r & 1) {
                seg[r - 1] += x;
                r--;
            }
            r /= 2;
        }
    }
};

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

    ll n, m;
    cin >> n >> m;

    SegmentTree seg(n);
    rep(i, n) {
        ll a;
        cin >> a;
        seg.add(i, i + 1, a);
    }

    rep(i, m) {
        int b;
        cin >> b;
        ll x = seg.get(b);
        seg.add(b, b + 1, -x);

        b++;
        ll q = x / n;
        ll r = x % n;
        seg.add(0, n, q);
        if (b + r >= n) {
            seg.add(b, n, 1);
            seg.add(0, b + r - n, 1);
        } else {
            seg.add(b, b + r, 1);
        }
    }

    rep(i, n) {
        if (i != 0)
            cout << ' ';
        cout << seg.get(i);
    }
    cout << endl;
}

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

    ll n, m, k;
    cin >> n >> m >> k;

    vector<tuple<ll, ll, ll>> es;
    rep(i, m) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        es.emplace_back(u, v, w);
    }

    ll ans = INF;
    auto dfs = [&](auto dfs, int depth, vint used) {
        if (used.size() == n - 1) {
            dsu uf(n);
            ll sum = 0;
            for (int i : used) {
                auto [u, v, w] = es[i];
                if (uf.same(u, v))
                    return;
                uf.merge(u, v);
                sum += w;
                sum %= k;
            }
            chmin(ans, sum);
            return;
        }
        if (depth == m) {
            return;
        }

        dfs(dfs, depth + 1, used);
        used.push_back(depth);
        dfs(dfs, depth + 1, used);
    };

    dfs(dfs, 0, {});
    cout << ans << endl;
}

void solve() {
    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, char>> qs;
    rep(i, m) {
        int x, y;
        char c;
        cin >> x >> y >> c;
        qs.emplace_back(x, y, c);
    }
    sort(all(qs));

    int cnum = INF;
    for (auto [x, y, c] : qs) {
        if (c == 'B') {
            if (cnum <= y) {
                yesno(false);
                return;
            }
        } else {
            chmin(cnum, y);
        }
    }
    yesno(true);
}

void solve() {
    int N, Q;
    cin >> N >> Q;

    // 配置されたときの index, その時の巣の番号
    vector<pair<int, int>> hato(N);
    // 入れ替えがあったときの index, 移動先の巣の番号
    vector<vector<pair<int, int>>> hako(N);
    rep(i, N) {
        hato[i] = {-1, i};
        hako[i].push_back({-1, i});
    }

    map<pair<int, int>, pair<int, int>> memo;

    rep(i, Q) {
        int t;
        cin >> t;
        if (t == 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;

            hato[a] = {i, b};
        } else if (t == 2) {
            int a, b;
            cin >> a >> b;
            a--, b--;

            hako[a].push_back({i, b});
            hako[b].push_back({i, a});
        } else {
            int a;
            cin >> a;
            a--;

            auto [id, num] = hato[a];
            vector<pair<int, int>> olds;
            while (true) {
                auto it = upper_bound(all(hako[num]), make_pair(id, INF));
                if (it == hako[num].end())
                    break;
                olds.push_back(*it);
                if (memo.count(*it)) {
                    auto x = memo[*it];
                    id = x.first;
                    num = x.second;
                } else {
                    id = it->first;
                    num = it->second;
                }
            }
            if (olds.size())
                olds.pop_back();
            // 経路圧縮
            for (auto [a, b] : olds) {
                memo[{a, b}] = {id, num};
            }
            hato[a] = {id, num};
            cout << num + 1 << endl;
        }
    }
}

vector<vector<mint>> dp(N + 1, vector<mint>(M + 1, 0));
rep(i, M) dp[1][i + 1] = 1;
rep2(i, 2, N + 1) {
    rep2(k, 1, M + 1) {
        rep2(j, 1, M + 1) {
            if (abs(k - j) >= K)
                dp[i][k] += dp[i - 1][j];
        }
    }
}

mint ans = 0;
rep2(i, 1, M + 1) ans += dp[N][i];
cout << ans.val() << endl;

void solve() {
    int n;
    cin >> n;
    vector<string> delta(n);
    rep(i, n) cin >> delta[i];

    vvll dist(n, vll(n, -1));
    // 回分の最短距離が決まっている path を que に入れる
    queue<pair<int, int>> que;

    rep(i, n) {
        dist[i][i] = 0;
        que.push({i, i});
    }

    rep(i, n) rep(j, n) {
        if (i != j && delta[i][j] != '-') {
            dist[i][j] = 1;
            que.push({i, j});
        }
    }

    while (que.size()) {
        auto [i, j] = que.front();
        que.pop();

        rep(k, n) {
            rep(l, n) {
                if (delta[k][i] != '-' && delta[k][i] == delta[j][l] &&
                    dist[k][l] == -1) {
                    // i -> j への path の回分の長さはすでに決まっている
                    // delta[k][i] == delta[j][l] ならば、k -> i -> j -> l という path が回分になる
                    // que には距離が短い順に入っているので一番最初に見つかった k -> l の path を最短として良い
                    // k -> i -> j -> l なる path を考えるときに (i,j) の全ての組み合わせを調べる必要はないということ
                    dist[k][l] = dist[i][j] + 2;
                    que.push({k, l});
                }
            }
        }
    }

    for (auto v : dist)
        print(v);
}

void solve() {
    ll n, m;
    cin >> n >> m;
    vll x(m);
    rep(i, m) {
        cin >> x[i];
        x[i]--;
    }

    vll cumsum(n * 2 + 1, 0);

    rep(i, m - 1) {
        ll mi = min(x[i], x[i + 1]);
        ll mx = max(x[i], x[i + 1]);

        ll dr = mx - mi;
        ll dl = n - dr;
        cumsum[mi] += dl;
        cumsum[mx] -= dl;
        cumsum[0] += dr;
        cumsum[mi] -= dr;
        cumsum[mx] += dr;
        cumsum[n] -= dr;
    }

    rep(i, n * 2) cumsum[i + 1] += cumsum[i];

    ll ans = INF;
    rep(i, n) chmin(ans, cumsum[i]);
    cout << ans << endl;
}

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    rep(i, H) cin >> grid[i];

    int si, sj;
    rep(i, H) rep(j, W) if (grid[i][j] == 'S') si = i, sj = j;
    vvint mark(H, vint(W, -1));

    queue<pair<int, int>> q;
    q.push({si, sj});
    mark[si][sj] = 0;

    vint di = {0, 1, 0, -1};
    vint dj = {1, 0, -1, 0};

    while (q.size()) {
        auto [i, j] = q.front();
        q.pop();

        int c = mark[i][j];
        int start = c == 0;

        rep(d, 4) {
            if (start)
                c = d + 1;
            int ni = i + di[d], nj = j + dj[d];
            if (clamp(ni, 0, H - 1) != ni || clamp(nj, 0, W - 1) != nj)
                continue;
            if (grid[ni][nj] == '#')
                continue;
            int m = mark[ni][nj];
            if (m > 0 && m != c) {
                yesno(true);
                return;
            }
            if (m == -1) {
                mark[ni][nj] = c;
                q.push({ni, nj});
            }
        }
    }
    yesno(false);
}

void solve() {
    int N;
    string S;
    cin >> N >> S;

    vint ids;
    rep(i, N) {
        if (S[i] == '1')
            ids.push_back(i);
    }

    ll ans = 0;
    int mid = ids[ids.size() / 2];
    int zid = mid + 1;
    for (int i = mid + 1; i < N; i++) {
        while (S[zid] == '1' && zid < N)
            zid++;
        if (i <= zid)
            continue;
        if (S[i] == '1') {
            ans += i - zid;
            swap(S[i], S[zid]);
        }
    }

    zid = mid - 1;
    for (int i = mid - 1; i >= 0; i--) {
        while (S[zid] == '1' && zid >= 0)
            zid--;
        if (zid <= i)
            continue;
        if (S[i] == '1') {
            ans += zid - i;
            swap(S[i], S[zid]);
        }
    }
    cout << ans << endl;
    // cout << S << endl;
}

int h, w;
vector<string> grid;
vvint memo;
vvint visited;
vint di = {0, 1, 0, -1};
vint dj = {1, 0, -1, 0};

pair<int, int> ind2sub(int x) {
    return {x / w, x % w};
}

int sub2ind(int i, int j) {
    return i * w + j;
}

int canMove(int i, int j) {
    int ok = 1;
    rep(d, 4) {
        int ni = i + di[d], nj = j + dj[d];
        if (clamp(ni, 0, h - 1) != ni || clamp(nj, 0, w - 1) != nj)
            continue;
        if (grid[ni][nj] == '#')
            ok = 0;
    }

    return ok;
}

void solve() {
    cin >> h >> w;
    grid = vector<string>(h);
    rep(i, h) cin >> grid[i];

    dsu uf(h * w);

    rep(i, h) rep(j, w) {
        if (grid[i][j] == '.' && canMove(i, j)) {
            for (auto [ii, jj] : vector<pair<int, int>>({{1, 0}, {0, 1}})) {
                int ni = i + ii, nj = j + jj;
                if (clamp(ni, 0, h - 1) != ni || clamp(nj, 0, w - 1) != nj)
                    continue;
                if (canMove(ni, nj)) {
                    uf.merge(sub2ind(i, j), sub2ind(ni, nj));
                }
            }
        }
    }

    int ans = 1;
    for (auto v : uf.groups()) {
        set<pair<int, int>> stop;
        {
            auto [i, j] = ind2sub(v[0]);
            if (grid[i][j] == '#')
                continue;
            else if (!canMove(i, j)) {
                continue;
            }
        }
        for (int id : v) {
            auto [i, j] = ind2sub(id);
            rep(d, 4) {
                int ni = i + di[d], nj = j + dj[d];
                if (clamp(ni, 0, h - 1) != ni || clamp(nj, 0, w - 1) != nj)
                    continue;
                if (grid[ni][nj] == '.' && !canMove(ni, nj))
                    stop.insert({ni, nj});
            }
        }
        chmax(ans, (int)v.size() + (int)stop.size());
    }

    cout << ans << endl;
}

ll intpow(ll x, ll n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1)
            ret *= x;
        x *= x;
        n >>= 1;
    }
    return ret;
}

void solve() {
    ll N;
    cin >> N;

    if (N == 1) {
        cout << 0 << endl;
        return;
    }

    N--;
    for (ll d = 1;; d++) {
        if (N <= intpow(10, (d - 1) / 2) * 9) {
            ll b = intpow(10, (d - 1) / 2) + N - 1;
            string s = to_string(b);
            s.resize(s.size() * 2 - d % 2, ' ');
            rep(i, d / 2) {
                s[s.size() - i - 1] = s[i];
            }
            cout << s << endl;

            return;
        } else {
            N -= intpow(10, (d - 1) / 2) * 9;
        }
    }
}

void solve() {
    ll l, r;
    cin >> l >> r;

    vector<pair<ll, ll>> ans;
    while (r - l >= 1) {
        ll cnt = 0;
        while ((l & (1LL << cnt)) == 0 && cnt <= 60)
            cnt++;

        while (l + (1LL << cnt) > r)
            cnt--;

        ans.push_back({l, l + (1LL << cnt)});
        l += 1LL << cnt;
    }

    cout << ans.size() << endl;
    for (auto [x, y] : ans) {
        cout << x << ' ' << y << endl;
    }
}

vvint graph;
vint visited;
set<int> memo;
int ans = 0;

bool dfs(int now) {
    bool res = false;
    if (memo.count(now))
        res = true;

    for (int nx : graph[now]) {
        if (visited[nx])
            continue;
        visited[nx] = 1;

        bool x = dfs(nx);
        res = res || x;

        // short-circuit で以下のよう書くと dfs が実行されない
        // res = res || dfs(nx)
    }

    if (res)
        ans++;
    return res;
}

void solve() {
    int n, k;
    cin >> n >> k;
    graph = vvint(n);
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vint nodes(k);
    rep(i, k) {
        cin >> nodes[i];
        nodes[i]--;
    }

    for (int x : nodes)
        memo.insert(x);

    visited = vint(n, 0);
    visited[nodes[0]] = 1;

    dfs(nodes[0]);
    cout << ans << endl;
}

void solve() {
    string S;
    cin >> S;

    int n = S.size();
    vvll v(n + 1, vll(10, 0));
    rep(i, n) {
        v[i + 1][S[i] - '0']++;
    }

    rep(k, 10) {
        rep(i, n) {
            v[i + 1][k] += v[i][k];
            v[i + 1][k] %= 2;
        }
    }

    vll cnt(1 << 10, 0);
    rep2(i, 0, n + 1) {
        int x = 0;
        rep(k, 10) {
            x *= 2;
            if (v[i][k])
                x += 1;
        }
        cnt[x]++;
    }

    ll ans = 0;
    rep(i, 1 << 10) {
        ans += cnt[i] * (cnt[i] - 1) / 2;
    }
    cout << ans << endl;
}

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

    A.push_back(0);
    A.insert(A.begin(), 0);

    N += 2;
    vll dl(N, 0), dr(N, 0);
    rep2(i, 1, N) {
        dl[i] = min(dl[i - 1] + 1, A[i]);
    }

    rep(i, N - 1) {
        int k = N - 1 - i;
        dr[k - 1] = min(dr[k] + 1, A[k - 1]);
    }

    ll ans = 0;
    rep(i, N) {
        chmax(ans, min(dr[i], dl[i]));
    }
    cout << ans << endl;
}

void solve() {
    ll T;
    cin >> T;
    rep(_, T) {
        ll N, M;
        cin >> N >> M;

        ll x = N * (N + 1) % M;
        string ans = "Alice";
        if (clamp(x, 1LL, N) == x) {
            ans = "Bob";
        }
        cout << ans << endl;
    }
}

ll f(ll n, ll p) {
    ll ans = 0;
    ll b = p;
    while (n / b) {
        ans += n / b;
        b *= p;
    }

    return ans;
}

void solve() {
    ll K;
    cin >> K;

    vector<pair<ll, ll>> div;
    {
        ll x = K;
        for (ll i = 2; i * i <= x; i++) {
            if (x % i != 0)
                continue;

            ll cnt = 0;
            while (x % i == 0) {
                x /= i;
                cnt++;
            }
            div.emplace_back(i, cnt);
        }
        if (x != 1)
            div.emplace_back(x, 1);
    }

    ll ac = K, wa = 1;
    while (abs(ac - wa) > 1) {
        ll wj = (ac + wa) / 2;
        ll ok = 1;
        for (auto [p, cnt] : div) {
            if (f(wj, p) < cnt)
                ok = 0;
        }
        if (ok)
            ac = wj;
        else
            wa = wj;
    }

    cout << ac << endl;
}

void solve() {
    ll n;
    cin >> n;
    vll h(n);
    rep(i, n) cin >> h[i];

    vll ans(n);
    vll st;
    for (int i = n - 1; i >= 0; i--) {
        ans[i] = st.size();
        while (st.size() != 0 && st.back() < h[i]) {
            st.pop_back();
        }
        st.push_back(h[i]);
    }
    print(ans);
}

void solve() {
    ll N, Q;
    cin >> N >> Q;

    dsu uf(N);
    vvint nodes(N);
    rep(i, N) {
        nodes[i].push_back(i);
    }

    rep(i, Q) {
        int q, a, b;
        cin >> q >> a >> b;
        if (q == 1) {
            int u = a - 1, v = b - 1;
            if (uf.same(u, v))
                continue;
            int ou = uf.leader(u);
            int ov = uf.leader(v);
            int newl = uf.merge(u, v);
            vint tmp = nodes[ou];
            for (auto x : nodes[ov])
                tmp.push_back(x);
            sort(rall(tmp));
            vint newv;
            for (int i = 0; i < 10 && i < tmp.size(); i++) {
                newv.push_back(tmp[i]);
            }
            nodes[newl] = newv;
        } else {
            int v = a - 1, k = b;
            int l = uf.leader(v);
            if (nodes[l].size() >= k) {
                cout << nodes[l][k - 1] + 1 << endl;
            } else {
                cout << -1 << endl;
            }
        }
    }
}

void solve() {
    ll N;
    cin >> N;
    vll f(N);
    rep(i, N) {
        cin >> f[i];
        f[i]--;
    }

    scc_graph graph(N);
    rep(i, N) {
        graph.add_edge(i, f[i]);
    }

    vvint scc = graph.scc();
    ll cnt = 0;
    for (auto& x : scc) {
        if (x.size() > 1) {
            cnt++;
        } else {
            // 大きさ1のときは自己ループしていればカウント
            if (x[0] == f[x[0]])
                cnt++;
        }
    }

    mint ans = ((mint)2).pow(cnt) - 1;
    cout << ans.val() << endl;
}

void solve() {
    ll N, M;
    cin >> N >> M;

    vector<Edge> es(M);
    rep(i, M) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        es[i] = {a, b, c};
    }

    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    for (auto e : es)
        pq.push(e);
    dsu uf(N);
    vll dust;
    while (pq.size()) {
        auto [u, v, c] = pq.top();
        pq.pop();

        if (uf.same(u, v)) {
            if (c > 0)
                dust.push_back({c});
        } else {
            uf.merge(u, v);
        }
    }

    ll ans = 0;
    for (ll x : dust) {
        if (x > 0)
            ans += x;
    }
    cout << ans << endl;
}