Right Cyclic Shift via Assignment Operations

You are given an integer \(n\) and a right-shift parameter \(K\). An array \(a\) of length \(n+1\) is defined as follows:

\(a_i = i \) for \(1 \le i \le n\) and \(a_{n+1} = 0\).

You are allowed to perform only one kind of operation by printing a string of the form "i j" (with a single space between two positive integers \(i,j\)) where \(1 \le i,j \le n+1\). This operation means that you assign \(a_i = a_j\) (the value at index \(j\) is copied to index \(i\), while \(a_j\) remains unchanged).

Your goal is to transform the first \(n\) elements of \(a\) so that they become a right cyclic shift by \(K\) positions. In other words, after all your operations, the following must hold:

• For \(1 \le i \le K\): \(a_i = n-K+i\).
• For \(K+1 \le i \le n\): \(a_i = i-K\).
• The value of \(a_{n+1}\) can be arbitrary.

You are allowed at most \(T = \lfloor 1.5\,n \rfloor\) assignment operations. Your score on a test case is determined by the number of operations \(S\) you use:

• If \(S \le T\), you get 100 points.
• If \(T < S \le 4T\), you get 50 points.
• If \(S > 4T\), you get 0 points.

Your final score is the minimum score over all test cases.

Note about arithmetic: All formulas must be interpreted in \(\LaTeX\) format. For example, use \(\lfloor 1.5\,n \rfloor\) for the expression.

Hint: Since the initial array is \(a = [1,2,\dots,n,0]\) and the desired array is known, you can compute a permutation that sends each index \(x\) to its destination. In this problem the permutation \(f\) (on indices \(1, 2, \dots, n\)) is defined by:

[ f(x)=\begin{cases}x+K,&\text{if }x\le n-K,\ x-(n-K),&\text{if }x> n-K.\end{cases} ]

An efficient method to perform the permutation with minimal moves is to decompose it into cycles and then rotate each cycle in place using the extra cell \(a_{n+1}\) as temporary storage. To achieve the correct result, for every index \(i\) (\(1 \le i \le n\)) the final value should satisfy:

[ a[i]=\begin{cases}n-K+i,&1\le i\le K,\i-K,&K+1\le i\le n.\end{cases} ]

</p>

inputFormat

The input consists of two integers \(n\) and \(K\) on a single line.

It is guaranteed that \(n \ge 1\) and \(0 \le K \le n\). (When \(K=0\) the array remains unchanged.)

outputFormat

Output a sequence of operations, each on its own line. Each operation must be a pair of integers \(i\) and \(j\) separated by a space, meaning that you set \(a_i = a_j\). The sequence of operations must transform the first \(n\) elements of \(a\) into a right cyclic shift by \(K\) positions as described above. If no operations are needed, output nothing.

Important: The total number of operations must be at most \(T = \lfloor 1.5\,n \rfloor\) to achieve full score.

sample

5 2

6 1
1 4
4 2
2 5
5 3
3 6

</p>