#include <bits/stdc++.h>
using namespace std;
long long M = 1e9 + 7;
long long fact[10];
long long sieve[10];
long long power(long long x, long long y) {
  if (y == 0) return 1;
  long long t = power(x, y / 2);
  t = ((t % M) * (t % M)) % M;
  if (y % 2 == 1) t = ((t % M) * (x % M)) % M;
  return t;
}
long long max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long min(long long a, long long b) {
  if (a > b) return b;
  return a;
}
long long binarySearch(vector<long long> arr, long long l, long long r,
                       long long x) {
  if (r >= l) {
    long long mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
  }
  return -1;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long phi(long long n) {
  long long result = n;
  for (long long p = 2; p * p <= n; ++p) {
    if (n % p == 0) {
      while (n % p == 0) n /= p;
      result -= result / p;
    }
  }
  if (n > 1) result -= result / n;
  return result;
}
void dfs(long long source, long long visited[], vector<long long> graph[],
         long long l) {
  visited[source] = l;
  long long i;
  for (i = 0; i < graph[source].size(); i++) {
    if (visited[graph[source][i]] == -1)
      dfs(graph[source][i], visited, graph, l);
  }
}
bool isPerfectSquare(long double x) {
  long double sr = sqrt(x);
  return ((sr - floor(sr)) == 0);
}
long long getMid(long long s, long long e) { return s + (e - s) / 2; }
long long getSumUtil(long long *st, long long ss, long long se, long long qs,
                     long long qe, long long si) {
  if (qs <= ss && qe >= se) return st[si];
  if (se < qs || ss > qe) return 0;
  long long mid = getMid(ss, se);
  return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) +
         getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2);
}
void updateValueUtil(long long *st, long long ss, long long se, long long i,
                     long long diff, long long si) {
  if (i < ss || i > se) return;
  st[si] = st[si] + diff;
  if (se != ss) {
    long long mid = getMid(ss, se);
    updateValueUtil(st, ss, mid, i, diff, 2 * si + 1);
    updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2);
  }
}
void updateValue(long long arr[], long long *st, long long n, long long i,
                 long long new_val) {
  if (i < 0 || i > n - 1) {
    cout << "Invalid Input";
    return;
  }
  long long diff = new_val - arr[i];
  arr[i] = new_val;
  updateValueUtil(st, 0, n - 1, i, diff, 0);
}
long long getSum(long long *st, long long n, long long qs, long long qe) {
  if (qs < 0 || qe > n - 1 || qs > qe) {
    cout << "Invalid Input";
    return -1;
  }
  return getSumUtil(st, 0, n - 1, qs, qe, 0);
}
long long constructSTUtil(long long arr[], long long ss, long long se,
                          long long *st, long long si) {
  if (ss == se) {
    st[si] = arr[ss];
    return arr[ss];
  }
  long long mid = getMid(ss, se);
  st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) +
           constructSTUtil(arr, mid + 1, se, st, si * 2 + 2);
  return st[si];
}
long long *constructST(long long arr[], long long n) {
  long long x = (long long)(ceil(log2(n)));
  long long max_size = 2 * (long long)pow(2, x) - 1;
  long long *st = new long long[max_size];
  constructSTUtil(arr, 0, n - 1, st, 0);
  return st;
}
vector<long long> maxSubArraySum(long long a[], long long size) {
  long long max_so_far = LONG_MIN, max_ending_here = 0, start = 0, end = 0,
            s = 0;
  for (long long i = 0; i < size; i++) {
    max_ending_here += a[i];
    if (max_so_far < max_ending_here) {
      max_so_far = max_ending_here;
      start = s;
      end = i;
    }
    if (max_ending_here < 0) {
      max_ending_here = 0;
      s = i + 1;
    }
  }
  vector<long long> v;
  v.push_back(max_so_far);
  v.push_back(start);
  v.push_back(end);
  return v;
}
vector<long long> smallestSumSubarr(long long arr[], long long n) {
  long long min_ending_here = 0;
  long long min_so_far = LONG_MAX, start = 0, end = 0, s = 0;
  for (long long i = 0; i < n; i++) {
    min_ending_here += arr[i];
    if (min_so_far > min_ending_here) {
      min_so_far = min_ending_here;
      start = s;
      end = i;
    }
    if (min_ending_here > 0) {
      min_ending_here = 0;
      s = i + 1;
    }
  }
  vector<long long> v;
  v.push_back(min_so_far);
  v.push_back(start);
  v.push_back(end);
  return v;
}
void bfs(vector<long long> g[], long long dist[], bool v[], long long u) {
  queue<long long> q;
  q.push(u);
  v[u] = true;
  dist[u] = 0;
  while (!q.empty()) {
    long long f = q.front();
    q.pop();
    for (auto i = g[f].begin(); i != g[f].end(); i++) {
      if (!v[*i]) {
        q.push(*i);
        v[*i] = true;
        dist[*i] = dist[f] + 1;
      }
    }
  }
}
class DisjSet {
  long long *rank, *parent, *gc, n;

 public:
  DisjSet(long long n) {
    rank = new long long[n];
    parent = new long long[n];
    gc = new long long[n];
    this->n = n;
    makeSet();
  }
  void makeSet() {
    for (long long i = 0; i < n; i++) {
      parent[i] = i;
    }
    for (long long i = 0; i < n; i++) {
      rank[i] = i;
      gc[i] = i;
    }
  }
  void initi(long long a[]) {
    for (long long i = 0; i < n; i++) gc[i] = a[i] % M;
  }
  long long find(long long x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }
  bool Union(long long x, long long y) {
    long long xset = find(x);
    long long yset = find(y);
    if (xset == yset) return false;
    if (rank[xset] < rank[yset]) {
      parent[xset] = yset;
      gc[yset] = gcd(gc[yset], gc[xset]) % M;
    } else if (rank[xset] > rank[yset]) {
      parent[yset] = xset;
      gc[xset] = gcd(gc[yset], gc[xset]) % M;
    }
  }
  long long get(long long x) { return gc[x] % M; }
};
bool isPali(string s) {
  long long st = 0, ed = s.size() - 1;
  while (st <= ed && s[st] == s[ed]) {
    st++;
    ed--;
  }
  if (st > ed) return true;
  return false;
}
long long sp[100];
long long mp[15000001];
long long siev() {
  sp[1] = 1;
  for (long long i = 2; i < 100; i++) sp[i] = i;
  long long j;
  long long mx = 0;
  for (long long i = 2; i * i < 100; i++) {
    long long c = 0;
    if (sp[i] == i) {
      c += mp[i];
      for (j = i * 2; j < 100; j += i) c += mp[j];
      if (sp[j] == j) sp[j] = i;
    }
    if (mx < c) mx = c;
  }
  return mx;
}
long long a[2][100009];
vector<long long> getFactorization(long long x) {
  vector<long long> ret;
  while (x != 1) {
    ret.push_back(sp[x]);
    x = x / sp[x];
  }
  return ret;
}
long long findlcm(long long arr[], long long n) {
  long long ans = arr[0];
  for (long long i = 1; i < n; i++)
    ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));
  return ans;
}
void bfs(vector<long long> v[], long long n, long long parent[]) {
  long long i;
  long long flg[200000 + 9] = {0};
  queue<long long> q;
  q.push(n);
  parent[n] = -1;
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    flg[u] = 1;
    for (i = 0; i < v[u].size(); i++) {
      long long ve = v[u][i];
      if (flg[ve] == 0) {
        q.push(ve);
        parent[ve] = u;
      }
    }
  }
}
long long spf[100];
vector<long long> getFactor(long long n) {
  vector<long long> v;
  long long i;
  for (i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      if (n / i != i) v.push_back(n / i);
      v.push_back(i);
    }
  }
  return v;
}
long long s;
long long poww[1000000 + 9];
long long c[1000000 + 9];
vector<long long> tree[200000 + 9];
long long depth[200000 + 9];
long long parent[200000 + 9][18];
void dfsUtil(vector<long long> v[], long long s, long long vis[],
             long long dis[]) {
  vis[s] = 1;
  long long i;
  for (i = 0; i < v[s].size(); i++) {
    if (vis[v[s][i]] == 0) {
      vis[v[s][i]] = 1;
      dis[v[s][i]] = dis[s] + 1;
      dfsUtil(v, v[s][i], vis, dis);
    }
  }
}
long long dis[200009];
long long par[200009];
void dfs(long long cur, long long prev) {
  depth[cur] = depth[prev] + 1;
  parent[cur][0] = prev;
  for (long long i = 0; i < tree[cur].size(); i++) {
    if (tree[cur][i] != prev) {
      dis[tree[cur][i]] = dis[cur] + 1;
      par[tree[cur][i]] = cur;
      dfs(tree[cur][i], cur);
    }
  }
}
void precomputeSparseMatrix(long long n) {
  for (long long i = 1; i < 18; i++) {
    for (long long node = 1; node <= n; node++) {
      if (parent[node][i - 1] != -1)
        parent[node][i] = parent[parent[node][i - 1]][i - 1];
    }
  }
}
long long lca(long long u, long long v) {
  if (depth[v] < depth[u]) swap(u, v);
  long long diff = depth[v] - depth[u];
  for (int i = 0; i < 18; i++)
    if ((diff >> i) & 1) v = parent[v][i];
  if (u == v) return u;
  for (long long i = 18 - 1; i >= 0; i--)
    if (parent[u][i] != parent[v][i]) {
      u = parent[u][i];
      v = parent[v][i];
    }
  return parent[u][0];
}
void dfs(vector<long long> v[], long long s, long long dis[], long long vis[],
         long long a[], long long su[], long long y) {
  if (su[s] == -1) {
    a[s] = 0;
  } else {
    a[s] = su[s] - y;
  }
  y += a[s];
  long long i;
  vis[s] = 1;
  for (i = 0; i < v[s].size(); i++) {
    if (vis[v[s][i]] == 0) {
      dis[v[s][i]] = dis[s] + 1;
      dfs(v, v[s][i], dis, vis, a, su, y);
    }
  }
  y -= a[s];
}
void numberOfNodes(vector<long long> adj[], long long count1[], long long s,
                   long long e) {
  vector<long long>::iterator u;
  count1[s] = 1;
  for (u = adj[s].begin(); u != adj[s].end(); u++) {
    if (*u == e) continue;
    numberOfNodes(adj, count1, *u, s);
    count1[s] += count1[*u];
  }
}
long long p[100000 + 9];
long long f[100000 + 9];
vector<long long> getBinary(long long x) {
  vector<long long> v;
  while (x > 0) {
    v.push_back(x % 2);
    x = x / 2;
  }
  return v;
}
long long max(long long a, long long b, long long c) {
  return max(max(a, b), c);
}
long long maxCrossingSum(long long arr[], long long l, long long m,
                         long long h) {
  long long s1[m - l + 1], s2[h - m];
  memset(s1, 0, sizeof(s1));
  memset(s2, 0, sizeof(s2));
  s1[m - l] = arr[m];
  long long le = m - l - 1;
  long long i;
  long long mx1[m - l + 1], mx2[h - m];
  mx1[m - l] = arr[m];
  for (i = m - 1; i >= l; i--) {
    s1[le] = s1[le + 1] + arr[i];
    mx1[le] = max(mx1[le + 1], arr[i]);
    le--;
  }
  s2[0] = arr[m + 1];
  le = 1;
  mx2[0] = arr[m + 1];
  for (i = m + 2; i <= h; i++) {
    s2[le] = s2[le - 1] + arr[i];
    mx2[le] = max(mx2[le - 1], arr[i]);
    le++;
  }
  long long j;
  i = 0;
  j = h - m - 1;
  long long maxi = 0;
  while (i <= m - l && j >= 0) {
    if (maxi < s1[i] + s2[j] - max(mx1[i], mx2[j]))
      maxi = s1[i] + s2[j] - max(mx1[i], mx2[j]);
    if (mx1[i] == max(mx1[i], mx2[j]))
      i++;
    else
      j--;
    cout << maxi << endl;
  }
  return maxi;
}
long long maxSubArraySum(long long arr[], long long l, long long h) {
  if (l == h) return 0;
  long long m = (l + h) / 2;
  long long l1 = maxSubArraySum(arr, l, m);
  long long l2 = maxSubArraySum(arr, m + 1, h);
  long long l3 = maxCrossingSum(arr, l, m, h);
  cout << l1 << " " << l2 << " " << l3 << " " << l << " " << h << endl;
  return max(l1, l2, l3);
}
long long Ni, Mi;
vector<long long> bfsM(long long s, vector<long long> v[], long long dis[],
                       bool vis[], long long a[], long long b[], double rt) {
  queue<long long> q;
  dis[s] = 1;
  vector<long long> vt;
  q.push(s);
  vis[s] = true;
  vt.push_back(s);
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    long long i;
    for (i = 0; i < v[u].size(); i++) {
      double d = (a[v[u][i]] / (double)b[v[u][i]]);
      if (!vis[v[u][i]] && d == rt) {
        q.push(v[u][i]);
        dis[v[u][i]] = dis[u] + 1;
        vis[v[u][i]] = true;
        vt.push_back(v[u][i]);
      }
    }
  }
  return vt;
}
pair<long long, long long> dfsUti(vector<long long> v[], long long s,
                                  long long a[], long long b[], long long c[],
                                  long long vis[],
                                  pair<long long, long long> p[]) {
  vis[s] = 1;
  long long x = 0, y = 0;
  for (long long i = 0; i < v[s].size(); i++) {
    if (vis[v[s][i]] == 0) {
      if (a[s] < a[v[s][i]]) a[v[s][i]] = a[s];
      pair<long long, long long> p1 = dfsUti(v, v[s][i], a, b, c, vis, p);
      x += p1.first;
      y += p1.second;
    }
  }
  if (b[s] == 1 && c[s] == 0)
    y++;
  else if (b[s] == 0 && c[s] == 1)
    x++;
  if (1) {
    long long d = min(x, y);
    x = x - d;
    y = y - d;
    p[s] = make_pair(d, d);
  }
  return make_pair(x, y);
}
void dfs(vector<long long> v[], long long s, long long a[], long long vis[],
         pair<long long, long long> p[], long long *cost, long long c) {
  vis[s] = 1;
  long long count = 2 * p[s].first;
  (*cost) = (*cost) + (a[s] * count);
  c = a[s];
  for (long long i = 0; i < v[s].size(); i++) {
    if (vis[v[s][i]] == 0) {
      dfs(v, v[s][i], a, vis, p, cost, c);
    }
  }
}
long long ft;
bool compt(long long x, long long y) { return (x % ft) < (y % ft); }
long long findMex(long long b[], long long n) {
  long long l = 0;
  long long a[n];
  for (long long i = 0; i < n; i++) a[i] = b[i];
  sort(a, a + n);
  for (long long i = 0; i < n; i++) {
    if (a[i] != l) {
      return l;
    }
    while (i < n && a[i] == l) {
      i++;
    }
    i--;
    l++;
  }
  return l;
}
long long maxProductSubarrayOfSizeK(long long A[], long long n, long long k) {
  sort(A, A + n);
  long long product = 1;
  if (A[n - 1] == 0 && (k & 1)) return 0;
  if (A[n - 1] <= 0 && (k & 1)) {
    for (long long i = n - 1; i >= n - k; i--) {
      product = (product * A[i]) % M;
      if (product < 0) product += M;
    }
    return product;
  }
  long long i = 0;
  long long j = n - 1;
  if (k & 1) {
    product *= A[j];
    product = product % M;
    j--;
    k--;
  }
  k >>= 1;
  for (long long itr = 0; itr < k; itr++) {
    long long left_product = A[i] * A[i + 1];
    long long right_product = A[j] * A[j - 1];
    if (left_product > right_product) {
      long long f = left_product % M;
      if (f < 0) f += M;
      product = ((product % M) * (f % M)) % M;
      if (product < 0) product += M;
      i += 2;
    } else {
      long long f = right_product % M;
      if (f < 0) f += M;
      product = ((product % M) * (f % M)) % M;
      if (product < 0) product += M;
      j -= 2;
    }
  }
  return product;
}
long long computeXOR(const long long n) {
  switch (n & 3) {
    case 0:
      return n;
    case 1:
      return 1;
    case 2:
      return n + 1;
    case 3:
      return 0;
  }
}
void output() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  string s;
  cin >> s;
  if (s.size() == 1) {
    cout << s << endl;
    return;
  }
  long long i, j;
  long long a[26] = {0};
  for (i = 0; i < s.size(); i++) a[(s[i] - 'a')]++;
  long long c = 0;
  for (i = 0; i < 26; i++) {
    if (a[i] % 2) c++;
  }
  long long f = 0;
  if (c % 2) f = 1;
  c = c / 2;
  string st = "";
  vector<char> v;
  for (i = 0; i < 26; i++) {
    if (a[i] % 2 == 1 && c > 0) {
      st.push_back('a' + i);
      c--;
      v.push_back('a' + i);
    } else if (a[i] % 2 == 1) {
      v.push_back('a' + i);
    }
    for (j = 0; j < a[i] / 2; j++) st.push_back(('a' + i));
  }
  if (v.size() % 2 == 1) {
    st.push_back(v[(v.size() / 2)]);
    i = st.size() - 2;
    while (i >= 0) {
      st.push_back(st[i]);
      i--;
    }
  } else {
    i = st.size() - 1;
    while (i >= 0) {
      st.push_back(st[i]);
      i--;
    }
  }
  cout << st << endl;
}
int main(int argc, const char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  t = 1;
  p[0] = 1;
  while (t--) output();
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

A string is called palindrome if it reads the same from left to right and from right to left. For example "kazak", "oo", "r" and "mikhailrubinchikkihcniburliahkim" are palindroms, but strings "abb" and "ij" are not.

You are given string s consisting of lowercase Latin letters. At once you can choose any position in the string and change letter in that position to any other lowercase letter. So after each changing the length of the string doesn't change. At first you can change some letters in s. Then you can permute the order of letters as you want. Permutation doesn't count as changes. 

You should obtain palindrome with the minimal number of changes. If there are several ways to do that you should get the lexicographically (alphabetically) smallest palindrome. So firstly you should minimize the number of changes and then minimize the palindrome lexicographically.

Input

The only line contains string s (1 ≤ |s| ≤ 2·105) consisting of only lowercase Latin letters.

Output

Print the lexicographically smallest palindrome that can be obtained with the minimal number of changes.

Examples

Input

aabc


Output

abba


Input

aabcd


Output

abcba

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long M = 1e9 + 7;
long long fact[10];
long long sieve[10];
long long power(long long x, long long y) {
  if (y == 0) return 1;
  long long t = power(x, y / 2);
  t = ((t % M) * (t % M)) % M;
  if (y % 2 == 1) t = ((t % M) * (x % M)) % M;
  return t;
}
long long max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long min(long long a, long long b) {
  if (a > b) return b;
  return a;
}
long long binarySearch(vector<long long> arr, long long l, long long r,
                       long long x) {
  if (r >= l) {
    long long mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
  }
  return -1;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long phi(long long n) {
  long long result = n;
  for (long long p = 2; p * p <= n; ++p) {
    if (n % p == 0) {
      while (n % p == 0) n /= p;
      result -= result / p;
    }
  }
  if (n > 1) result -= result / n;
  return result;
}
void dfs(long long source, long long visited[], vector<long long> graph[],
         long long l) {
  visited[source] = l;
  long long i;
  for (i = 0; i < graph[source].size(); i++) {
    if (visited[graph[source][i]] == -1)
      dfs(graph[source][i], visited, graph, l);
  }
}
bool isPerfectSquare(long double x) {
  long double sr = sqrt(x);
  return ((sr - floor(sr)) == 0);
}
long long getMid(long long s, long long e) { return s + (e - s) / 2; }
long long getSumUtil(long long *st, long long ss, long long se, long long qs,
                     long long qe, long long si) {
  if (qs <= ss && qe >= se) return st[si];
  if (se < qs || ss > qe) return 0;
  long long mid = getMid(ss, se);
  return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) +
         getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2);
}
void updateValueUtil(long long *st, long long ss, long long se, long long i,
                     long long diff, long long si) {
  if (i < ss || i > se) return;
  st[si] = st[si] + diff;
  if (se != ss) {
    long long mid = getMid(ss, se);
    updateValueUtil(st, ss, mid, i, diff, 2 * si + 1);
    updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2);
  }
}
void updateValue(long long arr[], long long *st, long long n, long long i,
                 long long new_val) {
  if (i < 0 || i > n - 1) {
    cout << "Invalid Input";
    return;
  }
  long long diff = new_val - arr[i];
  arr[i] = new_val;
  updateValueUtil(st, 0, n - 1, i, diff, 0);
}
long long getSum(long long *st, long long n, long long qs, long long qe) {
  if (qs < 0 || qe > n - 1 || qs > qe) {
    cout << "Invalid Input";
    return -1;
  }
  return getSumUtil(st, 0, n - 1, qs, qe, 0);
}
long long constructSTUtil(long long arr[], long long ss, long long se,
                          long long *st, long long si) {
  if (ss == se) {
    st[si] = arr[ss];
    return arr[ss];
  }
  long long mid = getMid(ss, se);
  st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) +
           constructSTUtil(arr, mid + 1, se, st, si * 2 + 2);
  return st[si];
}
long long *constructST(long long arr[], long long n) {
  long long x = (long long)(ceil(log2(n)));
  long long max_size = 2 * (long long)pow(2, x) - 1;
  long long *st = new long long[max_size];
  constructSTUtil(arr, 0, n - 1, st, 0);
  return st;
}
vector<long long> maxSubArraySum(long long a[], long long size) {
  long long max_so_far = LONG_MIN, max_ending_here = 0, start = 0, end = 0,
            s = 0;
  for (long long i = 0; i < size; i++) {
    max_ending_here += a[i];
    if (max_so_far < max_ending_here) {
      max_so_far = max_ending_here;
      start = s;
      end = i;
    }
    if (max_ending_here < 0) {
      max_ending_here = 0;
      s = i + 1;
    }
  }
  vector<long long> v;
  v.push_back(max_so_far);
  v.push_back(start);
  v.push_back(end);
  return v;
}
vector<long long> smallestSumSubarr(long long arr[], long long n) {
  long long min_ending_here = 0;
  long long min_so_far = LONG_MAX, start = 0, end = 0, s = 0;
  for (long long i = 0; i < n; i++) {
    min_ending_here += arr[i];
    if (min_so_far > min_ending_here) {
      min_so_far = min_ending_here;
      start = s;
      end = i;
    }
    if (min_ending_here > 0) {
      min_ending_here = 0;
      s = i + 1;
    }
  }
  vector<long long> v;
  v.push_back(min_so_far);
  v.push_back(start);
  v.push_back(end);
  return v;
}
void bfs(vector<long long> g[], long long dist[], bool v[], long long u) {
  queue<long long> q;
  q.push(u);
  v[u] = true;
  dist[u] = 0;
  while (!q.empty()) {
    long long f = q.front();
    q.pop();
    for (auto i = g[f].begin(); i != g[f].end(); i++) {
      if (!v[*i]) {
        q.push(*i);
        v[*i] = true;
        dist[*i] = dist[f] + 1;
      }
    }
  }
}
class DisjSet {
  long long *rank, *parent, *gc, n;

 public:
  DisjSet(long long n) {
    rank = new long long[n];
    parent = new long long[n];
    gc = new long long[n];
    this->n = n;
    makeSet();
  }
  void makeSet() {
    for (long long i = 0; i < n; i++) {
      parent[i] = i;
    }
    for (long long i = 0; i < n; i++) {
      rank[i] = i;
      gc[i] = i;
    }
  }
  void initi(long long a[]) {
    for (long long i = 0; i < n; i++) gc[i] = a[i] % M;
  }
  long long find(long long x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }
  bool Union(long long x, long long y) {
    long long xset = find(x);
    long long yset = find(y);
    if (xset == yset) return false;
    if (rank[xset] < rank[yset]) {
      parent[xset] = yset;
      gc[yset] = gcd(gc[yset], gc[xset]) % M;
    } else if (rank[xset] > rank[yset]) {
      parent[yset] = xset;
      gc[xset] = gcd(gc[yset], gc[xset]) % M;
    }
  }
  long long get(long long x) { return gc[x] % M; }
};
bool isPali(string s) {
  long long st = 0, ed = s.size() - 1;
  while (st <= ed && s[st] == s[ed]) {
    st++;
    ed--;
  }
  if (st > ed) return true;
  return false;
}
long long sp[100];
long long mp[15000001];
long long siev() {
  sp[1] = 1;
  for (long long i = 2; i < 100; i++) sp[i] = i;
  long long j;
  long long mx = 0;
  for (long long i = 2; i * i < 100; i++) {
    long long c = 0;
    if (sp[i] == i) {
      c += mp[i];
      for (j = i * 2; j < 100; j += i) c += mp[j];
      if (sp[j] == j) sp[j] = i;
    }
    if (mx < c) mx = c;
  }
  return mx;
}
long long a[2][100009];
vector<long long> getFactorization(long long x) {
  vector<long long> ret;
  while (x != 1) {
    ret.push_back(sp[x]);
    x = x / sp[x];
  }
  return ret;
}
long long findlcm(long long arr[], long long n) {
  long long ans = arr[0];
  for (long long i = 1; i < n; i++)
    ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));
  return ans;
}
void bfs(vector<long long> v[], long long n, long long parent[]) {
  long long i;
  long long flg[200000 + 9] = {0};
  queue<long long> q;
  q.push(n);
  parent[n] = -1;
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    flg[u] = 1;
    for (i = 0; i < v[u].size(); i++) {
      long long ve = v[u][i];
      if (flg[ve] == 0) {
        q.push(ve);
        parent[ve] = u;
      }
    }
  }
}
long long spf[100];
vector<long long> getFactor(long long n) {
  vector<long long> v;
  long long i;
  for (i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      if (n / i != i) v.push_back(n / i);
      v.push_back(i);
    }
  }
  return v;
}
long long s;
long long poww[1000000 + 9];
long long c[1000000 + 9];
vector<long long> tree[200000 + 9];
long long depth[200000 + 9];
long long parent[200000 + 9][18];
void dfsUtil(vector<long long> v[], long long s, long long vis[],
             long long dis[]) {
  vis[s] = 1;
  long long i;
  for (i = 0; i < v[s].size(); i++) {
    if (vis[v[s][i]] == 0) {
      vis[v[s][i]] = 1;
      dis[v[s][i]] = dis[s] + 1;
      dfsUtil(v, v[s][i], vis, dis);
    }
  }
}
long long dis[200009];
long long par[200009];
void dfs(long long cur, long long prev) {
  depth[cur] = depth[prev] + 1;
  parent[cur][0] = prev;
  for (long long i = 0; i < tree[cur].size(); i++) {
    if (tree[cur][i] != prev) {
      dis[tree[cur][i]] = dis[cur] + 1;
      par[tree[cur][i]] = cur;
      dfs(tree[cur][i], cur);
    }
  }
}
void precomputeSparseMatrix(long long n) {
  for (long long i = 1; i < 18; i++) {
    for (long long node = 1; node <= n; node++) {
      if (parent[node][i - 1] != -1)
        parent[node][i] = parent[parent[node][i - 1]][i - 1];
    }
  }
}
long long lca(long long u, long long v) {
  if (depth[v] < depth[u]) swap(u, v);
  long long diff = depth[v] - depth[u];
  for (int i = 0; i < 18; i++)
    if ((diff >> i) & 1) v = parent[v][i];
  if (u == v) return u;
  for (long long i = 18 - 1; i >= 0; i--)
    if (parent[u][i] != parent[v][i]) {
      u = parent[u][i];
      v = parent[v][i];
    }
  return parent[u][0];
}
void dfs(vector<long long> v[], long long s, long long dis[], long long vis[],
         long long a[], long long su[], long long y) {
  if (su[s] == -1) {
    a[s] = 0;
  } else {
    a[s] = su[s] - y;
  }
  y += a[s];
  long long i;
  vis[s] = 1;
  for (i = 0; i < v[s].size(); i++) {
    if (vis[v[s][i]] == 0) {
      dis[v[s][i]] = dis[s] + 1;
      dfs(v, v[s][i], dis, vis, a, su, y);
    }
  }
  y -= a[s];
}
void numberOfNodes(vector<long long> adj[], long long count1[], long long s,
                   long long e) {
  vector<long long>::iterator u;
  count1[s] = 1;
  for (u = adj[s].begin(); u != adj[s].end(); u++) {
    if (*u == e) continue;
    numberOfNodes(adj, count1, *u, s);
    count1[s] += count1[*u];
  }
}
long long p[100000 + 9];
long long f[100000 + 9];
vector<long long> getBinary(long long x) {
  vector<long long> v;
  while (x > 0) {
    v.push_back(x % 2);
    x = x / 2;
  }
  return v;
}
long long max(long long a, long long b, long long c) {
  return max(max(a, b), c);
}
long long maxCrossingSum(long long arr[], long long l, long long m,
                         long long h) {
  long long s1[m - l + 1], s2[h - m];
  memset(s1, 0, sizeof(s1));
  memset(s2, 0, sizeof(s2));
  s1[m - l] = arr[m];
  long long le = m - l - 1;
  long long i;
  long long mx1[m - l + 1], mx2[h - m];
  mx1[m - l] = arr[m];
  for (i = m - 1; i >= l; i--) {
    s1[le] = s1[le + 1] + arr[i];
    mx1[le] = max(mx1[le + 1], arr[i]);
    le--;
  }
  s2[0] = arr[m + 1];
  le = 1;
  mx2[0] = arr[m + 1];
  for (i = m + 2; i <= h; i++) {
    s2[le] = s2[le - 1] + arr[i];
    mx2[le] = max(mx2[le - 1], arr[i]);
    le++;
  }
  long long j;
  i = 0;
  j = h - m - 1;
  long long maxi = 0;
  while (i <= m - l && j >= 0) {
    if (maxi < s1[i] + s2[j] - max(mx1[i], mx2[j]))
      maxi = s1[i] + s2[j] - max(mx1[i], mx2[j]);
    if (mx1[i] == max(mx1[i], mx2[j]))
      i++;
    else
      j--;
    cout << maxi << endl;
  }
  return maxi;
}
long long maxSubArraySum(long long arr[], long long l, long long h) {
  if (l == h) return 0;
  long long m = (l + h) / 2;
  long long l1 = maxSubArraySum(arr, l, m);
  long long l2 = maxSubArraySum(arr, m + 1, h);
  long long l3 = maxCrossingSum(arr, l, m, h);
  cout << l1 << " " << l2 << " " << l3 << " " << l << " " << h << endl;
  return max(l1, l2, l3);
}
long long Ni, Mi;
vector<long long> bfsM(long long s, vector<long long> v[], long long dis[],
                       bool vis[], long long a[], long long b[], double rt) {
  queue<long long> q;
  dis[s] = 1;
  vector<long long> vt;
  q.push(s);
  vis[s] = true;
  vt.push_back(s);
  while (!q.empty()) {
    long long u = q.front();
    q.pop();
    long long i;
    for (i = 0; i < v[u].size(); i++) {
      double d = (a[v[u][i]] / (double)b[v[u][i]]);
      if (!vis[v[u][i]] && d == rt) {
        q.push(v[u][i]);
        dis[v[u][i]] = dis[u] + 1;
        vis[v[u][i]] = true;
        vt.push_back(v[u][i]);
      }
    }
  }
  return vt;
}
pair<long long, long long> dfsUti(vector<long long> v[], long long s,
                                  long long a[], long long b[], long long c[],
                                  long long vis[],
                                  pair<long long, long long> p[]) {
  vis[s] = 1;
  long long x = 0, y = 0;
  for (long long i = 0; i < v[s].size(); i++) {
    if (vis[v[s][i]] == 0) {
      if (a[s] < a[v[s][i]]) a[v[s][i]] = a[s];
      pair<long long, long long> p1 = dfsUti(v, v[s][i], a, b, c, vis, p);
      x += p1.first;
      y += p1.second;
    }
  }
  if (b[s] == 1 && c[s] == 0)
    y++;
  else if (b[s] == 0 && c[s] == 1)
    x++;
  if (1) {
    long long d = min(x, y);
    x = x - d;
    y = y - d;
    p[s] = make_pair(d, d);
  }
  return make_pair(x, y);
}
void dfs(vector<long long> v[], long long s, long long a[], long long vis[],
         pair<long long, long long> p[], long long *cost, long long c) {
  vis[s] = 1;
  long long count = 2 * p[s].first;
  (*cost) = (*cost) + (a[s] * count);
  c = a[s];
  for (long long i = 0; i < v[s].size(); i++) {
    if (vis[v[s][i]] == 0) {
      dfs(v, v[s][i], a, vis, p, cost, c);
    }
  }
}
long long ft;
bool compt(long long x, long long y) { return (x % ft) < (y % ft); }
long long findMex(long long b[], long long n) {
  long long l = 0;
  long long a[n];
  for (long long i = 0; i < n; i++) a[i] = b[i];
  sort(a, a + n);
  for (long long i = 0; i < n; i++) {
    if (a[i] != l) {
      return l;
    }
    while (i < n && a[i] == l) {
      i++;
    }
    i--;
    l++;
  }
  return l;
}
long long maxProductSubarrayOfSizeK(long long A[], long long n, long long k) {
  sort(A, A + n);
  long long product = 1;
  if (A[n - 1] == 0 && (k & 1)) return 0;
  if (A[n - 1] <= 0 && (k & 1)) {
    for (long long i = n - 1; i >= n - k; i--) {
      product = (product * A[i]) % M;
      if (product < 0) product += M;
    }
    return product;
  }
  long long i = 0;
  long long j = n - 1;
  if (k & 1) {
    product *= A[j];
    product = product % M;
    j--;
    k--;
  }
  k >>= 1;
  for (long long itr = 0; itr < k; itr++) {
    long long left_product = A[i] * A[i + 1];
    long long right_product = A[j] * A[j - 1];
    if (left_product > right_product) {
      long long f = left_product % M;
      if (f < 0) f += M;
      product = ((product % M) * (f % M)) % M;
      if (product < 0) product += M;
      i += 2;
    } else {
      long long f = right_product % M;
      if (f < 0) f += M;
      product = ((product % M) * (f % M)) % M;
      if (product < 0) product += M;
      j -= 2;
    }
  }
  return product;
}
long long computeXOR(const long long n) {
  switch (n & 3) {
    case 0:
      return n;
    case 1:
      return 1;
    case 2:
      return n + 1;
    case 3:
      return 0;
  }
}
void output() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  string s;
  cin >> s;
  if (s.size() == 1) {
    cout << s << endl;
    return;
  }
  long long i, j;
  long long a[26] = {0};
  for (i = 0; i < s.size(); i++) a[(s[i] - 'a')]++;
  long long c = 0;
  for (i = 0; i < 26; i++) {
    if (a[i] % 2) c++;
  }
  long long f = 0;
  if (c % 2) f = 1;
  c = c / 2;
  string st = "";
  vector<char> v;
  for (i = 0; i < 26; i++) {
    if (a[i] % 2 == 1 && c > 0) {
      st.push_back('a' + i);
      c--;
      v.push_back('a' + i);
    } else if (a[i] % 2 == 1) {
      v.push_back('a' + i);
    }
    for (j = 0; j < a[i] / 2; j++) st.push_back(('a' + i));
  }
  if (v.size() % 2 == 1) {
    st.push_back(v[(v.size() / 2)]);
    i = st.size() - 2;
    while (i >= 0) {
      st.push_back(st[i]);
      i--;
    }
  } else {
    i = st.size() - 1;
    while (i >= 0) {
      st.push_back(st[i]);
      i--;
    }
  }
  cout << st << endl;
}
int main(int argc, const char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  t = 1;
  p[0] = 1;
  while (t--) output();
  return 0;
}

```