CF985F.Isomorphic Strings

You are given a string s of length n consisting of lowercase English letters.

For two given strings s and t, say S is the set of distinct characters of s and T is the set of distinct characters of t. The strings s and t are isomorphic if their lengths are equal and there is a one-to-one mapping (bijection) f between S and T for which f(s__i) = t__i. Formally:

1. f(s__i) = t__i for any index i,
2. for any character there is exactly one character that f(x) = y,
3. for any character there is exactly one character that f(x) = y.

For example, the strings "aababc" and "bbcbcz" are isomorphic. Also the strings "aaaww" and "wwwaa" are isomorphic. The following pairs of strings are not isomorphic: "aab" and "bbb", "test" and "best".

You have to handle m queries characterized by three integers x, y, len (1 ≤ x, y ≤ n - len + 1). For each query check if two substrings s[x... x + len - 1] and s[y... y + len - 1] are isomorphic.

给你一个长度为 $ n $ 的字符串 $ s $，其中仅包含小写英文字母。

对于给定的两个字符串 $ s $ 和 $ t $，设 $ S $ 为 $ s $ 中所有不同字符构成的集合，$ T $ 为 $ t $ 中所有不同字符构成的集合。若 $ s $ 与 $ t $ 长度相等，且存在一个从 $ S $ 到 $ T $ 的一一映射（双射）$ f $，使得对任意下标 $ i $ 均有 $ f(s_i) = t_i $，则称 $ s $ 与 $ t $ 是同构的。形式化定义如下：

1. 对任意下标 $ i $，均有 $ f(s_i) = t_i $；
2. 对任意字符 $ x \in S $，恰存在唯一一个字符 $ y \in T $，使得 $ f(x) = y $；
3. 对任意字符 $ y \in T $，恰存在唯一一个字符 $ x \in S $，使得 $ f(x) = y $。

例如，字符串 "aababc" 与 "bbcbcz" 是同构的；字符串 "aaaww" 与 "wwwaa" 也是同构的。而以下字符串对则不是同构的："aab" 与 "bbb"、"test" 与 "best"。

你需要处理 $ m $ 个查询，每个查询由三个整数 $ x $、$ y $、$ \text{len} $ 描述（满足 $ 1 \le x, y \le n - \text{len} + 1 $）。对每个查询，请判断两个子串 $ s[x\ldots x + \text{len} - 1] $ 和 $ s[y\ldots y + \text{len} - 1] $ 是否同构。

The first line contains two space-separated integers n and m (1 ≤ n ≤ 2·105, 1 ≤ m ≤ 2·105) — the length of the string s and the number of queries.

The second line contains string s consisting of n lowercase English letters.

The following m lines contain a single query on each line: x__i, y__i and len__i (1 ≤ x__i, y__i ≤ n, 1 ≤ len__i ≤ n - max(x__i, y__i) + 1) — the description of the pair of the substrings to check.

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \leq n \leq 2\cdot10^5$，$1 \leq m \leq 2\cdot10^5$）—— 分别表示字符串 $s$ 的长度和查询次数。

第二行包含一个由 $n$ 个小写英文字母组成的字符串 $s$。

接下来的 $m$ 行每行包含一个查询：$x_i$、$y_i$ 和 $len_i$（$1 \leq x_i,\,y_i \leq n$，$1 \leq len_i \leq n - \max(x_i,\,y_i) + 1$）—— 描述待检查的一对子字符串。

For each query in a separate line print "YES" if substrings s[x__i... x__i + len__i - 1] and s[y__i... y__i + len__i - 1] are isomorphic and "NO" otherwise.

对于每个查询，在单独的一行中输出 "YES"，如果子串 $s[x_i...x_i+\text{len}_i-1]$ 和 $s[y_i...y_i+\text{len}_i-1]$ 是同构的；否则输出 "NO"。

The queries in the example are following:

1. substrings "a" and "a" are isomorphic: f(a) = a;
2. substrings "ab" and "ca" are isomorphic: f(a) = c, f(b) = a;
3. substrings "bac" and "aba" are not isomorphic since f(b) and f(c) must be equal to a at same time;
4. substrings "bac" and "cab" are isomorphic: f(b) = c, f(a) = a, f(c) = b.

示例中的查询如下：

1. 子串 “a” 和 “a” 是同构的：$f(a) = a$；
2. 子串 “ab” 和 “ca” 是同构的：$f(a) = c$，$f(b) = a$；
3. 子串 “bac” 和 “aba” 不是同构的，因为 $f(b)$ 和 $f(c)$ 必须同时等于 $a$；
4. 子串 “bac” 和 “cab” 是同构的：$f(b) = c$，$f(a) = a$，$f(c) = b$。