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 int MOD = (int)1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int)1e9 + 23111992;
const long long LINF = (long long)1e18 + 23111992;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline unsigned long long isqrt(unsigned long long k) {
  unsigned long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() { return abs((int)mt()); }
const int maxn = 1e5 + 5;
const int maxc = 10;
struct node_t {
  node_t* p;
  node_t* c[maxc];
  node_t *bf, *gf;
  int key;
  char val;
  vector<int> info;
  node_t();
  void clear();
} pool[maxn], *ptr = pool;
node_t::node_t() { clear(); }
void node_t::clear() {
  p = 0;
  for (int i = 0; i < maxc; i++) c[i] = 0;
  bf = gf = 0, key = -1, val = 0;
}
void clear() {
  node_t* st = pool;
  while (st != ptr) {
    st->clear();
    st++;
  }
  ptr = pool;
}
node_t* insert(node_t* x, char* s, int key, int len) {
  while (*s) {
    int k = *s - '0';
    if (!x->c[k]) {
      x->c[k] = ptr++;
      x->c[k]->p = x;
      x->c[k]->val = k;
    }
    x = x->c[k];
    s++;
  }
  x->key = key;
  x->info.push_back(len);
  return x;
}
void pushlink(node_t* rt) {
  static node_t* q[maxn];
  int b = 0, e = 0;
  q[e++] = rt;
  while (b < e) {
    node_t* x = q[b++];
    for (int i = 0; i < maxc; i++) {
      if (x->c[i]) q[e++] = x->c[i];
    }
    if (x == rt || x->p == rt) {
      x->bf = rt;
      x->gf = 0;
    } else {
      x->bf = x->p->bf;
      while (x->bf != rt && !x->bf->c[x->val]) x->bf = x->bf->bf;
      if (x->bf->c[x->val]) x->bf = x->bf->c[x->val];
      if (x->bf->key != -1)
        x->gf = x->bf;
      else
        x->gf = x->bf->gf;
      for (int e : x->bf->info) {
        x->info.push_back(e);
      }
      sort(x->info.begin(), x->info.end());
    }
  }
}
string l, r;
int n;
node_t* rt;
vector<vector<int> > f;
vector<vector<int> > dp;
int mem[maxn][10];
int func(int u, int k) {
  int& res = mem[u][k];
  if (~res) return res;
  node_t* cur = pool + u;
  while (cur != rt && !cur->c[k]) {
    cur = cur->bf;
  }
  return res = cur - pool;
}
int calc(int u, int v) {
  if (u == n) return 0;
  int& res = dp[u][v];
  if (~res) return res;
  res = 0;
  for (int i = (0); i < (10); ++i) {
    node_t* cur = pool + func(v, i);
    int cost = f[n - u][i], nv = cur - pool;
    if (cur->c[i]) {
      cur = cur->c[i];
      nv = cur - pool;
      if (cur->key == -1) {
        cur = cur->gf;
      }
      if (cur) {
        cost += upper_bound((cur->info).begin(), (cur->info).end(), n - u) -
                cur->info.begin();
      }
    }
    chkmax(res, calc(u + 1, nv) + cost);
  }
  return res;
}
void chemthan() {
  cin >> l >> r >> n;
  vector<vector<int> > g(10);
  if (int((l).size()) < int((r).size())) {
    for (int i = (1); i < (r[0] - '0'); ++i) {
      g[i].push_back(int((r).size()));
    }
    for (int i = (int((l).size()) + 1); i < (int((r).size())); ++i) {
      for (int j = (1); j < (10); ++j) {
        g[j].push_back(i);
      }
    }
    for (int i = (l[0] - '0' + 1); i < (10); ++i) {
      g[i].push_back(int((l).size()));
    }
  } else {
    for (int i = (l[0] - '0' + 1); i < (r[0] - '0'); ++i) {
      g[i].push_back(int((r).size()));
    }
  }
  for (int i = (1); i < (10); ++i) sort((g[i]).begin(), (g[i]).end());
  f.resize(n + 1, vector<int>(10));
  for (int i = (1); i < (n + 1); ++i)
    for (int j = (1); j < (10); ++j) {
      f[i][j] = upper_bound((g[j]).begin(), (g[j]).end(), i) - g[j].begin();
    }
  rt = ptr++;
  int flag = int((l).size()) < int((r).size()) || l[0] < r[0];
  for (int i = (1); i < (int((r).size())); ++i) {
    for (int j = (0); j < (r[i] - '0'); ++j) {
      if (flag || l[i] - '0' < j) {
        insert(rt, (char*)(r.substr(0, i) + char('0' + j)).data(), 0,
               int((r).size()) - i);
      }
    }
    if (!flag) {
      flag |= l[i] < r[i];
    }
  }
  flag = int((l).size()) < int((r).size()) || l[0] < r[0];
  for (int i = (1); i < (int((l).size())); ++i) {
    for (int j = (l[i] - '0' + 1); j < (10); ++j) {
      if (flag) {
        insert(rt, (char*)(l.substr(0, i) + char('0' + j)).data(), 0,
               int((l).size()) - i);
      }
    }
    if (!flag) {
      flag |= l[i] < r[i];
    }
  }
  insert(rt, (char*)l.data(), 0, 1);
  if (l < r) {
    insert(rt, (char*)r.data(), 0, 1);
  }
  pushlink(rt);
  dp.resize(n + 1);
  for (auto& e : dp) e.resize(ptr - pool, -1);
  memset(mem, -1, sizeof(mem));
  int mx = calc(0, 0);
  cout << mx << "\n";
  string res;
  int u = 0, v = 0;
  for (int it = (0); it < (n); ++it) {
    for (int i = (0); i < (10); ++i) {
      node_t* cur = pool + func(v, i);
      int cost = f[n - u][i], nv = cur - pool;
      if (cur->c[i]) {
        cur = cur->c[i];
        nv = cur - pool;
        if (cur->key == -1) {
          cur = cur->gf;
        }
        if (cur) {
          cost += upper_bound((cur->info).begin(), (cur->info).end(), n - u) -
                  cur->info.begin();
        }
      }
      if (calc(u + 1, nv) + cost == mx) {
        res += char('0' + i);
        mx -= cost;
        u++, v = nv;
        break;
      }
    }
  }
  cout << res << "\n";
}
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0), cin.tie(0);
  if (argc > 1) {
    assert(freopen(argv[1], "r", stdin));
  }
  if (argc > 2) {
    assert(freopen(argv[2], "wb", stdout));
  }
  chemthan();
  cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}