MICAPOKALEBE

Problem code: INS0904

Our friend Hannibal from NITK Surathkal was one of the k participants in the elite tournament Micapokalebe. The rules of the game to decide the ranking of the players for the tournament are as follows. There are n stacks of coins. The ith stack has x(i) coins. Each player gets to choose any one stack and pick any available number of coins greater than zero from that stack. The player who is unable to pick any coin from any stack during his move is the last(worst) ranked player. The players following him in order by turn will be considered second last ranked player, third last ranked player etc. Hannibal is asked to play first. Hannibal decides that he will not protest unless his tournament rank is bound to be the worst. Assuming all players in the tournament are rational and want to achieve the best rank possible, your job is to advice Hannibal with a simple "Yes" or "No" answer asking to protest or not to protest respectively given a configuration of the stacks.

Input

The first line give t, the number of test cases (t 250), Then t test cases follow.
For each test case:
The first line gives 2 integers n k, denoting the number of stacks and number of participants respectively.
The next line gives n integers x(1) x(2) x(3) .... x(n) denoting the number of coins in each stack.
(1 k n 105)
(1 x(i) 109)

Output:

For each test case output a single line.
"Yes" if he has to protest , "No" if he shouldn't

Example

Input:
2
5 4
6 4 2 1 2
5 2
5 6 3 1 6

Output:
No
Yes

Author: fctrl
Date Added: 14-10-2009
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

the time limit for this

INSCRIPTION09 @ 25 Oct 2009 03:22 PM

the time limit for this problem is 2 s

The sample test cases has

INSCRIPTION09 @ 25 Oct 2009 03:28 PM

The sample test cases has been modified..

 

Input:
2
5 4
6 4 2 1 2
5 3
5 6 3 1 6

Output:
No
Yes

Sorry for the inconvenience.

INSCRIPTION09 @ 25 Oct 2009 03:29 PM

Sorry for the inconvenience.

constraints  updated :  (1 <=

INSCRIPTION09 @ 25 Oct 2009 04:12 PM

constraints  updated :  (1 <= k <= n <=10^6 )

so, what was the logic for

imrankane2005 @ 25 Oct 2009 07:30 PM

so, what was the logic for this question ?

@Imran   The solution works

kyun @ 26 Oct 2009 12:20 PM

@Imran

 

The solution works similar to standard Nim. You express all the numbers in based 2, just as in standard Nim, and then add all the bits in all the columns (without carry) mod k. In standard Nim, this is equivalent to an XOR. There's a paper on the subject, if you can get access to Springerlink. You can prove it by induction of course.

 

Link to paper: http://www.springerlink.com/content/j2172k702v735747/

 

Hope that helps

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions