<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

546. Ternary Password
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



In the ternary world all passwords are ternary, that is, they consist only of digits "0", "1" and "2". Terentius is trying to register on a famous internet service site Toogle, but the problem is, according to the security policy of this service the password must contain exactly a characters "0" and exactly b characters "1". All other characters of the password must be "2".

Terentius was fond of his password, he spent much time trying to remember it and now he can type it even with his eyes closed. That's the reason Terentius wants to replace the minimum number of characters in his password so that it meets the strict requirements of the Toogle policy. Terentius wants only to replace (substitute) some characters in password, he doesn't intend to perform other operations with the password.

Help Terentius find the minimum number of replacements and print the corresponding possible variant of the password to Toogle.

Input
The first line of the input contains three integers n, a and b (1 ≤ n ≤ 200; 0 ≤ a,b ≤ 200) — the length of Terentius's password, the expected number of characters "0" and the expected number of characters "1" in the password to Toogle. The second line contains Terentius's password. All characters in this line are digits "0", "1" or "2".

Output
In the first output line print t — the minimum number of replacements. In the second line print the possible variant of the Toogle password — the password that satisfies the Toogle safety policy, that differs from Terentius's password in exactly t positions. If there are several passwords, print any of them. Obviously, the length of the printed password must equal n.

It is possible that Terentius's password already meets the Toogle policy. In this case the first line must contain "0", and the second line must contain Terentius's password.

If the solution doesn't exist, that is, if it is impossible to get a password to Toogle if Terentius uses replacements only, then print "-1" in the first line of the output. In this case print empty second line or don't print the second line at all.

Example(s)
sample input
sample output
6 1 3
012022
2
111022

sample input
sample output
5 5 0
02211
4
00000

<|response|>
1. Abridged problem statement  
Given a ternary string s of length n (characters ‘0’, ‘1’, ‘2’) and targets a (number of ‘0’) and b (number of ‘1’). You may only substitute characters; you cannot insert or delete. Find the minimum number of substitutions to make the string contain exactly a zeros, exactly b ones, and hence n – a – b twos. Output that minimum and one resulting string, or –1 if a + b > n.

2. Key observations  
- Let c0, c1, c2 be the counts of ‘0’, ‘1’, ‘2’ in the original string.  
- Define deficits/surpluses  
  • d0 = a – c0 (positive means need more zeros, negative means too many zeros)  
  • d1 = b – c1 (analogous for ones)  
- You can “swap” a surplus of one digit directly into a deficit of another:   
  • Convert some ‘1’→‘0’ if d0>0 and d1<0, or ‘0’→‘1’ if d1>0 and d0<0.  
  Each such direct swap fixes two imbalances at the cost of one replacement.  
- After maximal direct swaps, at least one of d0 or d1 becomes zero or both have the same sign.  
- Remaining imbalances must be resolved by converting to/from ‘2’:  
  • If d0>0, convert d0 copies of ‘2’→‘0’. If d0<0, convert –d0 copies of ‘0’→‘2’.  
  • Similarly for d1 and ‘1’.  
  Each such conversion costs |d0|+|d1| replacements.

3. Full solution approach  
Step A: Feasibility check  
  If a + b > n, print “-1” and exit.  
Step B: Count existing digits and compute deficits  
  Scan s once to compute c0, c1, c2, then set d0 = a – c0, d1 = b – c1.  
Step C: Direct swaps between ‘0’ and ‘1’  
  1. If d0>0 and d1<0, let q = min(d0, –d1). Replace q occurrences of ‘1’→‘0’, update d0–=q, d1+=q, cost += q.  
  2. If d1>0 and d0<0, let q = min(d1, –d0). Replace q occurrences of ‘0’→‘1’, update d1–=q, d0+=q, cost += q.  
Step D: Fix remaining imbalances via ‘2’  
  - Total extra cost = |d0| + |d1|.  
  - Traverse s again, for each character:  
    • If d0<0 and char==‘0’: change to ‘2’, d0++.  
    • Else if d0>0 and char==‘2’: change to ‘0’, d0–.  
    • Else if d1<0 and char==‘1’: change to ‘2’, d1++.  
    • Else if d1>0 and char==‘2’: change to ‘1’, d1–.  
  Continue until d0==0 and d1==0.  
Step E: Output total cost and the modified string.

4. C++ implementation with detailed comments  
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, a, b;
    string s;
    cin >> n >> a >> b;
    cin >> s;

    // If we need more 0's and 1's than length, impossible
    if (a + b > n) {
        cout << -1 << "\n";
        return 0;
    }

    // Count existing zeros and ones
    int c0 = 0, c1 = 0;
    for (char ch : s) {
        if (ch == '0') ++c0;
        else if (ch == '1') ++c1;
    }

    // Compute deficits: positive means we need more; negative means we have surplus
    int d0 = a - c0;
    int d1 = b - c1;
    int ops = 0;

    // Step C1: swap surplus '1' -> needed '0'
    if (d0 > 0 && d1 < 0) {
        int q = min(d0, -d1);
        ops += q;
        d0 -= q;
        d1 += q;
        // Perform actual replacements in the string
        for (char &ch : s) {
            if (q > 0 && ch == '1') {
                ch = '0';
                --q;
            }
        }
    }

    // Step C2: swap surplus '0' -> needed '1'
    if (d1 > 0 && d0 < 0) {
        int q = min(d1, -d0);
        ops += q;
        d1 -= q;
        d0 += q;
        for (char &ch : s) {
            if (q > 0 && ch == '0') {
                ch = '1';
                --q;
            }
        }
    }

    // Step D: fix remaining imbalances via '2'
    // Each remaining unit of |d0| or |d1| costs 1 replacement
    ops += abs(d0) + abs(d1);

    for (char &ch : s) {
        if (d0 < 0 && ch == '0') {
            // surplus zero -> make it '2'
            ch = '2';
            ++d0;
        }
        else if (d0 > 0 && ch == '2') {
            // need zero -> make '2' into '0'
            ch = '0';
            --d0;
        }
        else if (d1 < 0 && ch == '1') {
            // surplus one -> make it '2'
            ch = '2';
            ++d1;
        }
        else if (d1 > 0 && ch == '2') {
            // need one -> make '2' into '1'
            ch = '1';
            --d1;
        }
        // stop early if both deficits are zero
        if (d0 == 0 && d1 == 0) {
            // further characters already correct counts
            // but we can continue or break—both OK
        }
    }

    // Output result
    cout << ops << "\n";
    cout << s << "\n";
    return 0;
}

5. Python implementation with detailed comments  
def main():
    import sys
    data = sys.stdin.read().split()
    n, a, b = map(int, data[:3])
    s = list(data[3])

    # Impossible if total required zeros+ones exceeds length
    if a + b > n:
        print(-1)
        return

    # Count existing zeros and ones
    c0 = s.count('0')
    c1 = s.count('1')
    # Deficits (positive = need more, negative = surplus)
    d0 = a - c0
    d1 = b - c1
    ops = 0

    # Step C1: use surplus '1' -> needed '0'
    if d0 > 0 and d1 < 0:
        q = min(d0, -d1)
        ops += q
        d0 -= q
        d1 += q
        for i, ch in enumerate(s):
            if q <= 0:
                break
            if ch == '1':
                s[i] = '0'
                q -= 1

    # Step C2: use surplus '0' -> needed '1'
    if d1 > 0 and d0 < 0:
        q = min(d1, -d0)
        ops += q
        d1 -= q
        d0 += q
        for i, ch in enumerate(s):
            if q <= 0:
                break
            if ch == '0':
                s[i] = '1'
                q -= 1

    # Step D: fix remaining via '2'
    ops += abs(d0) + abs(d1)
    for i, ch in enumerate(s):
        if d0 < 0 and s[i] == '0':
            s[i] = '2'
            d0 += 1
        elif d0 > 0 and s[i] == '2':
            s[i] = '0'
            d0 -= 1
        elif d1 < 0 and s[i] == '1':
            s[i] = '2'
            d1 += 1
        elif d1 > 0 and s[i] == '2':
            s[i] = '1'
            d1 -= 1
        # once both are zero, no further changes are needed
        if d0 == 0 and d1 == 0:
            break

    # Print the result
    print(ops)
    print(''.join(s))

if __name__ == "__main__":
    main()