Task A (9.05.11)

#include <cstdio>
#include <iostream>
#include <string>
#include <cstdlib>

#define N int(1e4 + 5)

using namespace std;

string s;

void fail()
{
    cout << "IMPOSSIBLE";
    exit(0);
}

int a[N];

int main()
{
    freopen("divide.in", "r", stdin);
    freopen("divide.out", "w", stdout);

    int n, k, l, m;
    cin >> n >> k >> l >> m;
    cin >> s;

    for (int i = 0; i < s.size(); i++)
        a[i] = int(s[i] - '0');

    int sum = 0;

    if (l >= k)
    {
        for (int i = 0; i < k; i++)
            sum += a[i];

        if (sum % m)
            fail();

        for (int i = k; i < l; i++)
        {
            sum -= a[i - k];
            sum += a[i];

            if (sum % m)
                fail();
        }
    }
    else if (l)
    {
        for (int i = 0; i < l; i++)
            sum += a[i];

        for (int i = k - 1; i >= l; i--)
        {
            bool ok = false;

            for (int dig = 0; dig < 9; dig++)
            {
                if ((sum + dig) % m == 0)
                {
                    a[i] = dig;
                    sum += dig;
                    ok = true;
                    break;
                }
            }

            if (!ok)
            {
                sum += 9;
                a[i] = 9;
            }
        }

        if (sum % m)
            fail();
    }
    else
    {
        l++;
        for (a[0] = 1; a[0] < 10; a[0]++)
        {
            sum = 0;
            for (int i = 0; i < l; i++)
                sum += a[i];

            for (int i = k - 1; i >= l; i--)
            {
                bool ok = false;

                for (int dig = 0; dig < 9; dig++)
                {
                    if ((sum + dig) % m == 0)
                    {
                        a[i] = dig;
                        sum += dig;
                        ok = true;
                        break;
                    }
                }

                if (!ok)
                {
                    sum += 9;
                    a[i] = 9;
                }
            }

            if (sum % m == 0)
                break;
        }

        if (sum % m)
            fail();
    }

    for (int i = max(l, k); i < n; i++)
    {
        sum -= a[i - k];
        for (int dig = 0; dig < 10; dig++)
        {
            if ((sum + dig) % m == 0)
            {
                a[i] = dig;
                sum += dig;
                break;
            }
        }
    }

    for (int i = 0; i < n; i++)
        cout << a[i];

    return 0;
}