第k个最大递增子序列
某个整数序列中,去掉0个以上的数字后,剩余的部分就是原序列的子序列。例如,{7,4,9}、{10,4}、{10,9}等是{10,7,4,9}的子序列。而序列{10, 4, 7}具有不同于原序列的排列顺序,因而不属于{10,7,4,9}的子序列。严格递增的子序列称为递增子序列。序列的递增子序列中,最长的序列称为最大递增子序列(LIS)。例如:{5,20,21,22,8,9,10}的最大递增子序列是{5,8,9,10}。(不唯一)
给出以不同数字组成(无重复数字)的序列时,请编写程序,计算此序列的LIS中按照字典序排在第k个位置的LIS。
输入
第一行输入测试用例的个数C(C<=50)。各测试用例的第一行输入序列中元素的个数n(1<=n<=500)和k(1<=k<=2*109)。第二行输入序列的n个元素。各元素是大于等于1而小于等于100,000的整数,且同一数字只出现1次。
可以假设序列的LIS至少有k个。
输出
每个测试用例在第一行输出LIS的长度l,第二行以l个整数输出第k个LIS。
示例输入:
3
8 6
5 1 6 4 3 2 8 7
8 4
2 1 4 3 6 5 8 7
8 2
5 6 7 8 1 2 3 4
示例输出:
3
1 4 8
4
1 3 6 8
4
5 6 7 8