Thornhill Computer Club 2023 - December Contest - Problem 1

The 30th of November by The Ministry of Elvish Affairs
`Twas the season once more, proclaimed Saint Nick bold, Through the elf village, his voice mighty and old.
Conscripting young elves, six and above, For the Christmas crunch, a mission of love.

Unaware was dear Santa, of the plot in the air, A local elf youth grinned with a mischievous stare.
A grand "Grinching" scheme was about to unfold, As the factory elves planned, secrets to be told.

Little by little, in rows side by side, They conspired and whispered, their plans to confide.
To steal from the red-suited, jolly old man, But the obstacle faced was the security plan.

For the factory was guarded by tech of the past, A dated system that seemed to forever last.
Yet the elves, undeterred, with determination aflame, Dreamt of a Christmas without Santa's grand claim.

The present pipeline contains ~N~ presents with ids in order from ~1~ to ~N~. The elves have collectively made lists of some (if not all) of the presents they want to take home without permission. However, the pipeline contains a state of the art security system, almost impossible to bypass. The elves obviously already knew this, having intricately worked within the factory, and have coordinated to steal the presents immediately before the daily security check.

This check consist of a single security scanner, which starts by scanning the first present's id recording it's value. It then scans every third present after the initial present along the pipeline and checks if the difference between the last id and the current id is exactly 3. Upon reaching the end of the pipeline, the scanner with approve of the batch only if there are either no presents to scan or no errors detected between present ids. To counteract this system, the elves have come prepared with fake id tags and can manually replace the id of any present with a new value, after stealing their desired presents, before the security check is run.

Given a batch size ~N~ presents and ~M~ present ids to steal, return old and new ids of the presents that would need to be modified in order for the new line of presents to pass the security check. Output -1 if there are no presents that need to be changed.

Input Specifications

The first line consists of two integers ~N~ and ~M~ representing the batch size and number of presents to steal.
The next ~M~ lines consist of an integer ~P_i~ representing the present numbers to steal.
Due to the elves lack of communication, there can be multiple occurrences of the same present tag.

Output Specification

On each line for each modified present, output their old and new id separated by a space in ascending order (the order they are scanned).

Constraints

For all subtasks:
~1 \le P \le N, M \le 100,000~

Subtask 1 [30%]:

• ~1 \le M \le N \le 100~
• All stolen presents are unique and are in sorted order

Subtask 2 [30%]:

• ~1 \le M, N \le 1000~

Subtask 3 [40%]:

• No further constraints

Sample Input 1

12 4
3
5
6
11

Sample Output 1

7 4
10 7

Explanation of Sample Output 1

You are given a batch of 12 presents: 1 2 3 4 5 6 7 8 9 10 11 12
After stealing presents 3, 5, 6, 11, the remaining presents are: 1 2 4 7 8 9 10 12
By replacing present id 7 with 4 and 10 with 7, the scanner will be tricked into approving the batch of presents.
After replacing the ids the remaining presents will be numbered: 1 2 4 4 8 9 7 12

Sample Input 2

4 1
2

Sample Output 2

-1

Explanation of Sample Output 2

You are given a batch of 4 presents: 1 2 3 4
After removing present 2, you are left with: 1 3 4
The machine will only scan the initial present, leaving no present ids needing to be changed.

Sample Input 3

22 9
12
13
16
17
9
11
19
2
3

Sample Output 3

6 4
10 7
18 10
22 13