ALIBABA

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 i^{th} 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.
Input
 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.
Output
 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).
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 2000
 2 ≤ M ≤ 500
 1 ≤ Q < M
 1 ≤ A[i] ≤ 1000000000
Example
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
Note:
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)
Author:  incognito_14 
Tags  incognito_14 
Date Added:  2102015 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 