Bessie is using the latest and greatest innovation in text-editing software, miV! Its powerful find-and-replace feature allows her to find all occurrences of a lowercase English letter c and replace each with a nonempty string of lowercase letters s. For example, given the string "ball", if Bessie selects c to be 'l' and s to be "na", the given string transforms into "banana".

Bessie starts with the string "a" and transforms it using a number of these find-and-replace operations, resulting in a final string S. Since S could be massive, she wants to know, given l and r with 1≤l≤r≤min(|S|,10¹⁸), what S_l…r (the substring of S from the l-th to the r-th character inclusive) is.

It is guaranteed that the sum of |s| over all operations is at most 2⋅10⁵, and that r−l+1≤2⋅10⁵.

#5472 upload - done - how_to_reg -

Find and Replace timer 1s memory 32MB

#5472

Find and Replace 1s 32MB