CF610E Alphabet Permutations

You are given a string $ s $ of length $ n $ , consisting of first $ k $ lowercase English letters. We define a $ c $ -repeat of some string $ q $ as a string, consisting of $ c $ copies of the string $ q $ . For example, string "acbacbacbacb" is a $ 4 $ -repeat of the string "acb". Let's say that string $ a $ contains string $ b $ as a subsequence, if string $ b $ can be obtained from $ a $ by erasing some symbols. Let $ p $ be a string that represents some permutation of the first $ k $ lowercase English letters. We define function $ d(p) $ as the smallest integer such that a $ d(p) $ -repeat of the string $ p $ contains string $ s $ as a subsequence. There are $ m $ operations of one of two types that can be applied to string $ s $ : 1. Replace all characters at positions from $ l_{i} $ to $ r_{i} $ by a character $ c_{i} $ . 2. For the given $ p $ , that is a permutation of first $ k $ lowercase English letters, find the value of function $ d(p) $ . All operations are performed sequentially, in the order they appear in the input. Your task is to determine the values of function $ d(p) $ for all operations of the second type.

The first line contains three positive integers $ n $ , $ m $ and $ k $ ( $ 1

For each query of the second type the value of function $ d(p) $ .

After the first operation the string $ s $ will be abbbbba. In the second operation the answer is $ 6 $ -repeat of abc: ABcaBcaBcaBcaBcAbc. After the third operation the string $ s $ will be abbcbba. In the fourth operation the answer is $ 5 $ -repeat of cba: cbAcBacBaCBacBA. Uppercase letters means the occurrences of symbols from the string $ s $ .