Johnny, like every mathematician, has his favorite sequence of distinct natural numbers. Let’s call this sequence . Johnny was very bored, so he wrote down copies of the sequence in his big notebook. One day, when Johnny was out, his little sister Mary erased some numbers(possibly zero) from every copy of and then threw the notebook out onto the street. You just found it. Can you reconstruct the sequence?
In the input there are sequences of natural numbers representing the copies of the sequence after Mary’s prank. In each of them all numbers are distinct. Your task is to construct the shortest sequence that might have been the original . If there are many such sequences, return the lexicographically smallest one. It is guaranteed that such a sequence exists.
Sequence is lexicographically less than sequence if and only if there exists such that for all .
In the first line, there is one number denoting the number of copies of .
This is followed by
and in next line a sequence of length representing one of sequences after Mary's prank. All numbers are separated by a single space.
All values in one sequence are distinct numbers in range .
In one line, write the space-separated sequence - the shortest sequence that might have been the original . If there are many such sequences, return the lexicographically smallest one.
2 3 4
1 2 3 4
You have 2 copies of the sequence with some missing numbers: and . There are two candidates for the original sequence , where the first one is lexicographically least.