Gudrinieku ciema skolēnam Paulim šodien ir kontroldarbs matemātikā. Vienā uzdevumā viņam ir dots nenegatīvs vesels skaitlis x binārajā pierakstā un prasīts atrast vismazāko tādu nenegatīvu veselo skaitli y, ka skaitlis z = x xor y ir palindroms, ja to arī uzraksta binārajā pierakstā.

Paulim izdevās izzagties uz tualeti un nosūtīt izziņu ar šo uzdevumu Jums – tā kā jums ir dators, palīdziet Paulim atrisināt uzdevumu!

Pirmajā rindā dots viens naturāls skaitlis n (1 ≤ n ≤ 10⁵), ciparu skaits x binārajā pierakstā. Nākamajā rindā dota virkne no simboliem 0 un 1 garumā n, x pierakstīts binārajā skaitīšanas sistēmā. Garantēts, ka pierakstā nav vadošo nuļļu.

Izvadiet prasīto skaitli y binārajā pierakstā bez vadošajām nullēm.

Diviem bināriem cipariem a un b operācija xor tiek definēta šādi:

0 xor 0 = 0

0 xor 1 = 1

1 xor 0 = 1

1 xor 1 = 0

Pieņemsim, ka skaitļi x un y binārajā pierakstā ir a₁a₂...a_n un b₁b₂...b_n (iespējams, ar vadošajām nullēm). Par x xor y sauc tādu skaitli, kura binārais pieraksts ir c₁c₂...c_n, kur c_i = a_i xor b_i visiem i no 1 līdz n. 

Simbolu virkni sauc par palindromu, ja to lasa vienādi gan no kreisās, gan no labās puses. Piemēram, 10101 un 1001 ir palindromi, bet 011 – nav.