题目描述

本题译自 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$ 表示参与替换的另一个元素下标。

---

样例 1

输入

5 1
3 2 8 4 1

输出

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

输入

5 2
4 4 2 0 1

输出

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}$

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

子任务编号	附加任务	分值
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 \neq b$ 时结果为 $1$，否则为 $0$。

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

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

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