你在处理数组时遇到了另一个问题。让我们考虑一个包含 n 个(不一定不同)整数 a1, a2, ..., an 的任意序列。我们对所有可能的数字对 (ai, aj)、(1 ≤ i, j ≤ n) 感兴趣。换句话说,让我们考虑从给定数组中选取的所有 n2 对数字。
例如,序列 a = {3, 1, 5} 中有 9 对数字:(3, 3), (3, 1), (3, 5), (1, 3), (1, 1), (1, 5), (5, 3), (5, 1), (5, 5)。
让我们按非递减字典顺序对所有结果对进行排序。让我们提醒您,仅当 p1 < p2 或 p1 = p2 且 q1 < q2 时,对 (p1, q1) 按字典顺序小于对 (p2, q2)。
那么上面提到的序列将被排序为: (1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5)
让我们对排序列表中的所有对进行编号,从 1 到 n2。您的任务是这样表述的:您应该在给定的数组的所有可能对的有序列表中找到第 k 对。
输入
第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 1 ≤ k ≤ n2)。第二行包含包含 n 个整数 a1, a2, ..., an (- 109 ≤ ai ≤ 109) 的数组。数组中的数字可以重合。所有数字均以空格分隔。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout、streams 或 %I64d 指定符来代替。
输出
在单行中打印两个数字 - 所寻找的第 k 对。
示例
输入 #1
2 4 2 1
输出 #1
2 2
输入 #2
3 2 3 1 5
输出 #2
1 3
注意
在第一个示例中,给定数组的排序序列如下:(1, 1), (1, 2), (2, 1), (2, 2)。其中第四个是 (2, 2) 对。
语句中给出了第二个样本中数组的排序序列。第二对是 (1, 3)。