All submissions for this problem are available.
Alibaba finds a secret den in the jungle. He exclaims "Khulja SimSim!" and the magical den lets him in. He sees N stacks of gold coins each numbered from 1 to N lined up infront of him. The ith stack contains A[i] number of gold coins. There are M horses standing on one side of the den and a temple of Mahashweta devi on the other side. He has to select a subset amongst the stacks of gold coins in such a way that they form an increasing sequence. If A[i] and A[j] are two stacks selected and i<j then A[i]<A[j]. The horses will carry the coins for him but each of them have to be given an equal number of coins to carry. Moreover the magical den will only let him out if he offers Q coins to Mahashweta devi. Help Alibaba select the proper set of stacks.
- The first line of the input contains an integer T denoting the number of test cases. T test cases follows.
- The first line of each test case contains three integers N, M and Q.
- The second line of each test case consists of N integers denoting the number of coins in each stack.
- For each test case print in a single line the list of stacks Alibaba should choose to get out of the den.
- If multiple lists are possible print the one which comes lexicographically first.
- If there is no possible way, print "-1"(without quotes).
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 2000
- 2 ≤ M ≤ 500
- 1 ≤ Q < M
- 1 ≤ A[i] ≤ 1000000000
Input: 5 5 7 2 4 3 5 20 16 4 5 1 4 6 2 10 5 8 2 12 3 6 3 4 5 9 6 1 2 3 4 5 5 9 6 5 4 3 2 1 Output: 3 20 6 -1 1 2 3 -1
Alibaba is not greedy, he doesnot care how many coins he takes with him. Lexicographically: (2,4) comes before (3,5,7) (3,5) comes before (3,5,8)
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.