{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"There 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"},{"iden":"output","content":"Output \"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)."},{"iden":"examples","content":"Inputababaccc81 1 51 1 81 2 42 5 b2 6 a2 7 b2 8 a1 1 8OutputYESNOYESYESInputaaaa101 1 11 1 21 1 31 1 41 2 21 2 31 2 41 3 31 3 41 4 4OutputYESYESYESYESYESYESYESYESYESYES"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":"You are given a string of lowercase letters. You need to handle two types of operations:\n\n1. Query: Check if a substring from position l to r is a palindrome. Print \"YES\" if it is, \"NO\" otherwise.\n2. Update: Change the character at position p to a new letter c.\n\nDo this for K operations.","has_page_source":false}