Two Sum

Lab Python Intermediate 20 points

Read a line of integers and a target. Print the indexes i j (i < j) of the first pair (by j) that adds up to the target, or none. Do it in one pass with a dict.

Input

Line 1: integers. Line 2: target.

Output

i j or none.

Example

Input

2 7 11 15
9

Output

0 1

Sample input available Sample output available

Editor

Python

Hints

For each x, ask: have I already seen target - x?

Store value -> index in a dict.

Solution explanation

The dict turns an O(n²) double loop into a single O(n) pass.

Show solution

nums = list(map(int, input().split()))
target = int(input())
seen = {}
for j, x in enumerate(nums):
    if target - x in seen:
        print(seen[target - x], j)
        break
    seen.setdefault(x, j)
else:
    print("none")

Output

Answer