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);
}
int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); }
struct segment_tree
{
    int n;
    vi t;
    segment_tree(vi const &a)
    {
        n = (int)a.size();
        t.resize(4 * n);
        build(a, 1, 0, n - 1);
    }
    inline int left(int v) { return 2 * v; }
    inline int right(int v) { return 2 * v + 1; }
    int merge(int a, int b) { return gcd(a, b); }
    void build(vi const &a, int v, int tl, int tr)
    {
        if (tl == tr)
            t[v] = a[tl];
        else
        {
            int tm = (tl + tr) / 2;
            build(a, left(v), tl, tm);
            build(a, right(v), tm + 1, tr);
            t[v] = merge(t[left(v)], t[right(v)]);
        }
    }
    int query(int ql, int qr) { return query_util(1, 0, n - 1, ql, qr); }
    int query_util(int v, int tl, int tr, int ql, int qr)
    {
        if (ql == tl and qr == tr)
            return t[v];
        else if (ql > qr)
            return 0;
        else
        {
            int tm = (tl + tr) / 2;
            return merge(query_util(left(v), tl, tm, ql, min(tm, qr)),
                         query_util(right(v), tm + 1, tr, max(ql, tm + 1), qr));
        }
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi a(n);
    read_n(a.begin(), n);
    segment_tree seg(a);
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int l = 0, r = 0;
        if (i > 0)
            l = seg.query(0, i - 1);
        if (i < n - 1)
            r = seg.query(i + 1, n - 1);
        ans = max(ans, gcd(r, l));
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using spii = set<pii>;
const int NMAX = 1e5 + 11;
pii EMPTY = make_pair(INT_MAX, -2);
int n, cur_time = 0;
int sz[NMAX], depth[NMAX], visit_time[NMAX];
bool black[NMAX];
vi tree[NMAX];
spii seg[4 * NMAX];
void add_edge(int u, int v)
{
    tree[u].push_back(v);
    tree[v].push_back(u);
}
void visit(int u, int d)
{
    depth[u] = d;
    visit_time[u] = cur_time;
}
void traverse(int u, int d)
{
    int local_time = cur_time;
    visit(u, d);
    for (int v : tree[u])
    {
        if (visit_time[v] == -1)
            traverse(v, d + 1);
    }
    sz[u] = cur_time - local_time;
}
void build(int v, int tl, int tr)
{
    if (tl == tr)
        seg[v] = {EMPTY};
    else
    {
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm + 1, tr);
        seg[v] = {EMPTY};
    }
}
pii query(int v, int tl, int tr, int x)
{
    int pos = visit_time[x];
    if (tl == tr and pos == tl)
        return *seg[v].begin();
    else if (tl <= pos and pos <= tr)
    {
        int tm = (tl + tr) / 2;
        spii acc_ans;
        acc_ans.insert(*seg[v].begin());
        acc_ans.insert(query(v * 2, tl, tm, x));
        acc_ans.insert(query(v * 2 + 1, tm + 1, tr, x));
        return *acc_ans.begin();
    }
    else
        return EMPTY;
}
void update(int v, int tl, int tr, int ql, int qr, int x)
{
    if (ql > qr)
        return;
    if (tl == ql and tr == qr)
    {
        if (not black[x])
            seg[v].insert({depth[x], x});
        else
            seg[v].erase({depth[x], x});
    }
    else
    {
        int tm = (tl + tr) / 2;
        update(v * 2, tl, tm, ql, min(qr, tm), x);
        update(v * 2 + 1, tm + 1, tr, max(ql, tm + 1), qr, x);
    }
}
int main(void)
{
    int q, u, v, type;
    cin >> n >> q;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v;
        add_edge(u - 1, v - 1);
    }
    memset(visit_time, -1, NMAX);
    traverse(0, 0);
    build(1, 0, n - 1);
    while (q--)
    {
        cin >> type >> v;
        v -= 1;
        if (type == 1)
            cout << query(1, 0, n - 1, v).second + 1 << endl;
        else
        {
            update(1, 0, n - 1, visit_time[v], visit_time[v] + sz[v] - 1, v);
            black[v] = !black[v];
        }
    }
    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));
}
vi solve(int n, vi a)
{
    set<ii> sorted;
    for (int i = 0; i < n; ++i)
        sorted.emplace(a[i], i);
    vi dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = 1;
        auto it = sorted.lower_bound({a[i - 1] - 1, i - 1});
        if (it == sorted.begin() or prev(it)->first != a[i - 1] - 1)
            continue;
        auto [aj, j] = *prev(it);
        dp[i] += dp[j + 1];
    }
    int i = distance(dp.begin(), max_element(dp.begin(), dp.end())) - 1, m = dp[i + 1],
        x = a[i];
    vi ans(m);
    for (int j = m - 1; j >= 0; --j)
    {
        ans[j] = i + 1;
        auto it = sorted.lower_bound({x - 1, i});
        if (j > 0)
        {
            it--;
            x = it->first;
            i = it->second;
        }
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi a(n);
    read_n(a.begin(), n);
    vi ans = solve(n, a);
    cout << (int)ans.size() << endl;
    write(ans.begin(), ans.end(), " "), cout << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
array<ii, 26> dims;
enum ttype
{
    LPAR,
    RPAR,
    MAT,
    END
};
struct Token
{
    ttype type;
    char attr;
};
struct Parser
{
    string input;
    int ix, n;
    Parser(string input) : input(input), ix(0) { n = (int)input.size(); }
    Token get_token(void) const
    {
        if (ix == n)
            return {END, 0};
        else
        {
            char c = input[ix];
            if (isalpha(c))
                return {MAT, c};
            else if (c == '(')
                return {LPAR, c};
            else if (c == ')')
                return {RPAR, c};
            else
                throw -1;
        }
    }
    void eat(ttype t)
    {
        if (t != get_token().type)
            throw -1;
        ++ix;
    }
    inline ll cost(ii a, ii b) { return a.first * a.second * b.second; }
    pair<ii, ll> expr(void)
    {
        Token tkn = get_token();
        if (tkn.type == MAT)
        {
            eat(MAT);
            return {dims[tkn.attr - 'A'], 0};
        }
        else if (tkn.type == LPAR)
        {
            eat(LPAR);
            pair<ii, ll> lmat = expr();
            pair<ii, ll> rmat = expr();
            eat(RPAR);
            if (lmat.first.second == rmat.first.first)
                return {{lmat.first.first, rmat.first.second},
                        lmat.second + rmat.second +
                            cost(lmat.first, rmat.first)};
            else
                throw -1;
        }
        else
            throw -1;
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    while (n--)
    {
        char name;
        int rows, cols;
        cin >> name >> rows >> cols;
        dims[name - 'A'] = {rows, cols};
    }
    string line;
    while (cin >> line)
    {
        try
        {
            Parser p(line);
            cout << p.expr().second << endl;
        }
        catch (int e)
        {
            cout << "error" << 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;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using predicate = function<bool(int)>;
int const KMAX = 100 + 2;
int const NMAX = 10 + 2;
int const XMAX = 100 + 2;
int n, x, t, k, p[2 * KMAX + 1], f[2 * KMAX + 1];
int dp[2 * KMAX][2 * (NMAX + 1)][NMAX * XMAX];
int bs(int l, int r, predicate p)
{
    while (l < r)
    {
        int m = l + (r - l + 1) / 2;
        if (p(m))
            l = m;
        else
            r = m - 1;
    }
    return l;
}
inline int ceil(int a, int b) { return (a + b - 1) / b; }
inline int cost(int y) { return ceil(11 * (y + n * t), 10); }
double solve(void)
{
    memset(dp, 0, sizeof dp);
    n += 1;
    int max_money = bs(0, n * x, [](int y) { return cost(y) <= (n * x); });
    for (int i = 1; i <= 2 * k + 1; ++i)
    {
        for (int q = 0; q <= (2 * n); ++q)
        {
            for (int m = 0; m <= max_money; ++m)
            {
                auto &ans = dp[i][q][m];
                int new_rem = m - p[i - 1];
                ans = max(ans, dp[i - 1][q][m]);
                if (new_rem >= 0 and q > 0)
                    ans = max(ans, dp[i - 1][q - 1][new_rem] + f[i - 1]);
            }
        }
    }
    int ans = 0;
    for (int q = 0; q <= (2 * n); ++q)
        ans = max(ans, dp[2 * k + 1][q][max_money]);
    return (ans / double(n));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    while (cin >> n >> x >> t >> k and n != 0)
    {
        memset(p, 0, sizeof p);
        memset(f, 0, sizeof f);
        for (int i = 0; i < k; ++i)
        {
            int fj;
            cin >> p[2 * i];
            p[2 * i + 1] = p[2 * i];
            f[2 * i] = 0;
            for (int j = 0; j <= n; ++j)
                cin >> fj, f[2 * i] += fj;
            f[2 * i + 1] = f[2 * i];
        }
        cout << fixed << setprecision(2) << solve() << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
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));
}
int id(char c)
{
    switch (c)
    {
    case 'd':
        return 4;
    case 'r':
        return 3;
    case 'a':
        return 2;
    case 'h':
        return 1;
    default:
        return 0;
    }
}
ll solve(int n, string s, vll a)
{
    string t(" hard");
    vi sorted[5];
    fill(sorted, sorted + 5, vi(1, 0));
    for (int i = 1; i <= n; ++i)
    {
        int j = id(s[i]);
        if (j > 0)
            sorted[j].push_back(i);
    }
    for (int i = 1; i <= 4; ++i)
    {
        if ((int)sorted[i].size() == 0)
            return 0;
        sort(sorted[i].begin(), sorted[i].end());
    }
    vll dp(n + 2, 1e17);
    int fst = *sorted[id('h')].begin();
    sorted[0] = {-1, n + 1};
    dp[fst] = a[fst];
    dp[0] = 0;
    for (int i = fst + 1; i <= n; ++i)
    {
        int idd = id(s[i]);
        if (idd > 0)
        {
            auto &ans = dp[i];
            auto it = lower_bound(sorted[idd].begin(), sorted[idd].end(), i);
            ans = min(ans, dp[*prev(it)] + a[i]);
            it = lower_bound(sorted[idd - 1].begin(), sorted[idd - 1].end(), i);
            ans = min(ans, dp[(n + 2 + *prev(it)) % (n + 2)]);
        }
    }
    return dp[sorted[id('d')].back()];
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vll a(n + 1);
    string s(n + 1, ' ');
    read_n(next(s.begin()), n);
    read_n(next(a.begin()), n);
    cout << solve(n, s, a) << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<ll>;
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 <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);
}
ii med = {-1, -1};
set<ii> bot, top;
ll sbot, stop;
void fix()
{
    int m = 1 + (int)bot.size() + (int)top.size();
    if ((int)bot.size() < (m - 1) / 2)
    {
        bot.insert(med), sbot += med.first;
        med = *top.begin();
        top.erase(med), stop -= med.first;
    }
    if ((int)bot.size() > (m - 1) / 2)
    {
        top.insert(med), stop += med.first;
        med = *prev(bot.end());
        bot.erase(med), sbot -= med.first;
    }
}
void add(ii x)
{
    if (med.first == -1)
    {
        med = x;
        return;
    }
    if (x < med)
        bot.insert(x), sbot += x.first;
    else
        top.insert(x), stop += x.first;
    fix();
}
void rem(ii x)
{
    if (x == med)
    {
        med = *top.begin();
        top.erase(med), stop -= med.first;
    }
    else if (x < med)
        bot.erase(x), sbot -= x.first;
    else
        top.erase(x), stop -= x.first;
    fix();
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vi a(n);
    read_n(a.begin(), n);
    if (k == 1)
    {
        for (int i = 0; i < n; ++i)
            cout << 0 << " ";
        cout << endl;
        return 0;
    }
    for (int i = 0; i < n; ++i)
    {
        add({a[i], i});
        if (i >= k - 1)
        {
            auto left = ((int)bot.size() * med.first - sbot);
            auto right = (stop - (int)top.size() * med.first);
            cout << left + right << " ";
            rem({a[i - k + 1], i - k + 1});
        }
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
int solve(string s, string t)
{
    int n = (int)s.size(), m = (int)t.size();
    vector<vi> dp(n + 1, vi(m + 1, 0));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            auto &ans = dp[i][j];
            ans = max(ans, dp[i - 1][j]);
            ans = max(ans, dp[i][j - 1]);
            if (s[i - 1] == t[j - 1])
                ans = max(ans, dp[i - 1][j - 1] + 1);
        }
    }
    return dp[n][m];
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    string s, t;
    while (getline(cin, s) and getline(cin, t))
    {
        cout << solve(s, t) << 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);
}
int const INF = 1e9;
int n, atime, m1, m2;
vi t, dep_left, dep_right, acc_time;
int solve(void)
{
    vector<vi> dp(n + 2, vi(atime + 1, INF));
    dp[1][0] = 0;
    for (int tt = 1; tt <= atime; ++tt)
    {
        for (int i = 1; i <= n; ++i)
        {
            auto &ans = dp[i][tt];
            ans = min(INF, dp[i][tt - 1] + 1);
            if (i - 1 >= 1 and tt - acc_time[i] >= 0 and
                binary_search((dep_left).begin(), (dep_left).end(), tt - acc_time[i]))
            {
                ans = min(ans, dp[i - 1][tt - t[i]]);
            }
            if (i + 1 <= n and tt - (acc_time[n] - acc_time[i]) >= 0 and
                binary_search((dep_right).begin(), (dep_right).end(), tt - (acc_time[n] - acc_time[i])))
            {
                ans = min(ans, dp[i + 1][tt - t[i + 1]]);
            }
        }
    }
    return dp[n][atime] == INF ? -1 : dp[n][atime];
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int tc = 1;
    while (cin >> n and n)
    {
        cin >> atime;
        t.resize(n + 1, 0), read_n(t.begin() + 2, n - 1);
        acc_time.resize(n + 1, 0), partial_sum((t).begin(), (t).end(), begin(acc_time));
        cin >> m1;
        dep_left.resize(m1, 0), read_n(dep_left.begin(), m1);
        cin >> m2;
        dep_right.resize(m2, 0), read_n(dep_right.begin(), m2);
        cout << "Case Number " << tc << ": ";
        if (auto ans = solve(); ans != -1)
            cout << ans << endl;
        else
            cout << "impossible" << endl;
        tc++;
    }
    return 0;
}