← 返回题目列表

Codeforces · 160/C

C. 查找配对

中文机器翻译题面 查看原题

你在处理数组时遇到了另一个问题。让我们考虑一个包含 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)。