题目描述

本题译自 eJOI2020 Problem D. Xor Sort

给定一个整数 $S$ 和一个包含 $N$ 个非负整数的数列 $A$（下标从 $1$ 开始）。你可以对数列进行如下操作：选取任意一个下标 $i$（$1\le i\le N$），再选取它相邻元素中的一个 $j$（$1\le j\le N$，满足 $j=i-1$ 或 $j=i+1$），把 $A_i$ 换为 $(A_i\oplus A_j)$，其中 $\oplus$ 是异或运算。异或运算的定义见「数据范围与提示」。

你的目标是把 $A$ 数列变为一个排好序的数列：

• 若 $S=1$，则最后的序列必须严格递增，即对于 $1\le i<N$，有 $Ai<A{i+1}$；
• 若 $S=2$，则最后的序列必须单调不减，即对于 $1\le i<N$，有 $Ai\le A{i+1}$。

找到能满足条件的一组操作序列。

你不需要最小化操作数，只需要保证操作数不超过 $40000$ 即可。

输入格式

第一行两个整数 $N,S$。

接下来一行 $N$ 个非负整数 $A_1,A_2,\ldots ,A_N$。

输出格式

第一行输出一个整数 $K\ (0\le K\le 40000)$，表示操作数。

接下来 $K$ 行，按时间顺序输出操作序列，每行输出两个整数 $i,j$，$i$ 表示要被替换的元素下标，$j$ 表示参与替换的另一个元素下标。

样例 1

input

5 1
3 2 8 4 1

output

3
1 2
4 3
5 4

$$ [3, 2, 8, 4, 1] \to [\mathbf{1}, 2, 8, 4, 1] \to [1, 2, 8, \mathbf{12}, 1] \to [1, 2, 8, 12, \mathbf{13}] $$

样例 2

input

5 2
4 4 2 0 1

output

3
3 2
4 3
5 4

$$ [4, 4, 2, 0, 1] \to [4, 4, \mathbf{6}, 0, 1] \to [4, 4, 6, \mathbf{6}, 1] \to [4, 4, 6, 6, \mathbf{7}] $$

数据范围与提示

对于所有数据，$1\le S\le 2,2\le N\le 1000,0\le A_i<2^{20}$。

详细子任务附加限制及分值如下表：

当进行异或操作时，设 $a,b$ 分别为一个比特位，当 $a=b$ 时结果为 $1$，否则为 $0$。

当对整数 $a,b$ 进行异或操作时，仅对对应比特位进行异或操作。

$$ \begin{align} 75 & \oplus 29 \ \ \ \ \ \ \ \ \ \ = 86 \ 1001011 & \oplus 0011101 = 1010110 \end{align} $$

在 C / C++ / Java 语言中，可以用 ^ 运算符进行异或运算。