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