Arithmetic Progression Restoration

Vanya has a sequence s of length n, where some elements may be missing (represented by the character ?). He wishes to fill in the missing elements so that some contiguous subsequence of s of length m becomes an arithmetic progression t defined by the formula:

$$t_i = a + i\cdot d,\quad 0 \le i < m,$$

for some integers a and d. In other words, if an index i in the subsequence has a preset number (i.e. not ?), it must satisfy:

$$s_i = a + i\cdot d.$$

Your task is to determine whether there exists at least one contiguous segment of length m in s for which it is possible to substitute the missing values (the ? characters) to form a valid arithmetic progression. If such a segment exists, output YES; otherwise, output NO.

inputFormat

The input is provided via stdin and has the following format:

1. An integer n denoting the length of the sequence s.
2. A single line with n space-separated tokens. Each token is either an integer or the character ?.
3. An integer m denoting the length of the arithmetic progression to be matched.

outputFormat

Output a single line to stdout containing YES if there exists at least one contiguous subsequence of length m in s that can be transformed into an arithmetic progression, or NO if none exists.

7
5 ? 9 6 3 ? 7
3

YES