ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC, Eastern subregion, Yekaterinburg, October 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Sense of Beauty

Time limit: 0.5 second
Memory limit: 64 MB
The owner of a casino for New Russians has a very refined sense of beauty. For example, after a game there remain two piles with the same number of cards on the table, and the owner likes the cards to be arranged into two piles according to the color: one pile with red cards and the other with black cards. Of course, this is done not by the owner himself, but by a croupier. The owner just likes to watch the process. The croupier takes a card from the top of one of the initial piles and puts it into one of the new piles; this is repeated until all the cards from the initial piles are transferred. The owner doesn't like it if one of the resulting piles grows faster than the other. At each moment the resulting piles must not differ in size by more than one card; a bigger difference would contradict the owner's sense of beauty. Help the croupier to arrange the cards according to the tastes of his owner.


The first line of the input contains the number N of cards in each of the piles (4 ≤ N ≤ 1000). Each of the next two lines contains N digits 0 or 1 describing the piles: 1 denotes a red-suit card and 0 denotes a black-suit card. The cards in a pile are described from the top to the bottom. There are in total N red and N black cards in the two piles.


Output a line containing 2N digits 1 or 2, which describes the process of transferring the cards. Each number shows the number of the pile from which a card is taken. If it is impossible to perform this task according to the given rules, output "Impossible".


Problem Author: Leonid Volkov, Stanislav Vasilyev
Problem Source: Quarter-Final of XXXI ACM ICPC - Yekaterinburg - 2006
To submit the solution for this problem go to the Problem set: 1501. Sense of Beauty