Background

Note: Using submission feedback to extract data is cheating.

Even if the world is about to collapse
Darling, I will never shed a tear
I will not give up that feeling of having loved
Cherishing everything that holds memories of you
Even if the world is about to tilt
Darling, I will never say goodbye
Even if the doomsday threat is even stronger
With love, it is not tiring
—— “The World Has Not Yet Ended”

Problem Description

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

They agree to take turns starting from Vinsta. In each move, they may choose at least $1$ pile and at most $k$ piles of stones to operate on. For the $i$-th pile, they may choose two real numbers $a, b$ satisfying:

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

Then they discard $c$ stones from the $i$-th pile, i.e. set $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 three positive integers $n, k, S$, where $S = \max\{s_i\}$.

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

Output Format

Output one line. If there is a winning strategy, output YES; otherwise output NO.

7 1 13
2 3 4 5 7 10 11

YES

8 1 13
2 3 4 5 7 10 11 13

NO

7 2 100
19 26 8 17 11 45 14

YES

Hint

Constraints

This problem uses bundled testdata.

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

Translated by ChatGPT 5