Pair that fits a budget

Problem

Given n prices and a budget, find two positions i < j with price[i] + price[j] = budget. Choose the pair with the smallest j, and for that j the smallest i. Print i j, or none when there is no pair.

Input, output and limits

Input: The first line has n and the budget. The second line has n integers.
Output: Two indexes separated by a space, or none.
Constraints: 2 ≤ n ≤ 100000
-10^9 ≤ each price ≤ 10^9
-2·10^9 ≤ budget ≤ 2·10^9

Examples

Example

Input

5 17
3 8 12 5 9

Output

2 3

The pair 12 and 5 is completed first, at j = 3.

Hints

Try the problem first. Open one hint at a time.

Hint 1

For each price, look up budget - price among the earlier prices.

Hint 2

Store the first index of each price, and look up before storing.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

First repeated ideasy
Balance pointeasy
Repeated order ideasy
Same letterseasy
Running balanceeasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sums & Hashing problems

Problem

Input, output and limits

Examples

Hints

More Prefix Sums & Hashing problems