题目描述

给定一个长为 $N$ 的序列 $A_i$，你可以进行如下操作：

选定一个位置 $i$，将 $A_i$ 修改为 $A_i \oplus A_{i+1}$ 或 $A_i \oplus A_{i-1}$。

你想知道，需要用多少次操作才能把 $A_i$ 变为：

• $S=1$，严格单调递增序列，即 $A_i<A_{i+1}$。
• $S=2$，非严格单调递增序列，即 $A_i \le A_{i+1}$。

输入格式

第一行两个整数 $N,S$，代表序列长度以及测试点类型。
第二行 $N$ 个整数 $A_i$ 代表这个序列。

输出格式

第一行一个整数 $K$ 代表操作次数，你不需要使得 $K$ 最小，你只需要满足 $0 \le K \le 4 \times 10^4$。
接下来 $K$ 行每行两个整数 $i,j$ 代表要把 $A_i$ 修改为 $A_i \oplus A_j$，其中 $j=i+1$ 或 $i-1$。

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 解释

$$[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 解释

$$[4, 4, 2, 0, 1] \to [4, 4, \mathbf6, 0, 1] \to [4, 4, 6, \mathbf6, 1] \to [4, 4, 6, 6, \mathbf7] $$

数据规模与约定

本题采用捆绑测试。

• Subtask 1（25 pts）：$2 \le N \le 150$，$S=1$，$A_i$ 互不相同。
• Subtask 2（35 pts）：$2 \le N \le 200$，$S=1$，$A_i$ 互不相同。
• Subtask 3（40 pts）：$2 \le N \le 1000$，$S=2$。

对于 $100\%$ 的数据：

• $1 \le S \le 2$。
• $2 \le N \le 1000$。
• $0 \le A_i<2^{20}$。

本题使用 Special Judge。

说明

翻译自 eJOI 2020 Day2 A XOR Sort。