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:
-
Replace all characters at positions from li to ri by a character ci.
-
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.
Output
For each query of the second type the value of function
d(p).
Note
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.