Description

Given an array of integers nums and an integer target, find the indices of the two numbers such that they add up to the target.

Input

The first line contains an integer t, representing the number of test cases. For each test case:

• The first line contains an integer, representing the target.

• The second line contains an integer n, indicating the size of the array.

• The third line contains n space-separated integers, representing the elements of the array.

Constraints:

• 1 <= t <= 1000

• 0 <= target <= 2147483647

• 2 <= n <= 2500

• 0 <= nums[i] <= 1000000000

Output

For each test case:

• Output two space-separated integers representing the distinct indices (0-indexed) of the two numbers that add up to the target. The smaller index must be printed first.

• If no such pair exists, output "None".

• It is guaranteed that there is at most one solution per test case.

Note: Remember to print '\n' at the end of the output.

Hint: Use std::map from the STL to achieve an O(nlogn) time complexity.

Sample Input  Download

Sample Output  Download

Discuss