Palindromic Yarn Patches

Time limit: 3000 msMemory limit: 256 MB

Gats has a yarn whose colors are represented by a string $S$ of length $N$ . Each character represents the color of one consecutive position on the yarn.

A string $T$ of length $M$ is palindromic if

T_i = T_{M-i+1}

for every $i$ satisfying $1 \le i \le M$ .

Gats considers $Q$ independent queries. A query gives three integers $L$ , $R$ , and $K$ . For that query, Gats selects the substring

S_L S_{L+1} \ldots S_R.

In one repaint operation, Gats may choose one position of the selected substring and change its character to any lowercase English letter. Determine whether the selected substring can be made palindromic using at most $K$ repaint operations.

All queries are independent, and repaint operations considered for one query do not change $S$ for any other query.

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N \le 2 \times 10^5$ , ), the length of the yarn and the number of queries.

Output

For each query, print YES if the selected substring can be made palindromic using at most $K$ repaint operations. Otherwise, print NO.

The answer may be printed using any combination of uppercase and lowercase letters.

Samples

Sample 1

Input

Output

YES
NO
YES
YES
YES
NO

The six selected substrings require minimum repaint counts of $0$ , $3$ , $3$ , $2$ , $0$ , and $1$ , respectively. Comparing these values with the corresponding repaint limits gives the displayed answers.

Palindromic Yarn Patches

Input

Output

Samples

Sample 1

Submit

Submissions