You are given a string $s$ consisting of exactly $n$ characters, and each character is either '0', '1' or '2'. Such strings are called ternary strings.

Your task is to replace minimum number of characters in this string with other characters to obtain a balanced ternary string (balanced ternary string is a ternary string such that the number of characters '0' in this string is equal to the number of characters '1', and the number of characters '1' (and '0' obviously) is equal to the number of characters '2').

Among all possible balanced ternary strings you have to obtain the lexicographically (alphabetically) smallest.

Note that you can neither remove characters from the string nor add characters to the string. Also note that you can replace the given characters only with characters '0', '1' and '2'.

It is guaranteed that the answer exists.


-----Input-----

The first line of the input contains one integer $n$ ($3 \le n \le 3 \cdot 10^5$, $n$ is divisible by $3$) — the number of characters in $s$.

The second line contains the string $s$ consisting of exactly $n$ characters '0', '1' and '2'.


-----Output-----

Print one string — the lexicographically (alphabetically) smallest balanced ternary string which can be obtained from the given one with minimum number of replacements.

Because $n$ is divisible by $3$ it is obvious that the answer exists. And it is obvious that there is only one possible answer.


-----Examples-----
Input
3
121

Output
021

Input
6
000000

Output
001122

Input
6
211200

Output
211200

Input
6
120110

Output
120120

Difficulty: introductory

Starter code:

Solutions:
from sys import stdin, stdout
from math import sin, tan, cos, pi, atan2, sqrt, acos, atan, factorial
from random import randint

n = int(stdin.readline())
s = list(stdin.readline().strip())
a, b, c = s.count('0'), s.count('1'), s.count('2')
d = n // 3

for i in range(len(s)):
    if s[i] == '2' and c > d:
        if a < d:
            s[i] = '0'
            a += 1
            c -= 1
        else:
            s[i] = '1'
            b += 1
            c -= 1
    elif s[i] == '1' and b > d:
        if a < d:
            s[i] = '0'
            a += 1
            b -= 1

for i in range(len(s) - 1, -1, -1):
    if s[i] == '1' and b > d:
        if c < d:
            s[i] = '2'
            b -= 1
            c += 1
    elif s[i] == '0' and a > d:
        if c < d:
            s[i] = '2'
            a -= 1
            c += 1
        elif b < d:
            s[i] = '1'
            a -= 1
            b += 1


stdout.write(''.join(s))

n = int(input())

s = list(input())

c = {c: s.count(c) for c in '012'}

i = 0

while c['0'] < n // 3 and i < n:  # maybe redundant i < n
	if s[i] != '0' and c[s[i]] > n // 3:
		c[s[i]] -= 1
		c['0'] += 1
		s[i] = '0'
	
	i += 1

i = 0  # maybe redundant

while c['1'] < n // 3 and i < n:
	if s[i] == '2' and c[s[i]] > n // 3:
		c[s[i]] -= 1
		c['1'] += 1
		s[i] = '1'
	
	i += 1

i = n - 1

while c['2'] < n // 3 and i > 0:  # maybe redundant i > 0
	if s[i] != '2' and c[s[i]] > n // 3:
		c[s[i]] -= 1
		c['2'] += 1
		s[i] = '2'
	
	i -= 1

i = n - 1  # maybe redundant

while c['1'] < n // 3 and i > 0:  # maybe redundant i > 0
	if s[i] != '1' and c[s[i]] > n // 3:
		c[s[i]] -= 1
		c['1'] += 1
		s[i] = '1'
	
	i -= 1

print(''.join(s))


n=int(input())
x=input()
a=x.count('0')
b=x.count('1')
c=x.count('2')
s=list(c for c in x)
if a>n//3:
    if c<n//3:
        for i in range(len(s)-1,-1,-1):
            if s[i]=='0':
                s[i]='2'
                a-=1
                c+=1
            if c==n//3:
                break
            if a==n//3:
                break
    if a>n//3:
        if b<n//3:
            for i in range(len(s)-1,-1,-1):
                if s[i]=='0':
                    s[i]='1'
                    a-=1
                    b+=1
                if b==n//3:
                    break
                if a==n//3:
                    break
if b>n//3:
    if a<n//3:
        for i in range(0,len(s),):
            if s[i]=='1':
                s[i]='0'
                a+=1
                b-=1
            if b==n//3:
                break
            if a==n//3:
                break
    if b>n//3:
        if c<n//3:
            for i in range(len(s)-1,-1,-1):
                if s[i]=='1':
                    s[i]='2'
                    b-=1
                    c+=1
                if b==n//3:
                    break
                if c==n//3:
                    break
if c>n//3:
    if a<n//3:
        for i in range(0,len(s)):
            if s[i]=='2':
                s[i]='0'
                a+=1
                c-=1
            if c==n//3:
                break
            if a==n//3:
                break
    if c>n//3:
        if b<n//3:
            for i in range(0,len(s)):
                if s[i]=='2':
                    s[i]='1'
                    b+=1
                    c-=1
                if b==n//3:
                    break
                if c==n//3:
                    break
print(''.join(s))




n = int(input())
a = list(map(int, list(input())))
cs = [0, 0, 0]
for i in a:
    cs[i] += 1

ops = 0
for i in cs:
    ops += max(0, i - n // 3)

if cs[0] < n // 3:
    for i in range(n):
        if a[i] != 0 and cs[a[i]] > n // 3:
            cs[a[i]] -= 1
            a[i] = 0
            cs[0] += 1
        if cs[0] == n // 3:
            break

if cs[2] < n // 3:
    for i in range(n - 1, -1, -1):
        if a[i] != 2 and cs[a[i]] > n // 3:
            cs[a[i]] -= 1
            a[i] = 2
            cs[2] += 1
        if cs[2] == n // 3:
            break

if cs[1] < n // 3:
    for i in range(n - 1, -1, -1):
        if a[i] == 0 and cs[0] > n // 3:
            cs[0] -= 1
            a[i] = 1
            cs[1] += 1
        if cs[1] == n // 3:
            break

    for i in range(n):
        if cs[1] == n // 3:
            break
        if a[i] == 2 and cs[2] > n // 3:
            cs[2] -= 1
            a[i] = 1
            cs[0] += 1

print(''.join(list(map(str, a))))


n=int(input())
s=list(input())
a=[0]*3
for l in s:
    a[int(l)]+=1
ans=[None]*n
i=0
for l in s:
    if int(l)==1 and a[0]<n//3<a[1]:
       ans[i]='0'
       a[0]+=1
       a[1]-=1
    elif  int(l)==2 and a[0]<n//3<a[2]:
        ans[i] = '0'
        a[0] += 1
        a[2] -= 1
    elif  int(l)==2 and a[1]<n//3<a[2]:
        ans[i] = '1'
        a[1] += 1
        a[2] -= 1
    else:
        ans[i]=l
    i+=1
i=n-1
for l in ans[::-1]:
    if int(l)==0 and a[2]<n//3<a[0]:
        ans[i] = '2'
        a[2] += 1
        a[0] -= 1
    elif int(l)==1 and a[2]<n//3<a[1]:
        ans[i] = '2'
        a[2] += 1
        a[1] -= 1
    elif int(l)==0 and a[1]<n//3<a[0]:
        ans[i] = '1'
        a[1] += 1
        a[0] -= 1
    i-=1
print(''.join(ans))

import sys

n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
A = [0] * n
k = n // 3
c0 = 0
c1 = 0
c2 = 0
for i in range (0, n):
    if s[i] == '0':
        c0 = c0 + 1
    elif s[i] == '1':
        c1 = c1 + 1
    else:
        c2 = c2 + 1
    A[i] = s[i] 

i = 0
while c0 < k:
    if (A[i] == '1' and c1 > k):
        A[i] = '0'
        c0 = c0 + 1
        c1 = c1 - 1
    elif (A[i] == '2' and c2 > k):
        A[i] = '0'
        c0 = c0 + 1
        c2 = c2 - 1
    i = i + 1
i = n-1
while c0 > k and c2 < k:
    if A[i] == '0':
        A[i] = '2'
        c0 = c0 - 1
        c2 = c2 + 1
    i = i - 1
while c0 > k and c1 < k:
    if A[i] == '0':
        A[i] = '1'
        c0 = c0 - 1
        c1 = c1 + 1
    i = i - 1
i = n-1
while c1 > k and c2 < k:
    if A[i] == '1':
        A[i] = '2'
        c1 = c1 - 1
        c2 = c2 + 1
    i = i - 1
i = 0
while c1 < k and c2 > k:
    if A[i] == '2':
        A[i] = '1'
        c2 = c2 - 1
        c1 = c1 + 1
    i = i + 1

print("".join(A))

def new_print(arr):
    print("".join(arr))

n = int(input())
str = input()
l0 = str.count('0')
l1 = str.count('1')
l2 = str.count('2')
str = list(str)
real = n // 3

cur = 0
while (l0 < real):
    if (str[cur] == '1' and l1 > real):
        l1 -= 1
        l0 += 1
        str[cur] = '0'
    if (str[cur] == '2' and l2 > real):
        l2 -= 1
        l0 += 1
        str[cur] = '0'
    cur+=1

cur = 0
while (l1 < real and cur < len(str) and l2 > real):
    if (str[cur] == '2'):
        l2 -= 1
        l1 += 1
        str[cur] = '1'
    cur+=1

cur = len(str) - 1
while (l2 < real and cur >= 0):
    if (str[cur] == '1' and l1 > real):
        l2 += 1
        l1 -= 1
        str[cur] = '2'
    if (str[cur] == '0' and l0 > real):
        l2 += 1
        l0 -= 1
        str[cur] = '2'
    cur-=1


cur = len(str) - 1
while (l1 < real and cur >= 0):
    if (str[cur] == '0' and l0 > real):
        l1 += 1
        l0 -= 1
        str[cur] = '1'
    cur-=1

new_print(str)

n = int(input())
s = list(input())
d = {i:0 for i in '012'}
for i in s:
    d[i] += 1
eq = n // 3
i = 0
while d['0'] < eq:
    if s[i] != '0':
        if d[s[i]] > eq:
            d[s[i]] -= 1
            d['0'] += 1
            s[i] = '0'
    i += 1
i = n - 1
while d['2'] < eq:
    if s[i] != '2':
        if d[s[i]] > eq:
            d[s[i]] -= 1
            d['2'] += 1
            s[i] = '2'
    i -= 1
i = n - 1
while d['1'] < eq and i >= 0:
    if s[i] == '0':
        if d[s[i]] > eq:
            d[s[i]] -= 1
            d['1'] += 1
            s[i] = '1'
    i -= 1
i = 0
while d['1'] < eq and i < n:
    if s[i] == '2':
        if d[s[i]] > eq:
            d[s[i]] -= 1
            d['1'] += 1
            s[i] = '1'
    i += 1
print(*s, sep = '')



n=int(input())
s1=str(input())
count1=s1.count('0')
count2=s1.count('1')
count3=s1.count('2')
s=[]
for i in s1:
    s.append(i)
finish=n//3
tcount1=0
tcount2=0
tcount3=0
for i in range(n):
    if(s[i]=='0'):
        if(tcount1==n//3):
            if(count2<finish and tcount2<finish):
                s[i]='1'
                count2+=1
                tcount2+=1
                count1-=1
            elif(count3<finish and tcount3<finish):
                s[i]='2'
                count3+=1
                tcount3+=1
                count1-=1
            else:
                tcount1+=1
        else:
            tcount1+=1
    elif(s[i]=='1'):
        if(count2>n//3):
            if(count1<n//3 and tcount1<n//3):
                s[i]='0'
                count1+=1
                tcount1+=1
                count2-=1
            elif(tcount2==n//3):
                s[i]='2'
                count3+=1
                tcount3+=1
                count2-=1
            else:
                tcount2+=1
        else:
            tcount2+=1
    else:
        if(count3>n//3):
            if(count1<n//3 and tcount1<n//3):
                s[i]='0'
                count1+=1
                tcount1+=1
                count3-=1
            elif(count2<n//3 and tcount2<n//3):
                s[i]='1'
                count2+=1
                tcount2+=1
                count3-=1
            else:
                tcount3+=1
        else:
            tcount3+=1
    #print(tcount1,tcount2,tcount3)
ans=''
for i in s:
    ans+=i
print(ans)




def mi():
    return list(map(int, input().split()))
'''
3
121
6
120110
6
211200
'''
n = int(input())
a = list(input())

zc, oc, tc = 0,0,0
for i in a:
    if i=='1':
        oc+=1
    elif i=='0':
        zc+=1
    else:
        tc+=1
if oc==tc and oc==zc:
    print(''.join(a))
    return
target = n//3

ztba = max(0,target-zc)
ztbr = max(0,zc-target)

otba = max(0,target-oc)
otbr = max(0,oc-target)

ttba = max(0,target-tc)
ttbr = max(0,tc-target)

# print (target, ztba, ztbr, otba, otbr, ttba, ttbr)
if ztbr:
    for i in range(n-1,-1,-1):
        if a[i]=='0':
            ztbr-=1
            if ttba:
                a[i]='2'
                ttba-=1
            elif otba:
                a[i]='1'
                otba-=1
        if ztbr==0:
            break
if otbr:
    if ztba:
        for i in range(n):
            if otbr==0:
                break
            if a[i]=='1':
                a[i]='0'
                otbr-=1
                ztba-=1
            if ztba==0:
                break
    if otbr and ttba:
        for i in range(n-1,-1,-1):
            if otbr==0:
                break
            if a[i]=='1':
                a[i]='2'
                otbr-=1
                ttba-=1
            if ttba==0:
                break
if ttbr:
    if ztba:
        for i in range(n):
            if ttbr==0:
                break
            if a[i]=='2':
                a[i]='0'
                ttbr-=1
                ztba-=1
            if ztba==0:
                break
    if ttbr and otba:
        for i in range(n):
            if ttbr==0:
                break
            if a[i]=='2':
                a[i]='1'
                ttbr-=1
                otba-=1
            if otba==0:
                break
print(''.join(a))


N=int(input())
S=list(input())
Zero, One, Two = S.count("0"), S.count("1"), S.count("2")

i = 0
while i < N and Zero < N//3:
    if S[i] == "1" and One > N//3:
        S[i] = "0"
        Zero+=1
        One-=1
    elif S[i] == "2" and Two > N//3:
        S[i] = "0"
        Zero+=1
        Two-=1
    i += 1

i = N - 1
while i >= 0 and Two < N//3:
    if S[i] == "0" and Zero > N//3:
        S[i] = "2"
        Two += 1
        Zero -= 1
    elif S[i] == "1" and One > N//3:
        S[i] = "2"
        Two += 1
        One -= 1
    i-=1

i = 0
while i < N and One < N//3:
    if S[i] == "2" and Two > N//3:
        S[i] = "1"
        One += 1
        Two -= 1
    i+=1

i = N - 1
while i >= 0 and One < N//3:
    if S[i] == "0" and Zero > N//3:
        S[i] = "1"
        One += 1
        Zero -= 1
    i-=1



print("".join(S))   

from collections import Counter

N = int(input())
balanced = N // 3
s = list(map(int, list(input())))
counter = Counter(s)

if counter[0] < balanced:
    for i, n in enumerate(s):
        if n > 0 and counter[n] > balanced:
            s[i] = 0
            counter[n] -= 1
            counter[0] += 1
        if counter[0] == balanced:
            break

if counter[2] < balanced:
    for i, n in zip(range(N-1, -1, -1), s[::-1]):
        if n != 2 and counter[n] > balanced:
            s[i] = 2
            counter[n] -= 1
            counter[2] += 1
        if counter[2] == balanced:
            break

if counter[1] < balanced:
    for i, n in enumerate(s):
        if n == 2 and counter[2] > balanced:
            s[i] = 1
            counter[2] -= 1
            counter[1] += 1
        if counter[1] == balanced:
            break

if counter[1] < balanced:
    for i, n in zip(range(N-1, -1, -1), s[::-1]):
        if n == 0:
            s[i] = 1
            counter[1] += 1
        if counter[1] == balanced:
            break

print(*s, sep="")

n = int(input())
s = list(input())

ave = n // 3

c0, c1, c2 = 0, 0, 0
for c in s:
    if c == '0': c0 += 1
    if c == '1': c1 += 1
    if c == '2': c2 += 1


for check0 in range(len(s)):
    if s[check0] == '1' and c0 < ave and c1 > ave:
        s[check0] = '0'
        c0 += 1
        c1 -= 1
    elif s[check0] == '2' and c0 < ave and c2 > ave:
        s[check0] = '0'
        c0 += 1
        c2 -= 1

for check1 in range(len(s)):
    if s[check1] == '2' and c1 < ave and c2 > ave:
        s[check1] = '1'
        c1 += 1
        c2 -= 1

for check2 in range(len(s) - 1, -1 , -1):
    if s[check2] == '1' and c2 < ave and c1 > ave:
        s[check2] = '2'
        c2 += 1
        c1 -= 1
    elif s[check2] == '0' and c2 < ave and c0 > ave:
        s[check2] = '2'
        c2 += 1
        c0 -= 1

for check1 in range(len(s) - 1, -1 , -1):
    if s[check1] == '0' and c1 < ave and c0 > ave:
        s[check1] = '1'
        c1 += 1
        c0 -= 1
            
print("".join(s))

n=int(input())
m=n//3
a=list(input().strip())
a=list(map(int,a))
count=[0]*3
for i in a:
    count[i]+=1
if(count[0]>m):
    i=c=0
    while(c<=m):
        if(a[i]==0):
            c+=1
        i+=1
    j=i-1 #The first 0 which is to be converted
    while(j<n and count[1]<m):
        if(a[j]==0):
            a[j]=1
            count[0]-=1
            count[1]+=1
        j+=1
    if(count[0]>m):
        while(j<n and count[2]<m):
            if(a[j]==0):
                a[j]=2
                count[0]-=1
                count[2]+=1
            j+=1
if(count[2]>m):
    i=n-1
    c=0
    while(c<=m):
        if(a[i]==2):
            c+=1
        i-=1
    j=i+1 #The first 2 from right which is to be converted
    while(j>=0 and count[1]<m):
        if(a[j]==2):
            a[j]=1
            count[2]-=1
            count[1]+=1
        j-=1
    if(count[2]>m):
        while(j>=0 and count[0]<m):
            if(a[j]==2):
                a[j]=0
                count[2]-=1
                count[0]+=1
            j-=1
if(count[1]>m):
    j=c=0
    while(j<n and count[0]<m):
        if(a[j]==1):
            a[j]=0
            count[1]-=1
            count[0]+=1
        j+=1
    i=j
    while(i<n and c<=m):
        if(a[i]==1):
            c+=1
        i+=1
    j=i-1 #The first 1 which is to be converted
    if(count[1]>m):
        while(j<n and count[2]<m):
            if(a[j]==1):
                a[j]=2
                count[1]-=1
                count[2]+=1
            j+=1
print("".join(map(str,a)))

from collections import defaultdict

def solve():
    n = int(input())
    
    s = list(input())
    
    freq = defaultdict(int)
    
    for i in range(n):
        freq[s[i]] += 1
    
    zero_cnt = 0
    one_cnt = 0
    
    for i in range(n):
        if s[i] == "0" and zero_cnt < n // 3:
            zero_cnt += 1
            continue
        
        if freq["0"] < n // 3:
            if freq[s[i]] > n // 3:
                freq[s[i]] -= 1
                freq["0"] += 1
                s[i] = "0"
                continue
            
        if s[i] == "1" and one_cnt < n // 3:
            one_cnt += 1
            continue
            
        if freq["1"] < n // 3:
            if freq[s[i]] > n // 3:
                freq[s[i]] -= 1
                freq["1"] += 1
                s[i] = "1"
                continue
            
        if freq["2"] < n // 3:
            if freq[s[i]] > n // 3:
                freq[s[i]] -= 1
                freq["2"] += 1
                s[i] = "2"
                continue                
                
    print (''.join(k for k in s))
    
solve()

from collections import deque

n = int(input())
arr = [int(i) for i in input()]
ans = [0 for i in range(n)]

indx = [[] for i in range(3)]

for i in range(n):
	indx[arr[i]].append(i)


for i in range(3):
	indx[i] = deque(indx[i])

x = n//3


if len(indx[2])>x:
	diff = len(indx[2])-x
	while diff>0:
		if(len(indx[0]) < x):
			indx[0].append(indx[2][0])
			indx[2].popleft()
		elif len(indx[1]) < x:
			indx[0].append(indx[2][0])
			indx[2].popleft()
		diff-=1

if len(indx[1])>x:
	diff = len(indx[1])-x
	while diff!=0:
		if(len(indx[0]) < x):
			indx[0].append(indx[1][0])
			indx[1].popleft()
		elif len(indx[2]) < x:
			indx[2].append(indx[1][-1])
			indx[1].pop()
		diff-=1


if len(indx[0])>x:
	diff = len(indx[0])-x
	while diff!=0:
		if(len(indx[2]) < x):
			indx[2].append(indx[0][-1])
			indx[0].pop()
		elif len(indx[1]) < x:
			indx[1].append(indx[0][-1])
			indx[0].pop()
		diff-=1

for i in range(3):
	for j in indx[i]:
		ans[j] = i

print(''.join(str(i) for i in ans))


import math
import bisect
import itertools
import sys
I=lambda : sys.stdin.readline()
mod=10**9 +7
'''fact=[1]*100001
ifact=[1]*100001
for i in range(1,100001):
    fact[i]=((fact[i-1])*i)%mod
    ifact[i]=((ifact[i-1])*pow(i,mod-2,mod))%mod
def ncr(n,r):
    return (((fact[n]*ifact[n-r])%mod)*ifact[r])%mod
def npr(n,r):
    return (((fact[n]*ifact[n-r])%mod))
    '''


def mindiff(a):
    b=a[:]
    b.sort()
    m=10000000000
    for i in range(len(b)-1):
        if b[i+1]-b[i]<m:
            m=b[i+1]-b[i]
    return m
    
def lcm(a,b):
    return a*b//math.gcd(a,b)

    
def merge(a,b):
    i=0;j=0
    c=0
    ans=[]
    while i<len(a) and j<len(b):
        if a[i]<b[j]:
            ans.append(a[i])
            i+=1
        else:
            ans.append(b[j])
            c+=len(a)-i
            j+=1
    ans+=a[i:]
    ans+=b[j:]
    return ans,c
def mergesort(a):
    if len(a)==1:
        return a,0
    mid=len(a)//2   
    left,left_inversion=mergesort(a[:mid])
    right,right_inversion=mergesort(a[mid:])
    m,c=merge(left,right)
    c+=(left_inversion+right_inversion)
    return m,c
    
def is_prime(num):
    if num == 1: return False
    if num == 2: return True
    if num == 3: return True
    if num%2 == 0: return False
    if num%3 == 0: return False
    t = 5
    a = 2
    while t <= int(math.sqrt(num)):
        if num%t == 0: return False
        t += a
        a = 6 - a
    return True
    
  
def ceil(a,b):
    if a%b==0:
        return a//b
    else:
        return (a//b + 1)

def binsearch(arr,b,low,high):
    if low==high:
        return low
    if arr[math.ceil((low+high)/2)]<b:
        return binsearch(arr,b,low,math.ceil((low+high)/2) -1 )
    else:
        return binsearch(arr,b,math.ceil((low+high)/2),high)
def ncr1(n,r):
    s=1
    for i in range(min(n-r,r)):
        s*=(n-i)
        s%=mod
        s*=pow(i+1,mod-2,mod)
        s%=mod
    return s
    
def calc(n,m,r):
    s=0
    for i in range(0,r+1,2):
        s+=ncr1(n,i)*ncr1(m,i)
        s%=mod
    return s    
        
        

#/////////////////////////////////////////////////////////////////////////////////////////////////
n=int(input())
s=input()
c=''
d={'0':0,'1':0,'2':0}
ans=n//3
for i in s:
    d[(i)]+=1
d1={'0':0,'1':0,'2':0}
for i in s:
    if d['0']<ans:
        k='0'
    elif d['1']<ans:
        k='1'
    elif d['2']<ans:
        k='2'
    if d[i]>ans:
        if (int(i)<int(k) and d1[i]==ans) or int(i)>int(k):
            c+=k
            d[i]-=1
            d[k]+=1
            d1[k]+=1
        else:
            c+=i
            d1[i]+=1
    else:
        c+=i
        #d[i]-=1
        d1[i]+=1
    #print(c,d,d1)    
print(c)        


n=int(input())
a=list(input())
x=a.count('0')
y=a.count('1')
z=a.count('2')
if x<n//3:
    for i in range(n):
        if a[i]=='1' and y>n//3:
            a[i]='0'
            y-=1
            x+=1
        elif a[i]=='2' and z>n//3:
            a[i]='0'
            z-=1
            x+=1
        if x==n//3:
            break
if z<n//3:
    for i in range(n-1,-1,-1):
        if z==n//3:
            break
        if a[i]=='1' and y>n//3:
            a[i]='2'
            y-=1
            z+=1
        elif a[i]=='0' and x>n//3:
            a[i]='2'
            z+=1
            x-=1
if y<n//3:
    for i in range(n):
        if a[i]=='2' and z>n//3:
            a[i]='1'
            z-=1
            y+=1
    for i in range(n-1,-1,-1):
        if a[i]=='0' and x>n//3:
            a[i]='1'
            y+=1
            x-=1
    
print(''.join(a))

n = int(input())
s = input()
a = []
k0, k1, k2 = 0, 0, 0
for i in s:
    if i == '0':
        k0 += 1
    elif i == '1':
        k1 += 1
    else:
        k2 += 1
    a.append(i)
n1 = n // 3
if k1 == k2 and k2 == k0:
    print(s)
else:
    for i in range(n):
        if s[i] == '2':
            if k2 > n1:
                if k0 < n1:
                    a[i] = '0'
                    k0 +=1
                    k2 -= 1
                elif k1 < n1:
                    a[i] = '1'
                    k1 += 1
                    k2 -= 1
        if s[i] == '1':
            if k1 > n1:
                if k0 < n1:
                    a[i] = '0'
                    k0 +=1
                    k1 -= 1    
    for i in range(n-1, -1, -1):
        if a[i] == '0':
            if k0 > n1:
                if k2 < n1:
                    a[i] = '2'
                    k2 +=1
                    k0 -= 1
                elif k1 < n1:
                    a[i] = '1'
                    k1 += 1
                    k0 -= 1
        if a[i] == '1':
            if k1 > n1:
                if k2 < n1:
                    a[i] = '2'
                    k2 +=1
                    k1 -= 1          
    for i in a:
        print(i, end = '')

N=int(input())
S=[str(i) for i in input()]
L=[0,0,0]
for s in S:
    L[int(s)]+=1
num=N//3
T=S
a,b,c=L[0],L[1],L[2]
if a>=num and b>=num and c<=num:
    t=num-c
    s=a-num
    u=b-num
    i=N-1
    while t>0:
        if T[i]=='1' and u!=0:
            T[i]='2'
            t-=1
            u-=1
        elif T[i] == '0' and s != 0:
            T[i] = '2'
            t -= 1
            s -= 1
        i-=1

elif a>=num and b<=num and c<=num:
    t=num-c
    i=N-1
    while t>0:
        if T[i]=='0':
            T[i]='2'
            t-=1
        i-=1
    s=num-b
    while s>0:
        if T[i]=='0':
            T[i]='1'
            s-=1
        i-=1

elif a>=num and b<=num and c>=num:
    t=c-num
    i=0
    while t>0:
        if T[i]=='2':
            T[i]='1'
            t-=1
        i+=1
    i=N-1
    s=a-num
    while s>0:
        if T[i]=='0':
            T[i]='1'
            s-=1
        i-=1

elif a<=num and b>=num and c<=num:
    t=num-a
    i=0
    while t>0:
        if T[i]=='1':
            T[i]='0'
            t-=1
        i+=1
    i=N-1
    s=num-c
    while s>0:
        if T[i]=='1':
            T[i]='2'
            s-=1
        i-=1
elif a<=num and b<=num and c>=num:
    t=num-a
    i=0
    while t>0:
        if T[i]=='2':
            T[i]='0'
            t-=1
        i+=1
    s=num-b
    while s>0:
        if T[i]=='2':
            T[i]='1'
            s-=1
        i+=1
elif a<=num and b>=num and c>=num:
    t=num-a
    s=b-num
    u=c-num
    i=0
    while t>0:
        if T[i]=='2' and u!=0:
            T[i]='0'
            t-=1
            u-=1
        elif T[i]=='1'and s!=0:
            T[i]='0'
            t-=1
            s-=1
        i+=1
print(''.join(T))
#print(L)


n = int(input())
s = input()

nrml = n // 3
elm_array = [nrml - s.count(str(i)) for i in range(3)]

for i in [0,2,1]: # i = 1
	if elm_array[i] > 0:
		for j in range(3): # j = 0
			if elm_array[j] < 0:
				to_replace = min(elm_array[i], -elm_array[j])
				elm_array[i] -= to_replace
				elm_array[j] += to_replace
				if i > j:
					s = s[::-1].replace(str(j), str(i), to_replace)[::-1]
				else:
					s = s.replace(str(j), str(i), to_replace)

print(s)

n = int(input())
s = input()
c0, c1, c2 = 0, 0, 0
for x in s:
    if x == '0':
        c0 += 1
    elif x == '1':
        c1 += 1
    elif x == '2':
        c2 += 1
r = n // 3
#print(c0, c1, c2)

need = abs(r - c0) + abs(r - c1) + abs(r - c2)
need //= 2
#print(need)

ar = [x for x in s]

if c0 < r:
    for x in range(n):
        #print(''.join(ar))
        if ar[x] == '1' and c1 > r:
            c0 += 1
            c1 -= 1
            ar[x] = '0'
        elif ar[x] == '2' and c2 > r:
            c0 += 1
            c2 -= 1
            ar[x] = '0'
        #print(''.join(ar))
        #print('-' * 10)
        if c0 == r:
            break
        

if c2 < r:
    for x in range(n - 1, -1, -1):
        #print(''.join(ar))
        if ar[x] == '1' and c1 > r:
            c2 += 1
            c1 -= 1
            ar[x] = '2'
        elif ar[x] == '0' and c0 > r:
            c2 += 1
            c0 -= 1
            ar[x] = '2'
        #print(''.join(ar))
        #print('-' * 10)
        if c2 == r:
            break


if c2 > r:
    for x in range(n):
        #print(''.join(ar))
        if ar[x] == '2':
            c1 += 1
            c2 -= 1
            ar[x] = '1'
        #print(''.join(ar))
        #print('-' * 10)
        if c2 == r:
            break
if c0 > r:
    for x in range(n - 1, -1, -1):
        #print(''.join(ar))
        if ar[x] == '0':
            c1 += 1
            c0 -= 1
            ar[x] = '1'
        #print(''.join(ar))
        #print('-' * 10)
        if c0 == r:
            break

print(''.join(ar))