This is a normal programming problem, a deterministic solution exists
You are given an array A of size N. Now, you may know of the LIS problem already. Today, you need to solve a modified version of this problem.
Given the array, you need to find the length of the longest increasing submask subsequence of this array, and also find any such subsequence. We call an increasing subsequence a submask subsequence, if :
Let the elements picked be A[k1],A[k2],A[k3]...A[kx],k1<k2<k3...<kx then A[ki]&A[ki−1]=A[ki−1] for all 2≤k≤x
Here , "&" denotes the BITWISE AND operation. You need to maximize x obeying the above constraints.
Input Format:
The first line contains a single integer T denoting the number of test cases. The description of each test case follows over 2 lines. The first line contains a single integer N denoting the size of the given array A , and the next line contains N space seprated integers denoting the elements of the given array.
Output Format:
For each test case, print the answer over 2 lines. On the first line, print a single integer k denoting the length of the subsequence. On the next line, print k space separated integers, where the ith integer denotes the index of the ith picked element of the subsequence. In the case of multiple answers, print any solution
Constraints:
1≤T≤2
1≤N≤100,000
0≤A[i]<216
The elements 1,7 comprise of the required subsequence.