Hash Map Counting / Lookup Problem

Problem: Hash Table Pair Search (Two Sum Variant)

You are given an integer array nums along with an integer target. Identify two different positions in the array such that their corresponding values add up to target.

Output the pair of zero-indexed positions. When more than one valid pair is available, any one may be returned. If no such pair can be found, output -1 -1.

Input

• First line: an integer n
• Second line: n integer values nums[i]
• Third line: an integer target

Output

• Two positions i j where i != j, or -1 -1

Constraints

• 2 <= n <= 2 * 10^5
• -1e9 <= nums[i], target <= 1e9

Example

Input:

4
3 8 12 6
14

Output:

1 3

Explanation: nums[1] is 8 and nums[3] is 6, and together they equal 14.

Example

Input:
4
5 9 2 13
11

Output: 1 2

Explanation: The values at indices 1 and 2 are 9 and 2, whose sum is 11.