using namespace std;
using iii = tuple<int, int, int>;
using vi = vector<int>;
using viii = vector<iii>;
int main(void)
{
    int n, x, y;
    viii events;
    vi ans, rooms;
    cin >> n;
    ans = vi(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> x >> y;
        events.push_back({x, -1, i});
        events.push_back({y, 1, i});
    }
    sort(events.begin(), events.end());
    int occupied = 0, max_rooms = 0;
    for (auto [t, sign, i] : events)
    {
        if (sign == 1)
            rooms.push_back(ans[i]);
        else if (occupied == (int)rooms.size())
            ans[i] = ++max_rooms;
        else
            ans[i] = rooms[occupied++];
    }
    cout << max_rooms << endl;
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}

using namespace std;
using si = set<int>;
using msi = multiset<int>;
int main(void)
{
    int x, n, point, left, right;
    cin >> x >> n;
    si points = {0, x};
    msi lengths = {x};
    while (n--)
    {
        cin >> point;
        auto it = points.upper_bound(point);
        left = *prev(it);
        right = *it;
        lengths.erase(lengths.find(right - left));
        lengths.insert(point - left);
        lengths.insert(right - point);
        points.insert(it, point);
        cout << *lengths.rbegin() << " ";
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
int main(void)
{
    int n, x;
    cin >> n >> x;
    vi h(n), s(n);
    for (auto &hi : h)
        cin >> hi;
    for (auto &si : s)
        cin >> si;
    vvi dp(n + 1, vi(x + 1, 0));
    for (int i = 1; i <= n; ++i)
    {
        for (int c = 1; c <= x; ++c)
        {
            dp[i][c] = dp[i - 1][c];
            if (c - h[i - 1] >= 0)
                dp[i][c] = max(dp[i][c], dp[i - 1][c - h[i - 1]] + s[i - 1]);
        }
    }
    cout << dp[n][x] << 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;
const int NMAX = 1e5 + 11;
const int INF = 1e7;
int n, d1[NMAX], d2[NMAX];
void manacher(const string &s)
{
    for (int i = 0, l = 0, r = -1; i < n; ++i)
    {
        int j = l + r - i;
        int k = (i > r) ? 1 : min(d1[j], j - l + 1);
        while (0 <= i - k and i + k < n and s[i - k] == s[i + k])
            ++k;
        d1[i] = k--;
        if (i + k > r)
        {
            l = i - k;
            r = i + k;
        }
    }
    for (int i = 0, l = 0, r = -1; i < n; ++i)
    {
        int j = l + r - i;
        int k = (i > r) ? 0 : min(d2[j + 1], j - l + 1);
        while (0 <= i - k - 1 and i + k < n and s[i - k - 1] == s[i + k])
            ++k;
        d2[i] = k--;
        if (i + k > r)
        {
            l = i - k - 1;
            r = i + k;
        }
    }
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    int i1, i2, k1, k2, r1, r2, l1, l2, l;
    while (cin >> s)
    {
        memset(d1, 0, sizeof(d1));
        memset(d2, 0, sizeof(d2));
        n = s.size();
        manacher(s);
        i1 = i2 = n - 1;
        for (int i = n - 1; i >= 0; --i)
        {
            k1 = d1[i], k2 = d2[i];
            r1 = i + d1[i] - 1, r2 = i + d2[i] - 1;
            if (r1 == n - 1 and k1 > d1[i1])
                i1 = i;
            if (r2 == n - 1 and k2 > d2[i2])
                i2 = i;
        }
        l1 = i1 - (d1[i1] - 1);
        l2 = i2 - d2[i2];
        l = min(l1, (d2[i2] > 0 ? l2 : INF));
        if (l == 0)
        {
            cout << s << endl;
        }
        else
        {
            cout << s;
            for (int i = l - 1; i >= 0; --i)
                cout << s[i];
            cout << endl;
        }
    }
    return 0;
}

using namespace std;
using ll = long long;
ll qn;
ll trial_division(ll n)
{
    ll count = 0;
    ll max_prime = -1;
    for (ll d = 2; d * d <= n; d++)
    {
        if (n % d == 0)
            ++count;
        while (n % d == 0)
        {
            n /= d;
            max_prime = max(max_prime, d);
        }
    }
    if (n > 1 and n != qn)
    {
        max_prime = max(max_prime, n);
        ++count;
    }
    if (count >= 2)
        return max_prime;
    return -1;
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    while (cin >> qn and qn)
    {
        cout << trial_division(abs(qn)) << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
vi prefix_function(string s)
{
    int n = (int)s.length();
    vi pi(n);
    for (int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(NULL);
    int t, n, ix, maxp;
    string s;
    cin >> t;
    while (t--)
    {
        cin >> s;
        n = s.size();
        auto pi = prefix_function(s);
        ix = maxp = 0;
        for (int i = 0; i < n; ++i)
        {
            if (pi[i] > maxp and 2 * pi[i] == i + 1)
            {
                ix = i;
                maxp = pi[i];
            }
        }
        string ans(ix + 1, ' ');
        for (int i = 0; i <= ix; ++i)
            ans[i] = s[i];
        for (int j = (n - ix - 1); j < n - ix + 8 - 1; ++j)
            cout << s[j % (ix + 1)];
        cout << "..." << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    int n, x;
    vi dp;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        auto it = lower_bound(dp.begin(), dp.end(), x);
        if (it != dp.end())
            *it = x;
        else
            dp.push_back(x);
    }
    cout << dp.size() << 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, m;
vi g[NMAX];
ii edges[NMAX];
bool color[NMAX];
bool bfs(int src)
{
    queue<int> frontier;
    vector<bool> visited(n + 1, false);
    frontier.push(src);
    color[src] = 1;
    while (not frontier.empty())
    {
        auto u = frontier.front();
        frontier.pop();
        for (auto v : g[u])
        {
            if (not visited[v])
            {
                frontier.push(v);
                color[v] = !color[u];
                visited[v] = true;
            }
            else if (visited[v] and color[v] == color[u])
                return false;
        }
    }
    return true;
}
int main(void)
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edges[i] = {u, v};
    }
    if (bfs(1))
    {
        cout << "YES" << endl;
        for (int i = 0; i < m; ++i)
        {
            auto [u, v] = edges[i];
            cout << color[u];
        }
        cout << endl;
    }
    else
        cout << "NO" << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
using mii = map<int, int>;
int main(void)
{
    int n;
    cin >> n;
    vi k(n);
    mii freq;
    for (auto &ki : k)
        cin >> ki;
    int ans = 0;
    for (int i = 0, j = 0; i < n; ++i)
    {
        while (j < n and freq[k[j]] == 0)
        {
            ++freq[k[j]];
            ++j;
        }
        ans = max(j - i, ans);
        freq[k[i]]--;
    }
    cout << ans << endl;
    return 0;
}