const int NMAX = 20;
using namespace std;
using answer = bitset<NMAX>;
int tsum, n, a[NMAX];
int csum;
answer best;
void backtrack(int pos, answer current, int psum)
{
    if (psum > tsum)
        return;
    if (csum < psum)
    {
        csum = psum;
        best = current;
    }
    if (pos < n)
    {
        backtrack(pos + 1, current, psum);
        backtrack(pos + 1, current.set(pos, true), psum + a[pos]);
    }
}
int main(void)
{
    while (cin >> tsum >> n)
    {
        csum = int();
        best = answer();
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        backtrack(0, answer(), 0);
        for (int i = 0; i < n; ++i)
            if (best[i])
                cout << a[i] << " ";
        cout << "sum:" << csum << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
const int NMAX = 1e5 + 11;
vii g[NMAX];
int cost[NMAX];
ll dp[NMAX], dp2[NMAX];
void compdp(int u, int p)
{
    dp[u] = 0;
    dp2[u] = 0;
    ll vmin = LLONG_MAX;
    for (auto [v, c] : g[u])
    {
        if (v == p)
            continue;
        cost[v] = c;
        compdp(v, u);
        dp[u] += dp[v] + 2 * c;
        vmin = min(vmin, dp2[v] - dp[v] - c);
    }
    dp2[u] = dp[u];
    if (vmin != LLONG_MAX)
        dp2[u] += vmin;
}
int main(void)
{
    int n, x, y, w;
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> x >> y >> w;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
    compdp(1, 0);
    cout << dp2[1] << endl;
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using vii = vector<ii>;
int n, k;
vii events;
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int li, ri;
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
    {
        cin >> li >> ri;
        events.push_back({li, -1});
        events.push_back({ri, +1});
    }
    sort(events.begin(), events.end());
    int ck = 0;
    int cl, cr;
    vii ans;
    for (auto [t, sign] : events)
    {
        sign = -sign;
        if (sign > 0 and ck + 1 == k)
            cl = t;
        else if (sign < 0 and ck == k)
        {
            cr = t;
            ans.push_back({cl, cr});
        }
        ck += sign;
    }
    cout << ans.size() << endl;
    for (auto [l, r] : ans)
        cout << l << " " << r << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
int const NMAX = 4e2 + 11;
int const INF = 1e9;
int n, gb[NMAX][NMAX], gt[NMAX][NMAX];
int bfs(int g[NMAX][NMAX], int s, int t)
{
    vector<bool> visited(n, false);
    vector<int> d(n);
    queue<int> frontier;
    visited[s] = true;
    frontier.push(s);
    while (not frontier.empty())
    {
        int u = frontier.front();
        frontier.pop();
        if (u == t)
            return d[t];
        for (int v = 0; v < n; ++v)
        {
            if (g[u][v] and not visited[v])
            {
                d[v] = d[u] + 1;
                visited[v] = true;
                frontier.push(v);
            }
        }
    }
    return INF;
}
int main(void)
{
    int m;
    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
            gb[i][j] = gb[j][i] = true;
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        gt[u][v] = gt[v][u] = true;
        gb[u][v] = gb[v][u] = false;
    }
    auto anst = bfs(gt, 0, n - 1);
    auto ansb = bfs(gb, 0, n - 1);
    if (anst == INF or ansb == INF)
        cout << -1 << endl;
    else
        cout << max(anst, ansb) << endl;
    return 0;
}

using namespace std;
int main(void)
{
    int n, lowcnt = 0;
    string s;
    cin >> s;
    n = s.size();
    for (char &c : s)
    {
        if (islower(c))
            lowcnt += 1;
        c = (char)tolower(c);
    }
    if (lowcnt >= n - lowcnt)
        cout << s << endl;
    else
    {
        for (auto c : s)
            cout << (char)toupper(c);
        cout << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 123456 + 11;
int n, m, node_end1, node_end2, diameter, edges;
bool in_attack[NMAX], st_in_attack[NMAX];
vi g[NMAX];
void dfs1(int u, int p, int depth)
{
    if (in_attack[u] and
        (depth > diameter or (depth == diameter and u < node_end1)))
    {
        diameter = depth;
        node_end1 = u;
    }
    for (auto v : g[u])
        if (v != p)
            dfs1(v, u, depth + 1);
}
void dfs2(int u, int p, int depth)
{
    if (in_attack[u] and
        (depth > diameter or (depth == diameter and u < node_end2)))
    {
        diameter = depth;
        node_end2 = u;
    }
    st_in_attack[u] = in_attack[u];
    for (int v : g[u])
    {
        if (v != p)
        {
            dfs2(v, u, depth + 1);
            st_in_attack[u] |= st_in_attack[v];
        }
    }
    if (p != -1 and st_in_attack[u])
        edges += 1;
}
int main(void)
{
    int u, v;
    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }
    for (int i = 0; i < m; ++i)
    {
        cin >> u;
        in_attack[u - 1] = true;
    }
    edges = 0;
    dfs1((node_end1 = u - 1), -1, 0);
    dfs2((node_end2 = node_end1), -1, 0);
    cout << 1 + min(node_end1, node_end2) << endl;
    cout << 2 * edges - diameter << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 1e5 + 11;
const int AMAX = 10;
struct segtree
{
    int n;
    vector<vi> t;
    segtree() {}
    segtree(int n) : n(n) { t.resize(4 * n); }
    void build(vi a[]) { build_util(a, 1, 0, n - 1); }
    void build_util(vi a[], int v, int tl, int tr)
    {
        if (tl == tr)
        {
            sort(a[tl].begin(), a[tl].end());
            t[v] = a[tl];
            if (AMAX < (int)t[v].size())
                t[v].resize(10);
        }
        else
        {
            int tm = (tl + tr) >> 1;
            build_util(a, v << 1, tl, tm);
            build_util(a, (v << 1) + 1, tm + 1, tr);
            t[v].resize(t[v << 1].size() + t[(v << 1) + 1].size());
            merge(t[v << 1].begin(),
                  t[v << 1].end(),
                  t[(v << 1) + 1].begin(),
                  t[(v << 1) + 1].end(),
                  t[v].begin());
            if (AMAX < (int)t[v].size())
                t[v].resize(10);
        }
    }
    vi query(int u, int v) { return query_util(1, 0, n - 1, u, v); }
    vi query_util(int v, int tl, int tr, int ql, int qr)
    {
        if (ql > qr)
            return vi();
        if (tl == ql and tr == qr)
            return t[v];
        int tm = (tl + tr) >> 1;
        vi lans = query_util(v << 1, tl, tm, ql, min(tm, qr));
        vi rans = query_util((v << 1) + 1, tm + 1, tr, max(tm + 1, ql), qr);
        vi ans(lans.size() + rans.size());
        merge(lans.begin(), lans.end(), rans.begin(), rans.end(), ans.begin());
        return ans;
    }
} st;
vi g[NMAX];
vi population[NMAX];
int parent[NMAX], depth[NMAX];
int heavy[NMAX], pos[NMAX], head[NMAX], hldcnt;
int dfs(int u)
{
    int usz, vsz, msz;
    usz = 1;
    msz = 0;
    for (auto v : g[u])
    {
        if (parent[u] == v)
            continue;
        parent[v] = u;
        depth[v] = depth[u] + 1;
        vsz = dfs(v);
        usz += vsz;
        if (vsz > msz)
        {
            heavy[u] = v;
            msz = vsz;
        }
    }
    return usz;
}
void decompose(int u, int h)
{
    head[u] = h;
    pos[u] = hldcnt++;
    if (heavy[u] != -1)
        decompose(heavy[u], h);
    for (auto v : g[u])
    {
        if (parent[u] != v and heavy[u] != v)
            decompose(v, v);
    }
}
void query(int u, int v, int a)
{
    int n;
    vi ans, cur;
    while (head[u] != head[v])
    {
        if (depth[head[u]] > depth[head[v]])
            swap(u, v);
        cur = st.query(pos[head[v]], pos[v]);
        v = parent[head[v]];
        n = ans.size();
        ans.resize(n + cur.size());
        copy(cur.begin(), cur.end(), ans.begin() + n);
        inplace_merge(ans.begin(), ans.begin() + n, ans.end());
    }
    if (depth[u] > depth[v])
        swap(u, v);
    cur = st.query(pos[u], pos[v]);
    n = ans.size();
    ans.resize(n + cur.size());
    copy(cur.begin(), cur.end(), ans.begin() + n);
    inplace_merge(ans.begin(), ans.begin() + n, ans.end());
    int k = min(a, (int)ans.size());
    cout << k << " ";
    for (int i = 0; i < k; ++i)
    {
        cout << ans[i] + 1 << " ";
    }
    cout << endl;
}
void reset(void)
{
    hldcnt = 0;
    memset(heavy, -1, NMAX * sizeof(*heavy));
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, q, u, v, ci, a;
    cin >> n >> m >> q;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }
    reset();
    dfs(0);
    decompose(0, 0);
    for (int i = 0; i < m; ++i)
    {
        cin >> ci;
        population[pos[ci - 1]].push_back(i);
    }
    st = segtree(n);
    st.build(population);
    while (q--)
    {
        cin >> u >> v >> a;
        query(u - 1, v - 1, a);
    }
    return 0;
}

using namespace std;
int n, t;
string s1, s2;
int count_matching_indexes(void)
{
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (s1[i] == s2[i])
            ++ans;
    return ans;
}
char anything_but(char c, char d)
{
    for (char x = 'a'; x <= 'z'; ++x)
        if (x != c and x != d)
            return x;
    return 0;
}
string solve(void)
{
    string ans(n, ' ');
    int pt = n - t;
    int match_ix = count_matching_indexes();
    int rm_1 = max(0, pt - match_ix);
    int rm_2 = rm_1;
    int pmatch = min(match_ix, pt);
    for (int i = 0; i < n; ++i)
    {
        if (s1[i] != s2[i])
        {
            if (rm_1 > 0)
            {
                ans[i] = s1[i];
                --rm_1;
            }
            else if (rm_2 > 0)
            {
                ans[i] = s2[i];
                --rm_2;
            }
            else
                ans[i] = anything_but(s1[i], s2[i]);
        }
        else
        {
            if (pmatch > 0)
            {
                ans[i] = s1[i];
                --pmatch;
            }
            else
                ans[i] = anything_but(s1[i], s2[i]);
        }
    }
    if (rm_1 > 0 or rm_2 > 0)
        return "-1";
    else
        return ans;
}
int main(void)
{
    cin >> n >> t >> s1 >> s2;
    cout << solve() << endl;
    return 0;
}

using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main(void)
{
    int n, gi;
    multiset<int, greater<int>> ms;
    vector<int> a;
    cin >> n;
    for (int i = 0; i < n * n; ++i)
    {
        cin >> gi;
        ms.insert(gi);
    }
    while ((int)a.size() < n)
    {
        a.push_back(*ms.begin());
        ms.erase(ms.begin());
        for (int i = 0, nc = a.size() - 1; i < nc; ++i)
        {
            for (int j = 0; j < 2; ++j)
            {
                auto it = ms.find(gcd(a[i], a[nc]));
                ms.erase(it);
            }
        }
    }
    for (auto ai : a)
        cout << ai << " ";
    cout << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
int n, a[NMAX];
double f(double x)
{
    double mn = 0, mx = 0, sm = 0;
    for (int i = 0; i < n; i++)
    {
        sm += a[i] - x;
        mn = min(mn, sm);
        mx = max(mx, sm);
    }
    return abs(mx - mn);
};
double ternary_search(double l, double r, function<double(double)> f)
{
    double eps = 5e-12;
    while (r - l > eps)
    {
        double m1 = l + (r - l) / 3.0;
        double m2 = r - (r - l) / 3.0;
        if (f(m1) > f(m2))
            l = m1;
        else
            r = m2;
    }
    return f(l);
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cout << setprecision(15) << fixed << ternary_search(-1e4, 1e4, f) << endl;
    return 0;
}