Sasha and Lisa — two most ordinary girls who live in Moscow and love St. Petersburg very much. For the holidays, they planned an extensive excursion program in the northern capital, it remains only to buy tickets. The girls know that the fastest way to get to St. Petersburg is on the Sapsan high-speed train. Each car has N rows, each of which has 4 seats, which are numbered like this:
Sasha and Liza have chosen the car in which they plan to travel. It turned out that M tickets have already been sold in this car and it is known which seats are already occupied. The girls decided to buy tickets in this way:
- if there are two places next to each other, then they buy them (for example, 1 and 2 or 3 and 4)
- if there are no two seats nearby, then they try to buy seats next to each other through the aisle (for example, 2 and 4)
- If there are no such seats, then they buy any two free seats.
Help Sasha and Lisa determine which seats they should buy. It is guaranteed that there are at least two empty seats in the selected car.
Input
The first line of the input contains numbers N — the number of rows in the car (1 ≤ N ≤ 10
5) and M — number of tickets sold (1 ≤ M ≤ 4N - 2). The next line contains M different numbers — numbers of seats for which tickets have already been sold.
Imprint
Print two numbers — numbers of seats for which girls should buy tickets. If multiple answers are possible, print any of them.
Examples
| # |
Input |
Output |
| 1 |
2 3
3 7 8
| 5 6 |
| 2 |
2 5
1 4 5 2 7
| 6 8 |
| 3 |
2 5
2 7 4 5 6
| 1 3 |