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 個數(shù)，以及一個 k，現(xiàn)在要將這 n 個數(shù)劃分成 k 組，使得每組的和都是奇數(shù)，若能成功劃分，輸出 YES 以及任意一種劃分方案，若不能成功劃分輸出 NO

思路：

偶數(shù)個奇數(shù)的和是偶數(shù)，奇數(shù)個奇數(shù)的和是奇數(shù)，任意個偶數(shù)的和是偶數(shù)，一個奇數(shù)與一個偶數(shù)的和，因此，要劃分為 k 組后使得每組和為奇數(shù)，需要從 n 個數(shù)中奇數(shù)的個數(shù)入手

假設(shè) n 個數(shù)中存在 sum 個奇數(shù)，那么有 sum-(k-1) 個奇數(shù)是可以直接劃分成一個組，此時劃分了 k-1 個組，還需劃分 1 個組

這個時候，根據(jù)上面的結(jié)論，去判斷剩下的奇數(shù)個數(shù)是偶數(shù)還是奇數(shù)：

• 如果是奇數(shù)個，說明他們的和為奇數(shù)，此時無論加上多少個偶數(shù)，結(jié)果為奇數(shù)，劃分成功
• 如果是偶數(shù)個，說明他們的和為偶數(shù)，此時無論加上多少個偶數(shù)，結(jié)果為偶數(shù)，劃分失敗

因此，我們只需要統(tǒng)計 n 個數(shù)中奇數(shù)的個數(shù)，然后對 sum-(k-1) 進(jìn)行 %2 判斷，即可得知是否能劃分成功

如果能劃分成功，那么需要輸出任意一組方案，只需要對 n 個數(shù)從前向后掃一遍，將 i 個數(shù)進(jìn)行求和，如果和為奇數(shù)直接輸出當(dāng)前位置，然后重新求和繼續(xù)劃分，直到劃分出 k 個區(qū)間

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; }

?

總結(jié)

以上是生活随笔為你收集整理的Odd Sum Segments（CF-1196B）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。