Odd Sum Segments（CF-1196B）

Problem Description

You are given an array aa consisting of nn integers a1,a2,…,an. You want to split it into exactly kk non-empty non-intersecting subsegments such that each subsegment has odd sum (i. e. for each subsegment, the sum of all elements that belong to this subsegment is odd). It is impossible to rearrange (shuffle) the elements of a given array. Each of the nn elements of the array aa must belong to exactly one of the kksubsegments.

Let's see some examples of dividing the array of length 55 into 33 subsegments (not necessarily with odd sums): [1,2,3,4,5] is the initial array, then all possible ways to divide it into 33 non-empty non-intersecting subsegments are described below:

• [1],[2],[3,4,5];
• [1],[2,3],[4,5];
• [1],[2,3,4],[5];
• [1,2],[3],[4,5];
• [1,2],[3,4],[5];
• [1,2,3],[4],[5].

Of course, it can be impossible to divide the initial array into exactly kksubsegments in such a way that each of them will have odd sum of elements. In this case print "NO". Otherwise, print "YES" and any possible division of the array. See the output format for the detailed explanation.

You have to answer qq independent queries.

Input

The first line contains one integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of queries. Then qq queries follow.

The first line of the query contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — the number of elements in the array and the number of subsegments, respectively.

The second line of the query contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is the ii-th element of aa.

It is guaranteed that the sum of nn over all queries does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105).

Output

For each query, print the answer to it. If it is impossible to divide the initial array into exactly kk subsegments in such a way that each of them will have odd sum of elements, print "NO" in the first line. Otherwise, print "YES" in the first line and any possible division of the array in the second line. The division can be represented as kk integers r1, r2, ..., rk such that 1≤r1<r2<⋯<rk=n, where rjrj is the right border of the jj-th segment (the index of the last element that belongs to the jj-th segment), so the array is divided into subsegments [1;r1],[r1+1;r2],[r2+1,r3],…,[rk−1+1,n]. Note that rk is always n but you should print it anyway.

Examples

Input

3
5 3
7 18 3 14 1
5 4
1 2 3 4 5
6 2
1 2 8 4 10 2

Output

YES
1 3 5
NO
NO

题意：q 组询问，每组给出 n 个数，以及一个 k，现在要将这 n 个数划分成 k 组，使得每组的和都是奇数，若能成功划分，输出 YES 以及任意一种划分方案，若不能成功划分输出 NO

思路：

偶数个奇数的和是偶数，奇数个奇数的和是奇数，任意个偶数的和是偶数，一个奇数与一个偶数的和，因此，要划分为 k 组后使得每组和为奇数，需要从 n 个数中奇数的个数入手

假设 n 个数中存在 sum 个奇数，那么有 sum-(k-1) 个奇数是可以直接划分成一个组，此时划分了 k-1 个组，还需划分 1 个组

这个时候，根据上面的结论，去判断剩下的奇数个数是偶数还是奇数：

• 如果是奇数个，说明他们的和为奇数，此时无论加上多少个偶数，结果为奇数，划分成功
• 如果是偶数个，说明他们的和为偶数，此时无论加上多少个偶数，结果为偶数，划分失败

因此，我们只需要统计 n 个数中奇数的个数，然后对 sum-(k-1) 进行 %2 判断，即可得知是否能划分成功

如果能划分成功，那么需要输出任意一组方案，只需要对 n 个数从前向后扫一遍，将 i 个数进行求和，如果和为奇数直接输出当前位置，然后重新求和继续划分，直到划分出 k 个区间

Source Program

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 500000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
 
LL a[N];
int main() {
    int q;
    scanf("%d",&q);
    while(q--) {
        LL n,k;
        scanf("%lld%lld",&n,&k);
 
        LL sum=0;
        for(int i=1; i<=n; i++) {
            scanf("%lld",&a[i]);
            if(a[i]%2)
                sum++;
        }
 
        if(sum<k)
            printf("NO\n");
        else{
            if( (sum-(k+1))%2==0 )
                printf("NO\n");
            else{
                printf("YES\n");
                if(k>1){
                    int cnt=0;
                    LL sum=0;
                    for(int i=1;i<=n;i++){
                        sum+=a[i];
                        if(sum%2==1){
                            cnt++;
                            printf("%d ",i);
                            sum=0;
                        }
                        if(cnt>=k-1)
                            break;
                    }
                }
                printf("%d\n",n);
            }
        }
    }
    return 0;
}