题目描述

本题译自 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$，有 $A_i<A_{i+1}$；
• 若 $S=2$，则最后的序列必须单调不减，即对于 $1\le i<N$，有 $A_i\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$ 表示参与替换的另一个元素下标。

5 1
3 2 8 4 1

3
1 2
4 3
5 4

5 2
4 4 2 0 1

3
3 2
4 3
5 4

数据范围与提示

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

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

子任务编号	附加任务	分值
$1$	$2\le N\le 150,\ S=1$，保证 $A$ 中元素互不相同	$25$
$2$	$2\le N\le 200,\ S=1$，保证 $A$ 中元素互不相同	$35$
$3$	$2\le N\le 1000,\ S=2$	$40$

---

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

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

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

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