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

Ural Championship 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Game Testing

Time limit: 1.0 second
Memory limit: 64 MB
In the Higgs Pong game, each player can adjust the graphics to the performance of his computer by switching on or off some of the graphics options. There are n graphics options in the game. If they are all turned on simultaneously, the game slows down even on the most powerful computers.
When the development of the game was almost complete, it turned out that the team’s PR expert had placed at several popular game sites the information that the game would work perfectly on the Everest personal computer. Then the developers bought such a computer and asked their tester Ivan to find graphics configurations for which the game would work well on it.
Ivan set up a certain configuration of graphics settings, started the game, played it for some time, and wrote the result in his notebook. Then he continued tests changing exactly one setting before each of the following tests (he either switched on an option that was turned off at that moment or switched off an option that was turned on at that moment). Ivan chose the changes in such a way that no configuration had been tested twice. After some time Ivan decided that he had tested enough configurations and went to the developers to present the results.
Given the initial and final configurations of the graphics settings, find the maximum number of configurations that Ivan could test.


The first line contains the number n of graphics options (1 ≤ n ≤ 16). In the second line you are given the initial graphics configuration in the form of a list of integers k a1 a2 ... ak, where k is the number of active options and the integers ai are the numbers of these options (0 ≤ kn; 1 ≤ a1 < a2 < ... < akn). In the second line you are given the final graphics configuration in the same format. The initial and final configurations are different.


In the first line output the maximum number m of tested configurations including the initial and final configurations. In each of the following m lines give these configurations in the order in which Ivan tested them. The configurations must be given in the same format in which the initial and final configurations are given in the input data. If the problem has several solutions, output any of them. It is guaranteed that there exists at least one solution.


2 1 2
1 2
2 1 2
Problem Author: Idea by Alexander Ipatov
Problem Source: Ural Sport Programming Championship 2013
To submit the solution for this problem go to the Problem set: 1972. Game Testing