K-Palindrome Queries

You are given a string \(s\) and several queries. In each query, you are provided with three integers \(l\), \(r\), and \(k\). The substring \(s[l...r]\) (note: indices are 1-indexed) is considered. The task is to determine whether it is possible to convert this substring into a palindrome by changing at most \(k\) characters.

A palindrome is a string that reads the same backward as forward. Formally, for a given substring \(s[l...r]\) with length \(n\), let \(c(i)\) be the \(i^{th}\) character. The substring is a palindrome if \(c(i) = c(n-i+1)\) for all valid \(i\). However, you are allowed to change at most \(k\) characters to achieve this.

Your goal is to output "YES" if the substring can be transformed into a palindrome under the given constraint and "NO" otherwise.

inputFormat

The input is given through standard input in the following format:

T
n q
s
l1 r1 k1
l2 r2 k2
... (q lines of queries)
... (repeat the above block T times)

Where:

• T is the number of test groups.
• For each test group:
  • n is the length of the string \(s\).
  • q is the number of queries.
  • s is the string.
  • Each of the following \(q\) lines contains three integers \(l\), \(r\), and \(k\), representing the substring indices (1-indexed) and the maximum number of allowed changes.

outputFormat

For each query, print a line containing "YES" if the substring \(s[l...r]\) can be transformed into a palindrome by changing at most \(k\) characters, otherwise print "NO".

## sample

1
8 2
abcaacbd
1 4 1
3 8 2

YES
NO

</p>