32834번 - Pair Sorting 스페셜 저지다국어

문제

There are $n$ bins arranged in a row and 2ドルn$ balls on the ground. The balls are numbered from 1ドル$ to $n$ and there are exactly two balls numbered $i,ドル for each $i,ドル 1ドル ≤ i ≤ n$. Also, for 1ドル ≤ i ≤ n,ドル the $i$-th bin is denoted by $B_i$ and each bin $B_i$ can contain at most two balls. Initially, the bin $B_i$ contains both of ball $n + 1 - i$’s, for 1ドル ≤ i ≤ n$. See the Figure F.1 below for the initial configuration of bins.

Figure F.1. The initial configuration of bins

You can swap two balls only from adjacent bins, which implies one swap operation. Note the bin is not a stack and for adjacent bins $B_i$ and $B_{i+1},ドル you can swap the one of two balls in $B_i$ and the one in $B_{i+1}$. See the Figure F.2 below. The figure represents two swap operations.

Figure F.2. The swap operations between adjacent bins

Through these swap operations, you should sort the balls. As a result of the sorting, the bin $B_i$ must contain the both of ball $i$’s, for 1ドル ≤ i ≤ n$. In particular, the total number of swap operations should be no more than $Bound,ドル when $Bound$ is given as a function of $n,ドル especially, $Bound = 0.7n^2$.

Given $n$ bins and 2ドルn$ balls, write a program to find a sorting method of balls such that the total number of swap operations is no more than $Bound = 0.7n^2$.

입력

Your program is to read from standard input. The input consists of exactly one line. The line contains an integer $n$ (3ドル ≤ n ≤ 100$), representing that there are $n$ bins and 2ドルn$ balls.

출력

Your program is to write to standard output. Let $S$ be the total number of swap operations in your sorting method for the input. Print exactly $S + 1$ lines. The first line contains $S$. Each of the following $S$ lines contains three integers $j,ドル $a,ドル and $b,ドル representing one swap operation between the ball $a$ in the bin $B_j$ and the ball $b$ in $B_{j+1},ドル where 1ドル ≤ j ≤ n - 1$ and 1ドル ≤ a, b ≤ n$. The swap operations in your sorting method should be printed in order, one per line. The number $S$ must satisfy that $S ≤ 0.7n^2$.

제한

힌트