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

int n;
ll max_diff = -1;
vector<int> ans, a, b;

ll diff(vector<int> &a, vector<int> &b) {
    ll p = 1;
    for (int i=0; i<n; ++i) p *= 10;
    ll al = 0;
    for (int t: a) (al *= 10) += t;
    ll bl = 0;
    for (int t: b) (bl *= 10) += t;
    return min(abs(al-bl), p-abs(al-bl));
}

bool used[10];

void dfs() {
    if ((int)b.size() == n) {
        ll d = diff(a, b);
        if (d > max_diff || (d == max_diff && b < ans)) {
            max_diff = d;
            ans = b;
        }
        return;
    }
    for (int i=0; i<10; ++i) {
        if (used[i]) continue;
        b.push_back(i);
        used[i] = true;
        dfs();
        b.pop_back();
        used[i] = false;
    }
}

int main() {
    string S;
    cin >> S;
    n = S.size();
    
    a.resize(n);
    for (int i=0; i<n; ++i) a[i] = S[i]-'0';
    dfs();

    for (int t: ans) cout << t;
    cout << endl;

    return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

Example

Input

201


Output

701

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
ll max_diff = -1;
vector<int> ans, a, b;

ll diff(vector<int> &a, vector<int> &b) {
    ll p = 1;
    for (int i=0; i<n; ++i) p *= 10;
    ll al = 0;
    for (int t: a) (al *= 10) += t;
    ll bl = 0;
    for (int t: b) (bl *= 10) += t;
    return min(abs(al-bl), p-abs(al-bl));
}

bool used[10];

void dfs() {
    if ((int)b.size() == n) {
        ll d = diff(a, b);
        if (d > max_diff || (d == max_diff && b < ans)) {
            max_diff = d;
            ans = b;
        }
        return;
    }
    for (int i=0; i<10; ++i) {
        if (used[i]) continue;
        b.push_back(i);
        used[i] = true;
        dfs();
        b.pop_back();
        used[i] = false;
    }
}

int main() {
    string S;
    cin >> S;
    n = S.size();
    
    a.resize(n);
    for (int i=0; i<n; ++i) a[i] = S[i]-'0';
    dfs();

    for (int t: ans) cout << t;
    cout << endl;

    return 0;
}

```