Fortunately, he found an array a of size n lying around. The array contains positive integers. Chef’s friend likes even numbers very much. So for the gift, chef will choose a consecutive non-empty segment of the array. The segment should contain exactly k even integers. Though it can have any number of odd integers.
He will then pick that segment and gift it to his friend.
But there is a problem. It might not be always possible for the chef to choose such a segment. Please tell whether it is possible for chef to select some gift or not?
Input
First line of the input contains a single integer T denoting number of test cases.
For each test case, first line contains two space separated integers n, k.
Next line contains n space separated integers denoting content of array a.
It is also guaranteed that all the numbers in the array a are distinct.
Output
For each test case, print a single line containing “YES” or “NO” (without quotes) corresponding to the situation.
Constraints
1 ≤ T ≤ 10
1 ≤ n ≤ 50
0 ≤ k ≤ n
1 ≤ a i ≤ 100
Example
Input:
4
2 1
1 2
3 2
2 6 5
3 3
2 4 5
4 2
1 2 4 5
Output:
YES
YES
NO
YES
Explanation
For first test case, we can select a[2, 2] = {2}.
For second test case, we can select a[1, 2] = {2, 6}.
For third test case, we can not select any consecutive segment having exactly 3 even numbers.
For fourth test case, we can select a[2, 3] = {2, 4}.
Thanks to Dhaval for suggesting this approach and Article
Code :
#include <stdio.h>
#define gc getchar_unlocked
#define pc putchar_unlocked
inline int scan(){register int n=0,c=gc();while(c<‘0’||c>’9’)c=gc();while(c<=’9’&&c>=’0′)n=(n<<1)+(n<<3)+c-‘0’,c=gc();return n;}
int main(void){
int i,t,n,k,x,count=0;
t=scan();
while(t–){
n=scan();
k=scan();
while(n–){
x=scan();
if(x%2==0) count++;
}//while
if (count >= k) printf(“nYES“);
else printf(“nNO“);
count=0;
}//while
return 0;
}
//STDIN Input : 4 2 1 1 2 3 2 2 6 5 3 3 2 4 5 4 2 1 2 4 5
You can find Working code at http://ideone.com/pIhXeL