#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Two Pointers (Pair Sum) - Classic Problems | Repovive

CLS27. Two Pointers (Pair Sum)

1s256 MB

Given a sorted array of $n$ integers in non-decreasing order and a target sum $S$ , find two elements at different positions that add up to $S$ .

Output the two values in increasing order. If no such pair exists, output $-1$ .

If multiple valid pairs exist, output the one with the smallest first value.

Constraints

$2 \le n \le 10^5$
$-10^9 \le a_i \le 10^9$
$-2 \cdot 10^{18} \le S \le 2 \cdot 10^{18}$

Input

\begin{array}{l} n \quad S \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

Output

\begin{cases} a_i \quad a_j & \text{if pair exists} \\ -1 & \text{otherwise} \end{cases}

Samples

Input

5 9
1 2 4 5 7

Explanation

For this input, the required output is 2 7.

Output

2 7

Input

4 10
1 2 3 4

Explanation

For this input, the required output is -1.

Output

-1

Input

6 0
-5 -3 -1 1 3 5

Explanation

For this input, the required output is -5 5.

Output

-5 5

Given a sorted array of $n$ integers in non-decreasing order and a target sum $S$ , find two elements at different positions that add up to $S$ .

Output the two values in increasing order. If no such pair exists, output $-1$ .

If multiple valid pairs exist, output the one with the smallest first value.

$2 \le n \le 10^5$
$-10^9 \le a_i \le 10^9$
$-2 \cdot 10^{18} \le S \le 2 \cdot 10^{18}$

\begin{array}{l} n \quad S \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

\begin{cases} a_i \quad a_j & \text{if pair exists} \\ -1 & \text{otherwise} \end{cases}