{"raw_statement":[{"iden":"statement","content":"Given a string _s_, process _q_ queries, each having one of the following forms:\n\n*   1 _i_ _c_ — Change the _i_\\-th character in the string to _c_.\n*   2 _l_ _r_ _y_ — Consider the substring of _s_ starting at position _l_ and ending at position _r_. Output the number of times _y_ occurs as a substring in it."},{"iden":"input","content":"The first line of the input contains the string _s_ (1 ≤ |_s_| ≤ 105) of lowercase English letters.\n\nThe second line contains an integer _q_ (1 ≤ _q_ ≤ 105) — the number of queries to process.\n\nThe next _q_ lines describe the queries and may have one of the following forms:\n\n*   1 _i_ _c_ (1 ≤ _i_ ≤ |_s_|)\n*   2 _l_ _r_ _y_ (1 ≤ _l_ ≤ _r_ ≤ |_s_|)\n\n_c_ is a lowercase English letter and _y_ is a non-empty string consisting of only lowercase English letters.\n\nThe sum of |_y_| over all queries of second type is at most 105.\n\nIt is guaranteed that there is at least one query of second type.\n\nAll strings are 1\\-indexed.\n\n|_s_| is the length of the string _s_."},{"iden":"output","content":"For each query of type 2, output the required answer in a separate line."},{"iden":"examples","content":"Input\n\nababababa\n3\n2 1 7 aba\n1 5 c\n2 1 7 aba\n\nOutput\n\n3\n1\n\nInput\n\nabcdcbc\n5\n2 1 7 bc\n1 4 b\n2 4 7 bc\n1 2 a\n2 1 4 aa\n\nOutput\n\n2\n2\n1"},{"iden":"note","content":"Consider the first sample case. Initially, the string _aba_ occurs 3 times in the range \\[1, 7\\]. Note that two occurrences may overlap.\n\nAfter the update, the string becomes _ababcbaba_ and now _aba_ occurs only once in the range \\[1, 7\\]."}],"translated_statement":[{"iden":"statement","content":"给定一个字符串 $s$，处理 $q$ 个查询，每个查询具有以下形式之一：\n\n输入的第一行包含字符串 $s$（$1 ≤ |s| ≤ 10^5$），由小写英文字母组成。\n\n第二行包含一个整数 $q$（$1 ≤ q ≤ 10^5$）——需要处理的查询数量。\n\n接下来的 $q$ 行描述查询，可能具有以下形式之一：\n\n$1\\ i\\ c$（$1 ≤ i ≤ |s|$）\n\n$2\\ l\\ r\\ y$（$1 ≤ l ≤ r ≤ |s|$）\n\n其中 $c$ 是一个小写英文字母，$y$ 是一个仅由小写英文字母组成的非空字符串。\n\n所有第二类查询中 $|y|$ 的总和不超过 $10^5$。\n\n保证至少存在一个第二类查询。\n\n所有字符串均为 $1$-索引。\n\n$|s|$ 表示字符串 $s$ 的长度。\n\n对于每个第二类查询，请在单独一行中输出所需答案。\n\n考虑第一个样例。初始时，字符串 _aba_ 在区间 $[1, 7]$ 中出现 $3$ 次。注意，两个出现可以重叠。\n\n更新后，字符串变为 _ababcbaba_，现在 _aba_ 在区间 $[1, 7]$ 中仅出现一次。"},{"iden":"input","content":"输入的第一行包含字符串 $s$（$1 ≤ |s| ≤ 10^5$），由小写英文字母组成。第二行包含一个整数 $q$（$1 ≤ q ≤ 10^5$）——需要处理的查询数量。接下来的 $q$ 行描述查询，可能具有以下形式之一： $1\\ i\\ c$（$1 ≤ i ≤ |s|$） $2\\ l\\ r\\ y$（$1 ≤ l ≤ r ≤ |s|$）其中 $c$ 是一个小写英文字母，$y$ 是一个仅由小写英文字母组成的非空字符串。所有第二类查询中 $|y|$ 的总和不超过 $10^5$。保证至少存在一个第二类查询。所有字符串均为 $1$-索引。$|s|$ 表示字符串 $s$ 的长度。"},{"iden":"output","content":"对于每个第二类查询，请在单独一行中输出所需答案。"},{"iden":"examples","content":"输入\nababababa\n3\n2 1 7 aba\n1 5 c\n2 1 7 aba\n输出\n3\n1\n\n输入\nabcdcbc\n5\n2 1 7 bc\n1 4 b\n2 4 7 bc\n1 2 a\n2 1 4 aa\n输出\n2\n2\n1"},{"iden":"note","content":"考虑第一个样例。初始时，字符串 _aba_ 在区间 $[1, 7]$ 中出现 $3$ 次。注意，两个出现可以重叠。更新后，字符串变为 _ababcbaba_，现在 _aba_ 在区间 $[1, 7]$ 中仅出现一次。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ s \\in \\Sigma^* $ be a string of length $ n = |s| $, where $ \\Sigma $ is the set of lowercase English letters, and $ s $ is 1-indexed.\n- Let $ q \\in \\mathbb{N} $ be the number of queries.\n- Two types of queries:\n  1. **Update**: Replace the character at position $ c $ (1-indexed) with a new character (implicitly, the string $ s $ is modified).\n  2. **Query**: Given a non-empty pattern string $ y $, count the number of occurrences of $ y $ as a substring in the prefix $ s[1..7] $ (i.e., the first 7 characters of the current string $ s $).\n\n**Constraints:**\n\n- $ 1 \\leq n \\leq 10^5 $\n- $ 1 \\leq q \\leq 10^5 $\n- For each query of type 2, $ y \\in \\Sigma^+ $, and the total sum of $ |y| $ over all type-2 queries is $ \\leq 10^5 $\n- At least one query is of type 2.\n- All string indices are 1-based.\n\n**Objective:**\n\nFor each query of type 2, compute:\n\n$$\n\\left| \\left\\{ i \\in [1, 7 - |y| + 1] \\mid s[i..i + |y| - 1] = y \\right\\} \\right|\n$$\n\nThat is, the number of starting positions $ i $ in the range $ [1, 7 - |y| + 1] $ such that the substring of $ s $ from position $ i $ to $ i + |y| - 1 $ equals $ y $.\n\n**Note:** After each update query (type 1), the string $ s $ is modified in-place, and subsequent queries operate on the updated string.","simple_statement":null,"has_page_source":false}