Background

Note: Using submission feedback to obtain testdata is cheating.

Even if the world is about to collapse
My dear, I will never shed a tear
I will not give up that feeling of having loved
Cherishing everything that remembers you
Even if the world is about to tilt
My dear, I will never say goodbye
Even if the doomsday threat is stronger than ever
With love, it is not tiring
—— "The World Has Not Ended Yet"

Problem Description

Vinsta and Stella have $n$ piles of stones, and the $i$-th pile has $s_i$ stones.

They agree to take turns starting from Vinsta. In each move, one may choose at least $1$ pile and at most $k$ piles. For the $i$-th pile, one may choose two real numbers $a, b$ such that:

• $a \times b = s_i$
• $a + b = c, c \in [1, s_i] \cap \Z$

Then discard $c$ stones from the $i$-th pile, i.e., $s_i \leftarrow s_i - c$. The player who cannot make a move loses. They want to know whether Vinsta has a winning strategy.

Input Format

The first line contains a positive integer $T$, the number of test cases.

Then follow $T$ test cases. For each test case, the first line contains three positive integers $n, k, S$, where $S = \max\{s_i\}$.

The second line contains $n$ positive integers $s_i$, representing the initial number of stones in the $i$-th pile.

Output Format

For each test case, output one line. If there is a winning strategy, output YES, otherwise output NO.

2
7 1 13
2 3 4 5 7 10 11
8 1 13
2 3 4 5 7 10 11 13

YES
NO

1
7 2 100
19 26 8 17 11 45 14

YES

Hint

For $100\%$ of the testdata, $1 \le T \le 10$, $1 \le k \le n \le 3 \times 10^6$, $1 \le S \le 3 \times 10^{17}$.

Translated by ChatGPT 5