{"raw_statement":[{"iden":"statement","content":"You are given a string _s_ of length _n_ consisting of lowercase English letters.\n\nFor 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:\n\n1.  _f_(_s__i_) = _t__i_ for any index _i_,\n2.  for any character there is exactly one character that _f_(_x_) = _y_,\n3.  for any character there is exactly one character that _f_(_x_) = _y_.\n\nFor 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_\".\n\nYou 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."},{"iden":"input","content":"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.\n\nThe second line contains string _s_ consisting of _n_ lowercase English letters.\n\nThe 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."},{"iden":"output","content":"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."},{"iden":"example","content":"Input\n\n7 4\nabacaba\n1 1 1\n1 4 2\n2 1 3\n2 4 3\n\nOutput\n\nYES\nYES\nNO\nYES"},{"iden":"note","content":"The queries in the example are following:\n\n1.  substrings \"_a_\" and \"_a_\" are isomorphic: _f_(_a_) = _a_;\n2.  substrings \"_ab_\" and \"_ca_\" are isomorphic: _f_(_a_) = _c_, _f_(_b_) = _a_;\n3.  substrings \"_bac_\" and \"_aba_\" are not isomorphic since _f_(_b_) and _f_(_c_) must be equal to _a_ at same time;\n4.  substrings \"_bac_\" and \"_cab_\" are isomorphic: _f_(_b_) = _c_, _f_(_a_) = _a_, _f_(_c_) = _b_."}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"你被给定一个长度为 #cf_span[n] 的字符串 #cf_span[s]，由小写英文字母组成。\\n\\n对于两个给定的字符串 #cf_span[s] 和 #cf_span[t]，设 #cf_span[S] 是 #cf_span[s] 的不同字符的集合，#cf_span[T] 是 #cf_span[t] 的不同字符的集合。如果两个字符串长度相等，并且存在一个从 #cf_span[S] 到 #cf_span[T] 的一一映射（双射）#cf_span[f]，使得 #cf_span[f(si) = ti]，则称这两个字符串是 _同构的_。形式化地：\\n\\n例如，字符串 \\\"_aababc_\\\" 和 \\\"_bbcbcz_\\\" 是同构的。字符串 \\\"_aaaww_\\\" 和 \\\"_wwwaa_\\\" 也是同构的。以下字符串对不是同构的：\\\"_aab_\\\" 和 \\\"_bbb_\\\"，\\\"_test_\\\" 和 \\\"_best_\\\"。\\n\\n你需要处理 #cf_span[m] 个查询，每个查询由三个整数 #cf_span[x, y, len]（#cf_span[1 ≤ x, y ≤ n - len + 1]）描述。对于每个查询，检查两个子串 #cf_span[s[x... x + len - 1]] 和 #cf_span[s[y... y + len - 1]] 是否同构。\\n\\n第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 2·105], #cf_span[1 ≤ m ≤ 2·105]）——字符串 #cf_span[s] 的长度和查询数量。\\n\\n第二行包含一个由 #cf_span[n] 个小写英文字母组成的字符串 #cf_span[s]。\\n\\n接下来的 #cf_span[m] 行，每行包含一个查询：#cf_span[xi], #cf_span[yi] 和 #cf_span[leni]（#cf_span[1 ≤ xi, yi ≤ n], #cf_span[1 ≤ leni ≤ n - max(xi, yi) + 1]）——描述需要检查的两个子串。\\n\\n对于每个查询，在单独一行中输出 \\\"_YES_\\\" 如果子串 #cf_span[s[xi... xi + leni - 1]] 和 #cf_span[s[yi... yi + leni - 1]] 同构，否则输出 \\\"_NO_\\\"。\\n\\n示例中的查询如下：\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 2·105], #cf_span[1 ≤ m ≤ 2·105]）——字符串 #cf_span[s] 的长度和查询数量。第二行包含一个由 #cf_span[n] 个小写英文字母组成的字符串 #cf_span[s]。接下来的 #cf_span[m] 行，每行包含一个查询：#cf_span[xi], #cf_span[yi] 和 #cf_span[leni]（#cf_span[1 ≤ xi, yi ≤ n], #cf_span[1 ≤ leni ≤ n - max(xi, yi) + 1]）——描述需要检查的两个子串。\"},{\"iden\":\"output\",\"content\":\"对于每个查询，在单独一行中输出 \\\"_YES_\\\" 如果子串 #cf_span[s[xi... xi + leni - 1]] 和 #cf_span[s[yi... yi + leni - 1]] 同构，否则输出 \\\"_NO_\\\"。\"},{\"iden\":\"note\",\"content\":\"示例中的查询如下：\\n子串 \\\"_a_\\\" 和 \\\"_a_\\\" 是同构的：#cf_span[f(a) = a]；\\n子串 \\\"_ab_\\\" 和 \\\"_ca_\\\" 是同构的：#cf_span[f(a) = c], #cf_span[f(b) = a]；\\n子串 \\\"_bac_\\\" 和 \\\"_aba_\\\" 不是同构的，因为 #cf_span[f(b)] 和 #cf_span[f(c)] 必须同时等于 #cf_span[a]；\\n子串 \\\"_bac_\\\" 和 \\\"_cab_\\\" 是同构的：#cf_span[f(b) = c], #cf_span[f(a) = a], #cf_span[f(c) = b]。 \"}]}","sample_group":[],"show_order":[],"formal_statement":"Let $ s $ be a string of length $ n $ over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $.\n\nFor any substring $ s[i..i+\\ell-1] $, define its **character pattern** as the sequence of integers $ p_1, p_2, \\dots, p_\\ell $, where $ p_j $ is the index (starting from 1) of the first occurrence of the character $ s[i+j-1] $ within the substring $ s[i..i+\\ell-1] $.\n\nTwo substrings $ s[x..x+\\ell-1] $ and $ s[y..y+\\ell-1] $ are **isomorphic** if and only if their character patterns are identical.\n\nGiven $ m $ queries, each specified by $ (x, y, \\ell) $, determine whether the character patterns of $ s[x..x+\\ell-1] $ and $ s[y..y+\\ell-1] $ are equal.\n\n**Input:**\n- $ n, m \\in \\mathbb{N} $, $ 1 \\leq n, m \\leq 2 \\cdot 10^5 $\n- String $ s \\in \\Sigma^n $\n- $ m $ triples $ (x_i, y_i, \\ell_i) $, $ 1 \\leq x_i, y_i \\leq n $, $ 1 \\leq \\ell_i \\leq n - \\max(x_i, y_i) + 1 $\n\n**Output:**\nFor each query $ i $, output \"YES\" if $ \\text{pattern}(s[x_i..x_i+\\ell_i-1]) = \\text{pattern}(s[y_i..y_i+\\ell_i-1]) $, otherwise \"NO\".\n\n---\n\n**Formal Definition of Character Pattern:**\n\nFor a substring $ u = s[i..i+\\ell-1] $, define $ f_u : \\{1, \\dots, \\ell\\} \\to \\mathbb{N} $ by:\n\n$$\nf_u(j) = \\min \\{ k \\in \\{1, \\dots, j\\} \\mid u[k] = u[j] \\}\n$$\n\nThen the **pattern** of $ u $ is the sequence $ (f_u(1), f_u(2), \\dots, f_u(\\ell)) $.\n\nTwo substrings are isomorphic iff their patterns are identical.","simple_statement":null,"has_page_source":false}