Ta sẽ thực hiện ba phép thử:

Hai phép thử đầu tiên:

• Giả sử ta có số ~L = 2003~, và ~N = 2~.
• Ta lấy ~N~ chữ số đầu của ~L~ là ~20~.
• Lúc này, ta viết ~20~ một vài lần, cho đến khi số ta thu được ~\ge~ ~L~.
• Nếu số ta thu được, không thể ~\ge~ ~L~, ta sẽ lấy ~N~ chữ số đầu của ~L~, và cộng thêm ~1~, như trong ví dụ ta sẽ được ~21~.
• Lúc này, ta viết ~21~ một vài lần, cho đến khi số ta thu được l~\ge~ ~L~.
• Nếu sau cả hai lần thử đó, vẫn không có số thỏa mãn, ta sẽ đến với phép thử số ba.

Phép thử thứ ba:

• Gọi ~l~ là số chữ số của ~L~, và ~r~ là số chữ số của ~R~.
• Nếu giữa ~l~ và ~r~ (không tính hai biên) tồn tại một số chia hết cho ~n~ (giả sử là ~x~), kết quả sẽ là ~111 ... 111~ (~x~ chữ số ~1~).
• Nếu vẫn không tồn tại, ta in ra ~-1~.

Độ phức tạp: ~O (k * log (k))~, với ~k~ là số chữ số của ~R~.

Code mẫu:

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"

const int N = 5e5 + 9;
const int LG = 17;

int n, k, a[N], st[2][LG + 1][N], lg[N];

bool cmp (const string &a, const string &b){
    if (a.size () < b.size ()) return 1;
    if (a.size () > b.size ()) return 0;
    for (int i = 0; i < a.size (); i++){
        if (a[i] > b[i]) return 0;
        if (a[i] < b[i]) return 1;
    }
    return 1;
}

bool cmpr (const string &a, const string &b){
    if (a.size () < b.size ()) return 0;
    if (a.size () > b.size ()) return 1;
    for (int i = 0; i < a.size (); i++){
        if (a[i] < b[i]) return 0;
        if (a[i] > b[i]) return 1;
    }
    return 1;
}

string sum (string str1, string str2){
    if (str1.size () > str2.size ()) swap (str1, str2);
    string str = "";
    int n1 = str1.size (), n2 = str2.size ();
    reverse (str1.begin (), str1.end ());
    reverse (str2.begin (), str2.end ());
    int carry = 0;
    for (int i = 0; i < n1; i++){
        int sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
        str.push_back (sum % 10 + '0');
        carry = sum / 10;
    }
    for (int i = n1; i < n2; i++){
        int sum = ((str2[i] - '0') + carry);
        str.push_back (sum % 10 + '0');
        carry = sum / 10;
    }
    if (carry) str.push_back (carry + '0');
    reverse (str.begin (), str.end ());
    return str;
}

void sub1 (int l, int r){
    for (int i = l; i <= r; i++){
        string s = to_string (i);
        if (s.size () % n != 0) continue;
        bool flag = 1;
        for (int j = 0; j < s.size (); j++){
            if (s[j] != s[j % n]){
                flag = 0; break;
            }
        }
        if (flag){
            cout << i; exit (0);
        }
    }
    cout << -1; exit (0);
}

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    if (fopen ("input.txt", "r")){
        freopen ("input.txt", "r", stdin);
        freopen ("output.txt", "w", stdout);
    }
    string l, r; cin >> l >> r >> n;
    if (r.size () <= 6) sub1 (stoll (l), stoll (r));
    for (int i = l.size () + 1; i <= r.size (); i++){
        if (i % n == 0){
            string res = "";
            for (int j = 1; j <= i; j++) res += "1";
            if (cmp (res, r) && cmpr (res, l)){ 
                cout << res; exit (0);
            }
            res = "";
            for (int j = 1; j <= i; j++){
                if (j % n == 1) res += "1";
                else res += "0";
            }
            if (cmp (res, r) && cmpr (res, l)){ 
                cout << res; exit (0);
            }
        }
    }
    string res = "";
    for (int i = 0; i < n; i++) res += l[i];
    string res1 = sum (res, "1");
    string res2 = "", res3 = "";
    while (res2.size () < l.size ()) res2 += res;
    while (res3.size () < l.size ()) res3 += res1;
    if (cmp (res2, r) && cmpr (res2, l)) cout << res2;
    else if (cmp (res3, r) && cmpr (res3, l)) cout << res3;
    else cout << -1;
}