Spider Fashion

Brown Yellow Blak Cross Orb Weaver Spider. Photo by
Pixabay

Spiderdad is dressing up Spiderdaughter for UCLA’s SpiderCon in Ackerman Grand Ballroom. He has to choose from $n$ colors shoes (colors $1$ to $n$) and $m$ colors (colors $1$ to $m$) of socks. You can assume Spiderdaughter has an infinite supply of each color.

Spiderdaughter’s fashion sense requires that that no leg should have sock and shoe of the same color. SpiderCon rules require that no two adjacent shoes (i.e. shoes on adjacent legs) and no two adjacent socks have the same color.

Output a valid outfit, or that no valid outfit exists.

Note: Spiderdaughter, being a spider, has $8$ legs. However, on some years, she receives an extra leg on Christmas for being a good spider. So, in conclusion, the spider can have $8$ or $9$ legs. Also, recall from grade school that the legs of a spider are not arranged in a straight line, but in a circular fashion around the body :)

The only line of the input contains three space separated integers $l$ ($8$ or $9$), $n$ ($1 \leq n \leq 10^6 $), and $m$ ($1 \leq m \leq 10^6 $).

Output $-1$ if there is no valid outfit. Otherwise, the output consists of 3 lines: Line 1: The first line of output consists of a single integer $c$, the total number of colors used. Line 2: $l$ space separated integers representing the choices of shoe colors for each leg in order. Each integer $i$ in this list must be in the range ($1 \leq i \leq n$). Line 3: $l$ space separated integers representing the choices of sock colors for each leg in order. Each integer $i$ in this list must be in the range ($1 \leq i \leq m$).

Sample Input 1 | Sample Output 1 |
---|---|

8 4 5 |
5 4 1 3 1 4 3 2 1 3 2 1 2 1 5 4 5 |

Sample Input 2 | Sample Output 2 |
---|---|

8 1 5 |
-1 |