Problem E
Dining Disaster

The Noxus and Piltover representatives are holding a meeting to discuss their policy towards the undercity. They gather in a room, where there is a long table pointing from west to east with $N$ seats on either side. The representatives are trying to sit down to discuss, but no representative wants to sit next to or across from another and make the situation awkward. Note that sitting diagonally across from another representative is permitted. $K$ representatives are already sitting down at specified seats. Find a way to fit as many additional representatives at the table without making it awkward.

Input

The first line contains two space-separated integers, $N (1 \le N \le 2 \cdot 10^5)$ and $K (0 \le K \le 2N)$.
The next $K$ lines specify the position of one of the already seated representatives in the form $a_i$ $b_i$:

• $a_i$ is either $1$ or $2$, for whether the representative is on the north or south side of the table, respectively.

• $b_i$ $(1 \le b_i \le N)$ denotes the seat number of the representative, where $1$ denotes the westmost seat and $N$ denotes the eastmost seat.

It is guaranteed that no two of the existing $K$ representatives are next to or across from one another.

Output

The first line consists of a single integer $M$, representing the maximum number of representatives that can be seated at the table (including the representatives given in the input).
Line $2$ contains $N$ characters, where the $i$-th character is X if the $i$-th seat on the north side is occupied, and . otherwise.
Line $3$ contains $N$ characters, where the $i$-th character is X if the $i$-th seat on the south side is occupied, and . otherwise.
If there are multiple possible seating arrangements which achieve the maximum, you may output any arrangement.

5 3
1 1
2 3
1 5

3
X...X
..X..

10 3
2 1
1 5
2 7

8
.X..X..X.X
X.X...X.X.