CF914F Substrings in a String

Description

Given a string $ s $ , process $ q $ queries, each having one of the following forms: - $ 1ic $ — Change the $ i $ -th character in the string to $ c $ . - $ 2lry $ — 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.

Input Format

N/A

Output Format

N/A

Explanation/Hint

Consider the first sample case. Initially, the string aba occurs $ 3 $ times in the range $ [1,7] $ . Note that two occurrences may overlap. After the update, the string becomes ababcbaba and now aba occurs only once in the range $ [1,7] $ .