Mechanical Doll

A mechanical doll is a doll that automatically repeats a specific sequence of motions. Many mechanical dolls have been created in Japan since ancient times.

The motions of a mechanical doll are controlled by a circuit made of devices. The devices are connected with tubes. Each device has one or two exits and any number (possibly zero) of entrances. Each tube connects an exit of a device to an entrance of the same or another device. Exactly one tube is connected to each entrance, and exactly one tube is connected to each exit.

A ball is placed on one of the devices and travels through the circuit. At each step, the ball leaves its current device through one of its exits, follows the tube attached to that exit, and enters the device at the other end.

There are three types of devices: origin, trigger, and switch. There is exactly one origin, $M$ triggers, and $S$ switches, where $S$ can be zero. You must decide the value of $S$.

The origin is the device where the ball is placed at the start. It has one exit and serial number 0.

A trigger makes the doll perform a specific motion whenever the ball enters it. Every trigger has one exit. The serial numbers of the triggers are 1 to $M$.

Each switch has two exits, called 'X' and 'Y'. The state of a switch is either 'X' or 'Y'. After the ball enters a switch, it leaves through the exit given by the current state, and then the switch changes to the opposite state. Initially, every switch is in state 'X'. The serial numbers of the switches are -1 to -$S$.

You are given $M$ and a sequence $A$ of length $N$, where each element is a trigger serial number. A trigger may appear zero or more times in $A$. Create a circuit that satisfies all of the following conditions.

• The ball returns to the origin after some steps.
• When the ball first returns to the origin, every switch is in state 'X'.
• Before the ball first returns to the origin, it enters exactly $N$ triggers, and their serial numbers in entry order are $A_0, A_1, \ldots, A_{N-1}$.
• Let $P$ be the total number of state changes of all switches before the ball first returns to the origin. $P$ does not exceed 20,000,000.

You also want to avoid using too many switches.

Constraints

• $1 \le M \le 100000$
• $1 \le N \le 200000$
• $1 \le A_k \le M$ (for $0 \le k \le N-1$)