Problem: You are given a non-empty line s and an integer k. The following operation is performed with this line exactly once:

  * A line is split into at most k non-empty substrings, i.e. string s is represented as a concatenation of a set of strings s = t1 + t2 + ... + tm, 1 ≤ m ≤ k. 
  * Some of strings ti are replaced by strings tir, that is, their record from right to left. 
  * The lines are concatenated back in the same order, we get string s' = t'1t'2... t'm, where t'i equals ti or tir. 



Your task is to determine the lexicographically smallest string that could be the result of applying the given operation to the string s.

Input

The first line of the input contains string s (1 ≤ |s| ≤ 5 000 000), consisting of lowercase English letters. The second line contains integer k (1 ≤ k ≤ |s|) — the maximum number of parts in the partition.

Output

In the single line print the lexicographically minimum string s' which can be obtained as a result of performing the described operation. 

Examples

Input

aba
2


Output

aab


Input

aaaabacaba
2


Output

aaaaabacab


Input

bababa
1


Output

ababab


Input

abacabadabacaba
4


Output

aababacabacabad

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename S>
inline bool upmin(T& a, const S& b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
inline bool upmax(T& a, const S& b) {
  return a < b ? a = b, 1 : 0;
}
template <typename N, typename PN>
inline N flo(N a, PN b) {
  return a >= 0 ? a / b : -((-a - 1) / b) - 1;
}
template <typename N, typename PN>
inline N cei(N a, PN b) {
  return a > 0 ? (a - 1) / b + 1 : -(-a / b);
}
template <typename N>
N gcd(N a, N b) {
  return b ? gcd(b, a % b) : a;
}
inline void gn(long long& x) {
  int sg = 1;
  char c;
  while (((c = getchar()) < '0' || c > '9') && c != '-')
    ;
  c == '-' ? (sg = -1, x = 0) : (x = c - '0');
  while ((c = getchar()) >= '0' && c <= '9') x = x * 10 + c - '0';
  x *= sg;
}
inline void gn(int& x) {
  long long t;
  gn(t);
  x = t;
}
inline void gn(unsigned long long& x) {
  long long t;
  gn(t);
  x = t;
}
inline void gn(double& x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
inline void gn(long double& x) {
  double t;
  scanf("%lf", &t);
  x = t;
}
inline long long sqr(long long a) { return a * a; }
inline double sqrf(double a) { return a * a; }
int inf = 0x3f3f3f3f;
double eps = 1e-6;
int mo = 1000000007;
int qp(int a, long long b) {
  int n = 1;
  do {
    if (b & 1) n = 1ll * n * a % mo;
    a = 1ll * a * a % mo;
  } while (b >>= 1);
  return n;
}
char s[10111111];
int k, n;
int mi[5111111];
int mami[5111111];
int z[10111111];
int dbg = 0;
void buildz(int n) {
  z[1] = n;
  if (n <= 1) return;
  z[n + 1] = 'a' - 1;
  while (s[2 + z[2]] == s[1 + z[2]]) z[2]++;
  int a = 2;
  for (int i = 3; i <= n; i++) {
    if (i <= a + z[a] - 1) {
      z[i] = min(a + z[a] - 1 - i + 1, z[i - a + 1]);
    }
    while (s[i + z[i]] == s[1 + z[i]]) z[i]++;
    if (i + z[i] > a + z[a]) a = i;
  }
}
int zcmp(int i, int le) {
  if (z[i] >= le) return 0;
  char a = s[1 + z[i]], b = s[i + z[i]];
  if (a < b) return 1;
  return -1;
}
void init() {
  int i = 1, j = 2, k = 0;
  s[n + 1] = 'a' - 2;
  int bo = 0;
  int las = 0, las2 = 0;
  while (i <= n) {
    k = 0;
    while (s[i + k] == s[j + k]) {
      k++;
    }
    if (s[i + k] > s[j + k]) {
      bo++;
      int d = j - i, e = i + k;
      do {
        i += d;
        mi[i - 1] = las + 1;
        mami[i - 1] = las2 + 1;
        las = i - 1;
        if (dbg) printf("%d ", i - 1);
      } while (i - 1 < e);
      las2 = las;
      j = i + 1;
    } else {
      j = j + k + 1;
    }
  }
}
char ans[5111111];
char s2[5111111];
void doit() {
  for (int t = (n + 1), _ed = (n + n + 1); t < _ed; t++) s[t] = s[t - n];
  s[n + n + 1] = 0;
  int i = 1, j = 2, k = 0;
  while (j <= n) {
    k = 0;
    while (k < n && s[i + k] == s[j + k]) k++;
    if (s[i + k] > s[j + k]) {
      i = max(i + k + 1, j);
      j = i + 1;
    } else {
      j = j + k + 1;
    }
  }
  int tmp = 0;
  for (int t = (i), _ed = (i + n); t < _ed; t++) ans[++tmp] = s[t];
  for (int i = (1), _ed = (n + 1); i < _ed; i++) s2[i] = s[n - i + 1];
  int bo = 0;
  for (int i = (1), _ed = (n + 1); i < _ed; i++)
    if (ans[i] != s2[i]) {
      if (ans[i] > s2[i]) bo = 1;
      break;
    }
  if (bo)
    for (int i = (1), _ed = (n + 1); i < _ed; i++) ans[i] = s2[i];
  bo = 0;
  for (int i = (1), _ed = (n + 1); i < _ed; i++)
    if (ans[i] != s[i]) {
      if (ans[i] > s[i]) bo = 1;
      break;
    }
  if (bo)
    for (int i = (1), _ed = (n + 1); i < _ed; i++) ans[i] = s[i];
  for (int i = (1), _ed = (n + 1); i < _ed; i++) s[n + i] = s2[i];
  buildz(2 * n);
  int opt = 1;
  for (int i = (2), _ed = (n); i < _ed; i++) {
    int ve = zcmp(2 * n + 1 - i, i - opt);
    if (ve == 1) {
      opt = i;
    } else if (ve == 0) {
      ve = zcmp(i - opt + 1, opt);
      if (ve == -1) opt = i;
    }
  }
  tmp = 0;
  for (int i = (n + 1) - 1, _ed = (opt + 1); i >= _ed; i--) s2[++tmp] = s[i];
  for (int i = (1), _ed = (opt + 1); i < _ed; i++) s2[++tmp] = s[i];
  bo = 0;
  for (int i = (1), _ed = (n + 1); i < _ed; i++)
    if (ans[i] != s2[i]) {
      if (ans[i] > s2[i]) bo = 1;
      break;
    }
  if (bo)
    for (int i = (1), _ed = (n + 1); i < _ed; i++) ans[i] = s2[i];
  init();
  tmp = 0;
  for (int i = (mi[n]), _ed = (n + 1); i < _ed; i++) s2[++tmp] = s[i];
  for (int i = (mi[n]) - 1, _ed = (1); i >= _ed; i--) s2[++tmp] = s[i];
  bo = 0;
  for (int i = (1), _ed = (n + 1); i < _ed; i++)
    if (ans[i] != s2[i]) {
      if (ans[i] > s2[i]) bo = 1;
      break;
    }
  if (bo)
    for (int i = (1), _ed = (n + 1); i < _ed; i++) ans[i] = s2[i];
  s[++n] = 'z' + 1;
  init();
  n--;
  tmp = 0;
  for (int i = (mami[n + 1]), _ed = (n + 1); i < _ed; i++) s2[++tmp] = s[i];
  for (int i = (mami[n + 1]) - 1, _ed = (1); i >= _ed; i--) s2[++tmp] = s[i];
  bo = 0;
  for (int i = (1), _ed = (n + 1); i < _ed; i++)
    if (ans[i] != s2[i]) {
      if (ans[i] > s2[i]) bo = 1;
      break;
    }
  if (bo)
    for (int i = (1), _ed = (n + 1); i < _ed; i++) ans[i] = s2[i];
  for (int i = (1), _ed = (n + 1); i < _ed; i++) putchar(ans[i]);
  putchar('\n');
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  gn(k);
  if (k == 1) {
    for (int i = (1), _ed = (n + 1); i < _ed; i++) s2[i] = s[n - i + 1];
    int bo = 0;
    for (int i = (1), _ed = (n + 1); i < _ed; i++)
      if (s[i] != s2[i]) {
        if (s[i] < s2[i])
          ;
        else
          bo = 1;
        break;
      }
    if (bo == 0)
      printf("%s\n", s + 1);
    else
      printf("%s\n", s2 + 1);
    return 0;
  }
  if (strncmp(s + 1, "aaabehbieifhddd", 15) == 0) dbg = 1;
  dbg = 0;
  if (dbg) printf("n=%d\n", n);
  for (int i = 1; i < n - i + 1; i++) swap(s[i], s[n - i + 1]);
  init();
  int las = n;
  for (int t = k; t > 2 && las; t--) {
    int sst = mi[las], st = sst, le = las - sst + 1;
    if (st == las) {
      while (las >= 1 && mi[las] == las) putchar(s[las]), las--;
    } else {
      while (st - le >= 1) {
        int bo = 1;
        st -= le;
        for (int i = (0), _ed = (le); i < _ed; i++) {
          if (s[st + i] != s[sst + i]) {
            bo = 0;
            break;
          }
        }
        if (bo == 0) {
          st += le;
          break;
        }
      }
      for (int i = (st), _ed = (las + 1); i < _ed; i++) putchar(s[i]);
      las = st - 1;
    }
  }
  if (las) {
    n = las;
    doit();
  }
  putchar('\n');
  return 0;
}