It's May, and summer is in full swing!
Elen lives on a street of ~N~ adjacent houses, all of them being numbered an integer from ~1~ to ~N~. Being in a suburban neighbourhood, all of these houses have fragrant gardens and a sprinkler system on their front lawn.
On a particularly sweltering day, ~M~ of these houses decide to turn on their sprinklers. However, since the sprinklers on Elen's street are interconnected, whenever one house turns on its sprinkler, the sprinklers of that house and adjacent houses will flip states. If one of the three was previously on, it would turn off, and vice versa.
Elen wants to know which houses will have their sprinklers still on by the end of the day.
The first line will contain the integer ~N~ and ~M~, the number of houses on Elen's street, and the number of houses that turn on their sprinklers.
The following ~M~ lines will contain a single integer ~h_i~, the address of the next house to turn on their sprinkler.
Assume that all houses start with their sprinklers turned off and ~M~ of them turn sequentially in the order inputted. Note that if a house's sprinkler was already on and it was the next input, it would flip and turn off.
~1 \le N, M \le 5\,000~
~1 \le h_i \le N~
Print the addresses of all houses with their sprinklers on, space-separated on one line in increasing order. It is guaranteed that there will be at least one house with its sprinklers on.
6 3 3 4 2
1 3 5
Let us represent a house with a sprinkler on using
X, and a house without a sprinkler on using
.. Simulating the moves:
Therefore, houses ~1~, ~3~, and ~5~ have their sprinklers on at the end of the day.