This small puzzle was proposed at one of contests by Ozon company (local marketplace, like Amazon),
which I joined recently. These contests are used as "screening" for junior and trainee positions and internal
IT-courses.
Velta is preparing her PhD work on Robotics. Particularly she needs it in printed form, but being a perfectionist, she decided to review the work once more - this process includes reading pages here and there, only then sending them to printer.
As a result, pages are sent to be printed in somewhat random order. Sometimes as ranges of several sequential
pages. Say, page 1 is sent (with table of contents), then page 7 with the main diagram, then pages 2-5,
then 8. Then Velta forgets what exactly was already printed and sends pages 7-10, and so on.
At some moment Velta sees it is the time to rush to University. But she has a heap of pages - some lacking, some duplicating! She can reorder and deduplicate them while on her way, but she utterly needs lacking pages to be printed at once. We are going to help her!
Recollect the format used in printing dialog of Microsoft Word and similar programs. It consists of page numbers, separated with commas. There are also ranges of pages, as start and end page number, separated with dash.
We'll use such format as input - to describe which pages were printed already. E.g. example above makes the sequence:
1,7,2-5,7-10
And you need to give the list of lacking pages (those needed to be printed yet) in the same format. Ordered by ascending of numbers to simplify Velta's efforts in ordering them.
Input data contains the number T of test-cases to follow.
Next T lines contain the value N - total number of pages - and then, separated by space, the list
of pages which were already printed.
Answer should provide a list of remaining pages for each case, space-separated. Choose the shortest representation (any of them, if there are several).
Example:
input data:
7
8 7
8 1,7,1
8 1-5,1,7-7
10 1-5
10 1,2,3,4,5,6,8,9,10
3 1-2
100 1-2,3-7,10-20,100
answer:
1-6,8 2-6,8 6,8 6-10 7 3 8-9,21-99