Problem: You are given two integers l and r.

Let's call an integer x modest, if l ≤ x ≤ r.

Find a string of length n, consisting of digits, which has the largest possible number of substrings, which make a modest integer. Substring having leading zeros are not counted. If there are many answers, find lexicographically smallest one.

If some number occurs multiple times as a substring, then in the counting of the number of modest substrings it is counted multiple times as well.

Input

The first line contains one integer l (1 ≤ l ≤ 10^{800}).

The second line contains one integer r (l ≤ r ≤ 10^{800}).

The third line contains one integer n (1 ≤ n ≤ 2 000).

Output

In the first line, print the maximum possible number of modest substrings.

In the second line, print a string of length n having exactly that number of modest substrings.

If there are multiple such strings, print the lexicographically smallest of them.

Examples

Input


1
10
3


Output


3
101


Input


1
11
3


Output


5
111


Input


12345
12346
6


Output


1
012345

Note

In the first example, string «101» has modest substrings «1», «10», «1».

In the second example, string «111» has modest substrings «1» (3 times) and «11» (2 times).

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitnum(long long nValue) {
  return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32);
}
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
inline int bitmaxl(long long a) {
  int temp = a >> 32;
  if (temp) return 32 - __builtin_clz(temp) + 32;
  return bitmaxl(int(a));
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
const int maxr = 810;
char l[maxr], r[maxr];
const int maxn = maxr * 2;
const int maxl = 10;
struct trie {
  int nxt[maxl];
  int dp[maxl][maxr];
  void init() { memset(nxt, -1, sizeof(nxt)); }
} arr[maxn];
int larr;
map<char, int> mp;
inline void InitMp() {
  for (char ch = '0'; ch <= '9'; ch++) mp[ch] = ch - '0';
}
inline int AddWord(char str[maxr], int common_l, int common_f, int big) {
  int l = strlen(str), no = 0;
  int adv = 1;
  if (big) adv = -1;
  for (int i = 0; i < l; i++) {
    int nxt = arr[no].nxt[mp[str[i]]];
    if (nxt == -1) {
      arr[larr].init();
      nxt = arr[no].nxt[mp[str[i]]] = larr++;
    }
    if (i >= common_l) {
      for (int j = mp[str[i]] + (i != (l - 1) ? adv : 0); j != common_f;
           j += adv) {
        for (int k = l - i; k < maxr; k++) arr[no].dp[j][k]++;
      }
      if (big) {
        common_f = -1;
      } else {
        common_f = 10;
      }
    }
    no = nxt;
  }
  return no;
}
inline void addval(int no1, int no2) {
  for (int j = 0; j < maxl; j++)
    for (int i = 0; i < maxr; i++) {
      arr[no1].dp[j][i] += arr[no2].dp[j][i];
    }
}
void dfs(int l, int r) {
  for (int i = 1; i < maxl; i++) {
    int sum = 0;
    for (int j = l; j <= r; j++) {
      sum++;
      arr[0].dp[i][j] += sum;
    }
    for (int j = r + 1; j < maxr; j++) {
      arr[0].dp[i][j] += sum;
    }
  }
}
inline void acbfs() {
  pair<int, int> q[maxn];
  int lq = 0, rq = 0;
  for (int i = 0; i < maxl; i++) {
    if (arr[0].nxt[i] == -1)
      arr[0].nxt[i] = 0;
    else
      q[rq++] = make_pair(arr[0].nxt[i], 0);
  }
  for (; lq != rq; lq++) {
    int now = q[lq].first, fail = q[lq].second;
    addval(now, fail);
    for (int i = 0; i < maxl; i++) {
      if (arr[now].nxt[i] == -1)
        arr[now].nxt[i] = arr[fail].nxt[i];
      else {
        q[rq++] = make_pair(arr[now].nxt[i], arr[fail].nxt[i]);
      }
    }
  }
}
int p_pre[2][maxn], p_nxt[2][maxn], p_head[2], p_tail[2];
pair<int, pair<int, int> > bef[2010][maxn];
int n;
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%s%s", l, r);
  scanf("%d", &n);
  InitMp();
  arr[0].init();
  larr = 1;
  if (strlen(l) != strlen(r)) {
    AddWord(r, 0, 0, 1);
    AddWord(l, 0, 10, 0);
    dfs(strlen(l) + 1, strlen(r) - 1);
  } else {
    int common_l = 0, rl = strlen(l);
    while (l[common_l] == r[common_l] && common_l < rl) {
      common_l++;
    }
    if (common_l == strlen(r)) {
      AddWord(r, common_l - 1, l[common_l - 1] - '0' - 1, 1);
    } else {
      AddWord(r, common_l, l[common_l] - '0', 1);
      AddWord(l, common_l, l[common_l] - '0' + 1, 0);
    }
  }
  acbfs();
  int now = 0, nxt = 1;
  p_head[now] = 0;
  p_pre[now][0] = -1;
  p_nxt[now][0] = -1;
  memset(bef, -1, sizeof(bef));
  bef[0][0] = make_pair(0, make_pair(-1, -1));
  for (int i = 0; i < n; i++) {
    memset(p_pre[nxt], -1, sizeof(p_pre[nxt]));
    memset(p_nxt[nxt], -1, sizeof(p_nxt[nxt]));
    p_head[nxt] = -1, p_tail[nxt] = -1;
    for (int no = p_head[now]; no != -1; no = p_nxt[now][no]) {
      for (int k = 0; k < maxl; k++) {
        int nxt_p = arr[no].nxt[k];
        if (bef[i + 1][nxt_p].first <
            bef[i][no].first + arr[no].dp[k][min(maxr - 1, n - i)]) {
          if (p_head[nxt] == -1) {
            p_head[nxt] = nxt_p;
          } else if (p_head[nxt] == nxt_p && p_nxt[nxt][nxt_p] != -1) {
            p_head[nxt] = p_nxt[nxt][nxt_p];
          }
          if (p_tail[nxt] != nxt_p) {
            if (p_pre[nxt][nxt_p] != -1) {
              p_nxt[nxt][p_pre[nxt][nxt_p]] = p_nxt[nxt][nxt_p];
            }
            if (p_nxt[nxt][nxt_p] != -1) {
              p_pre[nxt][p_nxt[nxt][nxt_p]] = p_pre[nxt][nxt_p];
            }
            p_nxt[nxt][p_tail[nxt]] = nxt_p;
            p_pre[nxt][nxt_p] = p_tail[nxt];
            p_nxt[nxt][nxt_p] = -1;
            p_tail[nxt] = nxt_p;
          }
          bef[i + 1][nxt_p] =
              make_pair(bef[i][no].first + arr[no].dp[k][min(maxr - 1, n - i)],
                        make_pair(no, k));
        }
      }
    }
    swap(now, nxt);
  }
  int ans_no = p_head[now];
  for (int no = p_head[now]; no != -1; no = p_nxt[now][no]) {
    if (bef[n][no].first > bef[n][ans_no].first) {
      ans_no = no;
    }
  }
  cout << bef[n][ans_no].first << endl;
  string ans;
  for (int i = n; i > 0; i--) {
    ans += bef[i][ans_no].second.second + '0';
    ans_no = bef[i][ans_no].second.first;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  return 0;
}