#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

struct Info {
    LL minv;
    Info(LL minv = 1E9) : minv(minv) {}
};
Info operator+(const Info& a, const Info& b) {
    return std::min(a.minv, b.minv);
}
struct Tag {
    LL add;
    Tag(LL add = 0) : add(add) {}
};
void apply(Info& a, Tag b) {
    a.minv += b.add;
}
void apply(Tag& a, Tag b) {
    a.add += b.add;
}

template <typename Info, typename Tag,
        typename Merge = std::plus<Info>>
struct LazySegmentTree {
    const int n;
    const Merge merge;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree(int n) : n(n), merge(Merge()), 
                             info(4 << std::__lg(n)), tag(4 << std::__lg(n)) { }
    LazySegmentTree(std::vector<Info> init) : LazySegmentTree(init.size() - 1) {
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if(r == l) {
                info[p] = init[l];
                return;
            }
            int mid = (l + r) >> 1;
            build(2 * p, l, mid);
            build(2 * p + 1, mid + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) {
        info[p] = merge(info[2 * p], info[2 * p + 1]);
    }
    void apply(int p, const Tag &v) {
        ::apply(info[p], v);
        ::apply(tag[p], v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if(r == l) {
            info[p] = v;
            return;
        }
        int mid = (l + r) >> 1;
        push(p);
        if(x <= mid) {
            modify(p * 2, l, mid, x, v);
        }
        else {
            modify(p * 2 + 1, mid + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info& v) {
        modify(1, 1, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x)     return Info();
        if (l >= x && r <= y)   return info[p];
        int mid = (l + r) >> 1;
        push(p);
        return merge(rangeQuery(p * 2, l, mid, x, y), rangeQuery(p * 2 + 1, mid + 1, r, x, y));
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 1, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int mid = (l + r) >> 1;
        push(p);
        rangeApply(2 * p, l, mid, x, y, v);
        rangeApply(2 * p + 1, mid + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 1, n, l, r, v);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<Info> a(n + 1);
    for (int i = 1; i <= n; i ++ ) {
        std::cin >> a[i].minv;
    }    

    LazySegmentTree<Info, Tag> seg(a);

    int m;
    std::cin >> m;
    std::string s;
    std::getline(std::cin, s);

    // std::cout << seg.rangeQuery(1, 4).minv << "\n";
    while (m--) {
        std::getline(std::cin, s);
        std::stringstream ssin(s);
        std::vector<int> v;
        int x;
        while (ssin >> x) { 
            v.push_back(x);
        }

        if (v.size() == 2) {
            int l = v[0], r = v[1];
            l++, r++;
            // std::cout << l << " " << r << "\n";
            if (l <= r)
                std::cout << seg.rangeQuery(l, r).minv << "\n";
            else
                std::cout << std::min(seg.rangeQuery(1, r).minv, seg.rangeQuery(l, n).minv) << "\n";
        } else {
            int l = v[0], r = v[1], val = v[2];
            l++, r++;
            if (l <= r)
                seg.rangeApply(l, r, val);
            else {
                seg.rangeApply(1, r, val);
                seg.rangeApply(l, n, val);
            }
        }
    }

    return 0;
}

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> m >> n;
    std::vector<std::vector<int>> adj(m);
    std::vector<int> c(n);

    for (int i = 0; i < n; i ++ ) {
        std::cin >> c[i];
    }

    int root = -1;
    for (int i = 0; i < m - 1; i ++ ) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::vector dp(m, std::vector<int>(2, 1E9));

    for (int i = n; i < m; i ++ ) {
        dp[i][0] = dp[i][1] = 1;
    }

    for (int i = 0; i < n; i ++ ) {
        dp[i][!c[i]] = 1E9;
        dp[i][c[i]] = 1;
    }

    int res = 1E9;
    std::function<void(int, int)> dfs = [&](int x, int father) {
        if (x < n) {
            return;
        }
        for (auto y : adj[x]) {
            if (y == father) {
                continue;
            }
            dfs(y, x);
            dp[x][1] += std::min(dp[y][1] - 1, dp[y][0]);
            dp[x][0] += std::min(dp[y][0] - 1, dp[y][1]);
        }
    };

    dfs(n, -1);
    std::cout << std::min(dp[n][0], dp[n][1]) << "\n";
    return 0;
}

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<std::vector<PII>> e(n);
    for (int i = 0; i < n - 1; i ++ ) {
        int u, v, w;
        std::cin >> u >> v >> w;
        u--, v--;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }

    int res = 0;
    std::function<int(int, int)> dfs = [&](int x, int father) {
        int d1 = 0, d2 = 0;
        for (auto [y, w] : e[x]) {
            if (y == father)
                continue;
            int dist = dfs(y, x) + w;
            if (dist >= d1)
                d2 = d1, d1 = dist;
            else if (dist > d2)
                d2 = dist;
        }
        res = std::max(res, d1 + d2);
        return d1;
    };

    dfs(0, -1);

    std::cout << res << "\n";
    return 0;
}

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n = 0) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }   
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = std::max(a[i - 1], v);
        }
    }    
    T sum(int x) { // 小于x的数之和
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans = std::max(a[i - 1], ans);
        }
        return ans;
    }    
    T rangeSum(int l, int r) { // 区间和 左闭右开
        return sum(r) - sum(l);
    }    
    int kth(T k) { // 第一个大于等于k的位置
        int x = 0;
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x - 1;
    }
};

int main() {
    std::ios::sync_with_stdio(false);

    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    Fenwick<LL> fen(n);
    std::vector<LL> a(n);
    for (int i = 0; i < n; i ++ ) {
        std::cin >> a[i];
    }

    std::vector<LL> temp = a;
    std::sort(temp.begin(), temp.end());
    temp.erase(std::unique(temp.begin(), temp.end()), temp.end());

    std::vector<LL> sum(n);

    auto find = [&](int x) {
        return std::lower_bound(temp.begin(), temp.end(), x) - temp.begin();
    };
    LL res = 0;
    for (int i = 0; i < n; i ++ ) {
        int idx = find(a[i]);
        // sum[i] = a[i];
        // for (int j = 0; j < a[i]; j ++ ) {
        //  sum[i] = std::max(sum[i], maxsum[j] + a[i]);
        // }
        sum[i] = std::max(a[i], fen.sum(idx) + a[i]);
        // maxsum[a[i]] = std::max(maxsum[a[i]], sum[i]);
        fen.add(idx, sum[i]);
    }


    std::cout << fen.sum(n);

    return 0;
}

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<LL> a(2 * n + 1);

    for (int i = 1; i <= n; i ++ ) {
        std::cin >> a[i];
        a[i + n] = a[i];
    }

    LL res = 0;
    std::vector dp(2 * n + 1, std::vector<LL>(2 * n + 1, 0));

    for (int len = 3; len <= n + 1; len ++ ) {
        for (int l = 1; l + len - 1 <= 2 * n; l ++ ) {
            int r = l + len - 1;
            for (int k = l + 1; k < r; k ++ ) {
                dp[l][r] = std::max(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]);
                res = std::max(res, dp[l][r]);
            }
        }
    }

    std::cout << res << "\n";

    return 0;
}

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> a(n);

    for (int i = 0; i < n; i ++ ) {
        std::cin >> a[i];
    }

    int init = a[0];
    std::vector<int> col;
    for (int i = 1; i < n; i ++ ) {
        if (a[i] == init) {
            continue;
        }
        col.push_back(init);
        init = a[i];
    }
    col.push_back(init);
    n = col.size();
    std::vector dp(n, std::vector<int>(n, 1E9));

    for (int len = 1; len <= n; len ++ )
        for (int l = 0; l + len - 1 < n; l ++ ) {
            int r = l + len - 1;
            if (l == r)
                dp[l][r] = 0;
            else {
                if (col[l] == col[r]) {
                    dp[l][r] = dp[l + 1][r - 1] + 1;
                } else {
                    dp[l][r] = std::min(dp[l + 1][r], dp[l][r - 1]) + 1;
                }
            }
        }

    std::cout << dp[0][n - 1] << "\n";

    return 0;
}

// 定义变量sum来维护最大连续字段和
#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

constexpr int INF = 0x3f3f3f3f;
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1), f(n + 1, -INF), g(n + 2, -INF);

    for (int i = 1; i <= n; i ++ ) {
        std::cin >> a[i];
    }

    int sum = 0;
    for (int i = 1; i <= n; i ++ ) {
        sum = std::max(0, sum) + a[i];
        //std::cout << sum << '\n';
        f[i] = std::max(f[i - 1], sum);
        //std::cout << f[i] << '\n';
    }

    sum = 0;

    for (int i = n; i >= 1; i -- ) {
        sum = std::max(0, sum) + a[i];
        g[i] = std::max(g[i + 1], sum);
    }

    int res = -INF;
    for (int i = 1; i < n; i ++ ) {
        res = std::max(res, f[i] + g[i + 1]);
    }

    std::cout << res << "\n";
    return;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }   

    return 0;
}

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

constexpr int MOD = 1E9;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> dp(n + 1); 
    dp[0] = 1;
    for (int i = 1; i <= n; i <<= 1)
        for (int j = i; j <= n; j ++ )
            dp[j] = (dp[j] + dp[j - i]) % MOD;

    std::cout << dp[n] << "\n";

    return 0;
}

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

void solve() {
    int n, k;
    std::cin >> n >> k;

    bool setios = false;
    if (k % 3 != 0 || n < k) {
        if (n % 3 == 0)
            setios = false;
        else
            setios = true;
    } else {
        n %= k + 1;
        if (n == k || n % 3 != 0)
            setios = true;
        else
            setios = false;
    }

    if (setios) 
        std::cout << "Alice\n";
    else
        std::cout << "Bob\n";
    return;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>

using LL = long long;
using PII = std::pair<int, int>;

constexpr int MOD = 998244353, INF = 0x3f3f3f3f;
int main() { 
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector dp(n + 1, std::vector<LL>(k + 1, -INF));

    for (int i = 1; i <= k; i ++ )
        dp[1][i] = 0;
    for (int i = 1; i <= n; i ++ )
        dp[i][0] = m;
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= k; j ++ )
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * (m - 1) % MOD) % MOD;

    std::cout << dp[n][k] << "\n";

    return 0;
}