서로 다른 부분 문자열 쿼리 2

비어있는 문자열 S가 있다. 이때, 아래와 같이 쿼리를 수행하는 프로그램을 작성하시오.

• c: S의 가장 뒤에 문자 c를 추가한다. 이때, c는 알파벳 소문자이다.
• ?: S의 서로 다른 부분 문자열의 개수를 출력한다.

첫째 줄에 문자열 Q가 주어진다. 문자열 Q는 쿼리를 의미하며, 쿼리를 한 줄로 합친 문자열이다. 문자열은 알파벳 소문자 또는 ?로만 이루어져 있고, 길이는 200,000을 넘지 않는다. Q에 포함되어 있는 ?의 개수는 하나 이상이다.

?가 주어질 때마다, S의 서로 다른 부분 문자열의 개수를 출력한다.