using namespace std;
using ll = long long;
using vi = vector<int>;
int const AMAX = 2e6 + 11;
bitset<AMAX> is_prime;
void sieve()
{
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    for (ll i = 2; i < AMAX; ++i)
        if (is_prime[i])
            for (ll j = i * i; j < AMAX; j += i)
                is_prime[j] = 0;
}
int main(void)
{
    int n;
    vi a, ans;
    cin >> n;
    a.resize(n);
    for (auto &ai : a)
        cin >> ai;
    sort(a.begin(), a.end());
    sieve();
    if (a[0] == 1)
    {
        auto it = upper_bound(a.begin(), a.end(), 1);
        int ones = distance(a.begin(), it);
        int x = -1;
        for (; it != a.end(); ++it)
        {
            if (is_prime[*it + 1])
            {
                x = *it;
                break;
            }
        }
        ans = vi(a.begin(), a.begin() + ones);
        if (x != -1)
            ans.push_back(x);
    }
    if ((int)ans.size() < 2)
    {
        for (int i = 0; i < n - 1; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                if (is_prime[a[i] + a[j]])
                {
                    ans.clear();
                    ans.push_back(a[i]), ans.push_back(a[j]);
                    break;
                }
            }
            if ((int)ans.size() == 2)
                break;
        }
    }
    if ((int)ans.size() < 1)
        ans = {a[0]};
    cout << ans.size() << endl;
    for (auto x : ans)
        cout << x << " ";
    cout << endl;
    return 0;
}

using namespace std;
string s;
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)
{
    int n = s.size();
    char last = s[0];
    for (int i = 1; i < n - 1; ++i)
    {
        if (s[i] == last)
            s[i] = anything_but(last, s[i + 1]);
        last = s[i];
    }
    if (n != 1 and s[n - 1] == last)
        s[n - 1] = anything_but(last, last);
    return s;
}
int main(void)
{
    cin >> s;
    cout << solve() << endl;
    return 0;
}

using namespace std;
using vs = vector<string>;
int n, m;
vs dictionary;
string cpattern;
void match(int pos, string ans)
{
    if (pos == cpattern.size())
    {
        cout << ans << endl;
        return;
    }
    if (cpattern[pos] == '0')
    {
        for (int i = 0; i < 10; ++i)
            match(pos + 1, ans + to_string(i));
    }
    else
    {
        for (int i = 0; i < n; ++i)
            match(pos + 1, ans + dictionary[i]);
    }
}
int main(void)
{
    string word;
    string pattern;
    while (cin >> n)
    {
        for (int i = 0; i < n; ++i)
        {
            cin >> word;
            dictionary.push_back(word);
        }
        cin >> m;
        cout << "--" << endl;
        for (int j = 0; j < m; ++j)
        {
            cin >> pattern;
            cpattern = pattern;
            match(0, "");
        }
        dictionary = vs();
    }
    return 0;
}

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;
}