AMBM - Ambitious Manager

no tags 

The Bogus Corporation distributes salary to its employees in a weird manner. The salary is distributed every K days,  and instead of same salary for each day, the salary for the ith day is ai. An ambitious young manager, fresh from Institute of Mismanagement, observes that people usually prefer to take leave towards the end of this period of K days, when the workload is higher. Instead of revising each of the ai's, the manager comes up with a quick fix solution - he redefines the new salary on the ith day as bi=ai+2ai-1+22ai-2+23ai-3+........+2i-1a1 . Baba, one of the employees, is in a dire financial crisis, and must accumulate at least N rupees at the end of the forthcoming period. Being a lazy worker that he is, he is interested in finding out if attending particular days would guarantee him exactly  N rupees at the end of the period. Can you help Baba?

Input

First line contains a single integer integer T, the number of test cases ( 1<=T<=100). Each test case is described on two lines. First line contains two integers, N and K ( 1<=N<=263-1, 1<=K<=50) , the second line contains a space separated list of K integers, the ai's ( 1<=ai<=1000).

Output

For each test case, output on a single line 1-based indices of the days (separated by a single space) he should attend to ensure a salary of exactly N rupees at the end of the period. The indices should be printed in the sorted order. In case of multiple answers, output any one of them. If there is no answer, print -1.

Example

Input:
2
9 3
1 1 2
10 2
2 3
Output:
1 3
-1

hide comments
aeon: 2017-01-28 16:57:23

nice question.
just read the output instruction, not the question statement both are contradictory.
question statement: must accumulate at least N rupees at the end of the forthcoming period
output statement: ensure a salary of exactly N rupees at the end of the period

Last edit: 2017-01-28 17:02:35
Akash Garg: 2016-05-27 18:34:11

stare at it till it confesses its solution:P

Anish Kumar: 2015-06-07 20:09:28

All you need is a little Maths :)

P_Quantum: 2013-08-27 22:34:35

Nice prblm.. :)

pushap: 2012-09-22 05:51:42

tricky mathematics!!!

Bharath Reddy: 2012-08-06 03:49:51

Easy problem...

:): 2012-07-23 13:59:52

plz explain 1st case
day 1- 1
day 2- 3
day 4- 4
so total=8<9
shouldnt it be 1?


Added by:Rahul Garg
Date:2007-07-04
Time limit:0.117s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:C-maphore, Tryst 2007