E. I Wanna Know...
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

With the week zooming by, Warith is really feeling the feels thinking about February 14th coming up soon. Valentine's Day is just around the corner, and coincidentally the general onsale for TWICE's stop in Austin is very soon! Love is in the air (although he still wonders what that is), so he needs to lock in on getting concert tickets for him and his Valentine.

They decide to agree that among all possible pairs of tickets $$$(i,j)$$$, where $$$i \lt j$$$, they will pick the one with the $$$k$$$th-smallest price difference. However, Warith wants to save money for gifts. If multiple pairs of tickets have a difference equal to the $$$k$$$th-smallest, he will tiebreak in the following order:

  • Smallest total sum $$$p_i + p_j$$$
  • Smallest index $$$i$$$
  • Smallest index $$$j$$$

Warith is convinced that these tickets are the one spark to elevate his relationship, so can you help Warith get his tickets and bag his queen of hearts?

Input

The first line will contain two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le \frac{n(n-1)}{2}$$$), the number of tickets and the index of the price difference Warith desires.

The second line will contain the array $$$p$$$ of $$$n$$$ space-separated integers, where $$$p_i$$$ ($$$1 \le p_i \le 10^9$$$) denotes the price of the $$$i$$$th ticket.

Output

Output two integers $$$i$$$ and $$$j$$$ ($$$1 \le i \lt j \le n$$$), denoting two indices of the original list such that $$$|p_j-p_i|$$$ is the $$$k$$$-th smallest difference. Due to the tiebreaking system, there will be a unique solution.

Example
Input
4 4
1 2 3 2
Output
1 2
Note

In the sample test case, the differences (sorted) are $$$[0, 1, 1, 1, 1, 2]$$$. The $$$4$$$th smallest difference is $$$1$$$, and four pairs satisfy this. The below table sorts them using the tiebreaking system listed above:

$$$p_i + p_j$$$$$$i$$$$$$j$$$
$$$3$$$$$$1$$$$$$2$$$
$$$3$$$$$$1$$$$$$4$$$
$$$5$$$$$$2$$$$$$3$$$
$$$5$$$$$$3$$$$$$4$$$

$$$^\dagger$$$ Fun fact: Excluding the title of the problem itself, there are as many tickets in the sample test case as there are TWICE song references in the problem statement!