MalnaRISC

Time limit1sMemory limit512 MB

Summary

Given N, output a parallel sorting network of CMPSWP comparator lines that sorts N registers, minimizing the number of parallel nanoseconds.

Level: Hard8 of 10
Topics: Sorting, Divide and conquer, Implementation, Brute force
Solved: No attempts yet

Problem

It is early in the morning and the Croatian IOI team is starting to assemble at the Zagreb airport. The trip is long, with the final destination being Singapore and a layover in Amsterdam. Mr. Malnar drank the last drop of his grapefruit-based beverage and ordered the team to proceed to the gate. As usually happens, he disappeared after the security check and somehow managed to show up just a few minutes before boarding.

Olympian 1: Where were you?! I swear you're going to miss the next flight if you keep doing this.

Mr. Malnar: It's not my fault this time, the security wouldn't let me through. They thought I might be a terrorist.

Olympian 2: A terrorist?! You wouldn't hurt a fly. What happened?

Mr. Malnar: Ah, they found MalnaRISC (Reduced Instruction Set Computer) and refused to believe me that I am capable of building my own processor. They let me go once I explained how efficient it is at sorting integers.

Olympian 3: I also wouldn't believe you. As a matter of fact, I still don't. What makes your processor so interesting?

Mr. Malnar: You are members of our national IOI team, I shouldn't need to explain anything to you. Here is the documentation, figure it out yourselves.

Olympian 4: Give that to me, I'll solve this year's COI on it using the assembly.

The assembly language for MalnaRISC contains a single instruction:

CMPSWP $R_i$ $R_j$ : swaps the values in registers $R_i$ and $R_j$ if $R_i > R_j$ holds.

What's special about MalnaRISC is that all instructions written on the same line execute in parallel during a single nanosecond. Naturally, each register can only be used at most once as an argument in a single line.

It is known that registers $R_1, R_2, \dots, R_N$ contain some integers. Write an efficient code in assembly that sorts these values in non-descending order.

Input

The only line contains an integer $N$ from the task description.

Output

Output an integer $t$ on the first line denoting the execution time of your program (in nanoseconds).

On the next $t$ lines output the assembly code that sorts the values in the $N$ registers. Each line should contain at least one instruction, and each register should only be mentioned once in a single line. Each instruction needs to be of the form "CMPSWP $R_i$ $R_j$ " ( $1 \le i, j \le N$ ), and the instructions in a single line need to be separated by a single space character.

Examples3

Example 1
Input
```
2
```
Expected output
```
1
CMPSWP R1 R2
```

Example 2

Input

Expected output

3
CMPSWP R1 R2
CMPSWP R1 R3
CMPSWP R2 R3

Example 3

Input

Expected output

4
CMPSWP R1 R3
CMPSWP R2 R4
CMPSWP R1 R2 CMPSWP R3 R4
CMPSWP R2 R3