Строку s[a, b] = s_as_a + 1... s_b (1 ≤ a ≤ b ≤ |s|) назовем подстрокой строки s = s₁s₂... s_|s|, где |s| — длина строки s.

Следом непустой строки t называется множество символов, из которых она состоит. Например, след строки «aab» равен {'a', 'b'}.

Для заданного непустого множества символов C можно рассмотреть все максимальные по включению подстроки строки s, след которых равен C. Количество таких подстрок s для множества C будем называть r(C, s). Подстрока s[a, b] длины n = b - a + 1 называется максимальной по включению, если не существует удовлетворяющей заданному свойству подстроки s[x, y] длины большей n, такой что 1 ≤ x ≤ a ≤ b ≤ y ≤ |s|. Две подстроки строки s считаются различными, даже если они совпадают, но начинаются в различных позициях строки s.

На экзамене по строковедению, Поликарпу достался не самый простой билет. Ему нужно выполнить следующее практическое задание: даны строка s и непустые множества символов C₁, C₂, ..., C_m, для каждого множества C_i надо найти r(C_i, s). Помогите Поликарпу решить задачу, он так не хочет в армию!