Iahub 希望增强他的多任务处理能力。为了做到这一点,他想要同时对 n 个数组进行排序,每个数组由 m 个整数组成。
Iahub 可以选择一对不同的索引 i 和 j (1 ≤ i, j ≤ m, i ≠ j)。然后,在每个数组中,仅当位置 i 处的值严格大于位置 j 处的值时,才会交换位置 i 和 j 处的值。
Iahub 希望找到一个由不同索引对组成的数组,按顺序选择这些索引,按升序或降序对所有 n 个数组进行排序(特定顺序在输入中给出)。数组的大小最多为 $$\frac{m(m-1)}{2}$$ (最多 $$\frac{m(m-1)}{2}$$ 对)。帮助Iahub,找到任何合适的阵列。
输入
第一行包含三个整数 n (1 ≤ n ≤ 1000)、m (1 ≤ m ≤ 100) 和 k。如果数组必须按升序排序,则整数 k 为 0;如果数组必须按降序排序,则整数 k 为 1。接下来的n行中的每一行i包含m个由空格分隔的整数,代表第i个数组。对于数组 i 的每个元素 x,1 ≤ x ≤ 106 成立。
输出
在输出的第一行打印一个整数 p,即数组的大小(p 最多可以是 $$\frac{m(m-1)}{2}$$)。接下来的 p 行中的每一行都必须包含两个不同的整数 i 和 j (1 ≤ i, j ≤ m, i ≠ j),表示所选索引。
如果有多个正确答案,您可以打印任何一个。
示例
输入 #1
2 5 0 1 3 2 5 4 1 4 3 2 5
输出 #1
3 2 4 2 3 4 5
输入 #2
3 2 1 1 2 2 3 3 4
输出 #2
1 2 1
注意
考虑第一个样本。第一次操作后,数组变为 [1, 3, 2, 5, 4] 和 [1, 2, 3, 4, 5]。第二次操作后,数组变为 [1, 2, 3, 5, 4] 和 [1, 2, 3, 4, 5]。第三次操作后,它们变成 [1, 2, 3, 4, 5] 和 [1, 2, 3, 4, 5]。