Problem Background

Note: Using submission feedback to obtain data is considered cheating.

Even if the world is crumbling
Dear, I will never shed a tear
I won't give up on the feeling of love
Cherishing all the memories with you
Even if the world tilts
Dear, I will never say goodbye
Despite the strong threats of the apocalypse
With love, I am not tired
— "The World is Not Ending"

Problem Description

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

They agree to take turns starting with Vinsta. Each turn, a player can choose between $1$ and $k$ piles of stones. For the $i$-th pile, they can select two real numbers $a$ and $b$ that satisfy:

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

and remove $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 if Vinsta has a guaranteed 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$, representing the initial number of stones in the $i$-th pile.

Output Format

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

Sample Input and Output

Sample Input #1

7 1 13
2 3 4 5 7 10 11

Sample Output #1

YES

Sample Input #2

8 1 13
2 3 4 5 7 10 11 13

Sample Output #2

NO

Sample Input #3

7 2 100
19 26 8 17 11 45 14

Sample Output #3

YES

Notes

Data Range

This problem uses batched testing.

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

见题面 Input 部分

见题面 Output 部分