{"problem":{"name":"G. Polycarp and Palindromes","description":{"content":"Polycarp has got the string S, which consists of N small Latin letters. Polycarp is eager to know if the given substrings of the string S are palindromes. A palindrome is a string which is read identi","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10083G"},"statements":[{"statement_type":"Markdown","content":"Polycarp has got the string S, which consists of N small Latin letters. Polycarp is eager to know if the given substrings of the string S are palindromes. A palindrome is a string which is read identically right to left and left to right. But it is not enough for Polycarp: he can change the signs in the string. Polycarp is eager to know if it is possible to know and define very quickly if the substring of the string S is a palindrome if the letters in S can be substituted. Polycarp conducts K operations one after another.\n\nThere is string S in the first line. Its length is N, 1 ≤ N ≤ 100000. S consists of only small Latin letters.\n\nThe second line contains the only integer K, 1 ≤ K ≤ 100000 — the number of operations.\n\nNext K lines contain the descriptions of operations, one in each line. Each line starts with the integer ti, which can take the values 1 and 2. If ti equals 1, two integers li and ri, 1 ≤ li ≤ ri ≤ N follow it. It means — it is necessary to define if the substring slisli + 1... sri is a palindrome. If ti equals 2, it is followed by the integer pi and a small Latin letter ci. It means — to substitute in the string S sign in position pi to ci\n\nOutput \"YES\" in separate lines for each operation of the palindrome definition if the substring is a palindrome, or \"NO\", if it isn’t (without quotations).\n\n## Input\n\nThere is string S in the first line. Its length is N, 1 ≤ N ≤ 100000. S consists of only small Latin letters.The second line contains the only integer K, 1 ≤ K ≤ 100000 — the number of operations.Next K lines contain the descriptions of operations, one in each line. Each line starts with the integer ti, which can take the values 1 and 2. If ti equals 1, two integers li and ri, 1 ≤ li ≤ ri ≤ N follow it. It means — it is necessary to define if the substring slisli + 1... sri is a palindrome. If ti equals 2, it is followed by the integer pi and a small Latin letter ci. It means — to substitute in the string S sign in position pi to ci\n\n## Output\n\nOutput \"YES\" in separate lines for each operation of the palindrome definition if the substring is a palindrome, or \"NO\", if it isn’t (without quotations).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ S \\in \\Sigma^N $ be a string of length $ N $, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ K \\in \\mathbb{Z}^+ $ be the number of operations.  \n\n**Operations**  \nFor each operation $ i \\in \\{1, \\dots, K\\} $:  \n- If $ t_i = 1 $: given $ l_i, r_i \\in \\mathbb{Z} $ with $ 1 \\leq l_i \\leq r_i \\leq N $, query whether the substring $ S[l_i:r_i] $ is a palindrome.  \n- If $ t_i = 2 $: given $ p_i \\in \\mathbb{Z} $ with $ 1 \\leq p_i \\leq N $ and $ c_i \\in \\Sigma $, update $ S[p_i] \\leftarrow c_i $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ 1 \\leq K \\leq 10^5 $  \n3. For all operations:  \n   - $ t_i \\in \\{1, 2\\} $  \n   - If $ t_i = 1 $: $ 1 \\leq l_i \\leq r_i \\leq N $  \n   - If $ t_i = 2 $: $ 1 \\leq p_i \\leq N $, $ c_i \\in \\Sigma $  \n\n**Objective**  \nFor each operation with $ t_i = 1 $, output:  \n$$\n\\begin{cases}\n\\text{``YES''} & \\text{if } S[l_i:r_i] = \\text{reverse}(S[l_i:r_i]) \\\\\n\\text{``NO''} & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10083G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}