using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename T>
struct Dijkstra
{
    using Graph = vector<vector<pair<int, T>>>;
    T INF = numeric_limits<T>::max();
    Graph g;
    int src, m = 0;
    vector<int> p;
    vector<T> d;
    Dijkstra(int n) : g(n), p(n), d(n){};
    void add_edge(int u, int v, T w = 1) { g[u].emplace_back(v, w), m++; }
    void run_dense(int src = 0)
    {
        clear(src);
        int n = g.size();
        vector<bool> vis(n, false);
        d[src] = 0;
        for (int i = 0; i < n; i++)
        {
            int u = -1;
            for (int v = 0; v < n; v++)
                if (not vis[v] and (u == -1 or d[v] < d[u]))
                    u = v;
            if (d[u] == INF)
                break;
            vis[u] = true;
            for (auto [v, w] : g[u])
            {
                if (d[u] + w < d[v])
                {
                    d[v] = d[u] + w;
                    p[v] = u;
                }
            }
        }
    }
    void run_sparse(int src = 0)
    {
        clear(src);
        set<pair<T, int>> q;
        d[src] = 0;
        q.emplace(d[src], src);
        while (!q.empty())
        {
            int u = q.begin()->second;
            q.erase(q.begin());
            for (auto [v, w] : g[u])
            {
                if (d[u] + w < d[v])
                {
                    q.erase({d[v], v});
                    d[v] = d[u] + w;
                    p[v] = u;
                    q.emplace(d[v], v);
                }
            }
        }
    }
    vector<vector<pair<int, T>>> shortest_path_DAG(void) const
    {
        int n = g.size();
        vector<vector<pair<int, T>>> dag(n);
        for (int v = 0; v < n; ++v)
            if (auto u = p[v]; u != -1)
                dag[u].emplace_back(v, d[v] - d[u]);
        return dag;
    }
    vector<int> shortest_path(int u) const
    {
        if (d[u] == INF)
            return {};
        vector<int> path;
        for (int v = u; v != src; v = p[v])
            path.push_back(v);
        path.push_back(src);
        reverse(begin(path), end(path));
        return path;
    }
    void clear(int src)
    {
        this->src = src;
        fill(begin(p), end(p), -1);
        fill(begin(d), end(d), INF);
    }
    void operator()(int src = 0)
    {
        long long n = g.size();
        if (n * n + m < (n + m) * log2(n))
            run_dense(src);
        else
            run_sparse(src);
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    Dijkstra<ll> dijkstra(n);
    for (int i = 0; i < m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w, u--, v--;
        dijkstra.add_edge(u, v, ll(w));
        dijkstra.add_edge(v, u, ll(w));
    }
    dijkstra(0);
    if (auto ans = dijkstra.shortest_path(n - 1); not ans.empty())
    {
        for (auto x : ans)
            cout << x + 1 << " ";
        cout << endl;
    }
    else
        cout << -1 << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 50 + 11;
int n, m;
bool painted[NMAX][NMAX];
vector<ii> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
inline bool valid(int r, int c)
{
    return 0 <= r and r < n and 0 <= c and c < m;
}
vector<ii> get_neighbors(int r, int c)
{
    vector<ii> ans;
    for (auto [dr, dc] : directions)
        if (valid(r + dr, c + dc) and painted[r + dr][c + dc])
            ans.emplace_back(r + dr, c + dc);
    return ans;
}
bool bfs(int r, int c, vector<ii> targets)
{
    vector<vector<bool>> visited(n, vector<bool>(m, 0));
    queue<ii> frontier;
    visited[r][c] = true;
    frontier.emplace(r, c);
    while (not frontier.empty())
    {
        auto [r, c] = frontier.front();
        frontier.pop();
        if (auto it = find(targets.begin(), targets.end(), make_pair(r, c)); it != targets.end())
        {
            targets.erase(it);
            if ((int)targets.size() == 0)
            {
                return true;
            }
        }
        for (auto [rr, cc] : get_neighbors(r, c))
        {
            if (not visited[rr][cc])
            {
                frontier.emplace(rr, cc);
                visited[rr][cc] = true;
            }
        }
    }
    return false;
}
int main(void)
{
    cin >> n >> m;
    int asz = 0;
    char ch;
    for (int r = 0; r < n; ++r)
        for (int c = 0; c < m; ++c)
            cin >> ch, painted[r][c] = (ch == '#'), asz += painted[r][c];
    if (asz <= 2)
        cout << -1 << endl;
    else
    {
        for (int r = 0; r < n; ++r)
        {
            for (int c = 0; c < m; ++c)
            {
                if (not painted[r][c])
                    continue;
                auto neighbors = get_neighbors(r, c);
                auto [rr, cc] = neighbors.back();
                neighbors.pop_back();
                painted[r][c] = false;
                if ((int)neighbors.size() == 0 or not bfs(rr, cc, neighbors))
                {
                    cout << 1 << endl;
                    return 0;
                }
                painted[r][c] = true;
            }
        }
        cout << 2 << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 1e5 + 11;
int const LMAX = 18;
int n, val[NMAX], tin[NMAX], tout[NMAX], up[NMAX][LMAX + 1], ssize[NMAX],
    depth[NMAX], timer;
ii edges[NMAX];
vi g[NMAX];
void precompute_lca(int u, int p)
{
    tin[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i <= LMAX; ++i)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto v : g[u])
        if (v != p)
            precompute_lca(v, u);
    tout[u] = ++timer;
}
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = LMAX; i >= 0; --i)
    {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
void precompute_sz(int u, int p = 0)
{
    ssize[u] = val[u];
    depth[u] = depth[p] + 1;
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        precompute_sz(v, u);
        ssize[u] += ssize[v];
    }
}
int main(void)
{
    int k, u, v, root = 1;
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edges[i] = {u, v};
    }
    precompute_lca(root, root);
    cin >> k;
    while (k--)
    {
        cin >> u >> v;
        val[lca(u, v)] -= 2;
        val[u] += 1;
        val[v] += 1;
    }
    precompute_sz(root);
    for (int i = 0; i < n - 1; ++i)
    {
        auto [u, v] = edges[i];
        if (depth[u] < depth[v])
            swap(u, v);
        cout << ssize[u] << " ";
    }
    cout << endl;
    return 0;
}

using namespace std;
int n;
int v[3];
int mem[4010];
bool vis[4010];
int dp(int remainder)
{
    if (remainder == 0)
        return 0;
    else if (remainder < 0)
        return INT_MIN;
    if (vis[remainder])
        return mem[remainder];
    int ans = INT_MIN;
    for (int i = 0; i < 3; ++i)
    {
        ans = max(ans, 1 + dp(remainder - v[i]));
    }
    vis[remainder] = true;
    mem[remainder] = ans;
    return ans;
}
int main(void)
{
    cin >> n >> v[0] >> v[1] >> v[2];
    cout << dp(n) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
string reverse(string s)
{
    reverse(s.begin(), s.end());
    return s;
}
string solve(string s)
{
    string ans;
    vi alpha(26, 0);
    for (auto c : s)
        alpha[c - 'A'] += 1;
    int oddix = -1;
    for (int i = 0; i < (int)alpha.size(); ++i)
    {
        if (alpha[i] % 2 == 1)
        {
            if (oddix != -1)
                return "NO SOLUTION";
            oddix = i;
        }
        else if (alpha[i] > 0)
        {
            ans.resize(ans.size() + alpha[i] / 2, i + 'A');
        }
    }
    return ans + string(alpha[oddix], oddix + 'A') + reverse(ans);
}
int main(void)
{
    string s;
    cin >> s;
    cout << solve(s) << endl;
    return 0;
}

using namespace std;
bool solve(int a, int b)
{
    if (a < b)
        swap(a, b);
    int diff = a - b;
    if (b < diff)
        return false;
    a -= 2 * diff;
    b -= diff;
    return (a % 3 == 0);
}
int main(void)
{
    int t, a, b;
    cin >> t;
    while (t--)
    {
        cin >> a >> b;
        cout << (solve(a, b) ? "YES" : "NO") << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
vi prefix_function(string s)
{
    int n = s.size();
    vi pi(n, 0);
    for (int i = 1; i < n; ++i)
    {
        int j = pi[i - 1];
        while (j > 0 and s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            ++j;
        pi[i] = j;
    }
    return pi;
}
int solve(string s, string p)
{
    int m = p.size();
    auto pi = prefix_function(p + '#' + s);
    return count_if(pi.begin(), pi.end(), [m](int x) { return x == m; });
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    string s, p;
    cin >> s >> p;
    cout << solve(s, p) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 2e5 + 11;
const int PTWO = 32;
int _succ[NMAX][PTWO];
int succ(int x, int k, int i = 0)
{
    if (k == 0)
        return x;
    if (k == 1)
        return _succ[x][i];
    int rem = k % 2;
    if (rem == 1)
        return _succ[succ(x, k / 2, i + 1)][i];
    else
        return succ(x, k / 2, i + 1);
}
int main(void)
{
    int n, q, x, k;
    cin >> n >> q;
    for (int u = 1; u <= n; ++u)
        cin >> _succ[u][0];
    for (int p = 1; p < PTWO; ++p)
    {
        for (int u = 1; u <= n; ++u)
        {
            _succ[u][p] = _succ[_succ[u][p - 1]][p - 1];
        }
    }
    while (q--)
    {
        cin >> x >> k;
        cout << succ(x, k) << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
template <long long M, typename T = long long>
class NumMod
{
    static_assert(std::is_integral<T>::value, "Integral required.");
    using NM = NumMod<M, T>;
    T x;
  public:
    static const ll MOD = M;
    NumMod(T x) : x(x) {}
    NumMod() : x(0) {}
    NumMod(NM const &y) : x(y.v()) {}
    explicit operator T() const { return x; }
    T v(void) const { return (this->x + M) % M; }
    NM & operator=(NM const &y)
    {
        this->x = y.v();
        return *this;
    }
    NM &operator=(T const &y) { return this->operator=(NM(y)); }
    NM &operator+=(NM const &y) { return this->operator=(operator+(y)); }
    NM &operator-=(NM const &y) { return this->operator=(operator-(y)); }
    NM &operator*=(NM const &y) { return this->operator=(operator*(y)); }
    NM operator+(NM const &y) const { return (v() + y.v()) % M; }
    NM operator+(T const &y) const { return this->operator+(NM(y)); }
    NM operator-(NM const &y) const { return (v() - y.v()) % M; }
    NM operator-(T const &y) const { return this->operator-(NM(y)); }
    NM operator*(NM const &y) const { return (v() * y.v()) % M; }
    NM operator*(T const &y) const { return this->operator*(NM(y)); }
};
ll const MOD = 1e9 + 7;
using NM = NumMod<MOD, ll>;
ll solve(int n, int m, vi a)
{
    vector<vector<NM>> dp(n + 1, vector<NM>(m + 2, 0));
    if (a[1] == 0)
        for (int x = 1; x <= m; ++x)
            dp[1][x] = 1;
    else
        dp[1][a[1]] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (a[i] == 0)
            for (int x = 1; x <= m; ++x)
                dp[i][x] = dp[i - 1][x - 1] + dp[i - 1][x] + dp[i - 1][x + 1];
        else
        {
            dp[i][a[i]] =
                dp[i - 1][a[i] - 1] + dp[i - 1][a[i]] + dp[i - 1][a[i] + 1];
        }
    }
    return ll(accumulate(dp[n].begin(), dp[n].end(), NM(0)));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vi a(n + 1, 0);
    read_n(next(a.begin()), n);
    cout << solve(n, m, a) << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
using si = set<int>;
int main(void)
{
    int n;
    vi x;
    si sums;
    cin >> n;
    x.resize(n);
    for (auto &xi : x)
        cin >> xi;
    for (auto xi : x)
    {
        si temp;
        for (auto sum : sums)
            temp.insert(sum + xi);
        sums.insert(xi);
        sums.insert(temp.begin(), temp.end());
    }
    cout << sums.size() << endl;
    for (auto sum : sums)
    {
        cout << sum << " ";
    }
    cout << endl;
    return 0;
}