Sorting Machine Design

Bull recently learned about sorting algorithms and became fascinated with their efficiency. He now wants to design a computer that can sort an array in ascending order using a series of comparators.

The array to be sorted is stored in a size \(n\) array \(Q\). The basic unit of computation is a comparator. A comparator is represented as a triple \((i,j,t)\) where \(1 \le i Q_j\), it swaps their values, otherwise it does nothing.

To ensure that the computer works (although it might not solve the problem if designed incorrectly), any two comparators must not conflict. Two comparators \((A,B,S)\) and \((C,D,T)\) are said to conflict if and only if among \(A, B, C, D\) there are at least two equal numbers and \(S = T\). For example, comparators \((1,3,1)\) and \((2,4,1)\) do not conflict, whereas \((1,2,3)\) and \((2,3,3)\) do conflict.

The total running time of the computer is defined as the maximum time parameter among all comparators, denoted as \(w\), and a smaller \(w\) represents a faster running time.

For each test group, you are given \(q\) problems. Each problem consists of a permutation \(P\) of \(\{1,2,\dots,n\}\). Your task is to design a sorting machine that, with a running time not exceeding \(m\), is capable of sorting every provided permutation.

Hint: One possible approach is to use the odd–even transposition sort (a form of sorting network) which involves \(n\) phases. In odd phases, comparators operate on pairs \((1,2)\), \((3,4)\), etc., and in even phases, on pairs \((2,3)\), \((4,5)\), etc. Note that in each phase, the comparators are placed such that none share an index.

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\) where:

• \(n\) is the size of the array \(Q\),
• \(m\) is the maximum allowed running time, and
• \(q\) is the number of permutation problems.

Each of the following \(q\) lines contains a permutation of \(n\) integers representing a test case.

outputFormat

Output the description of your sorting machine. The first line should contain an integer \(k\) which is the number of comparators used. The following \(k\) lines should each contain three integers \(i\), \(j\), and \(t\) indicating that at time \(t\), the comparator compares \(Q_i\) and \(Q_j\) and swaps them if needed.

Your designed machine must be able to sort every given permutation and the maximum time \(t\) used (i.e. the run time \(w\)) must not exceed \(m\).

sample

3 3 1
3 1 2

6
1 2 1
2 3 1
2 3 2
1 2 3